文章目录
求【L,R】区间满足某种性质数的个数
模板：
int dfs(int pos, int pre, int lead, int limit){
if(!pos) { 边界 }
if(!limit && !lead && dp[pos][pre] != -1) return dp[pos][pre];
int res = 0;
int mx = limit ? a[pos] : 9;
for(int i = 0; i < mx; ++i)
{
if( 不符合的 ) continue;
res += dfs(pos - 1, i, i == 0 && lead, limit && i == mx);
}
return limit ? res : lead ? res : dp[pos][pre] = res;
}
int cal(int x)
{
memset(dp, -1, sizeof dp);
len = 0;
while (x) a[++len] = x % 10, x /= 10;
return dfs(len, 0, 1 ,1 ); // 枚举第几个数， 前面一个数是多少，有没有前导零，有没有限制
}
int main()
{
cin >> L >> R;
cout << cal(R) - cal(L - 1) << endl;
return 0;
}
不要62
题意：找到区间 [ L , R ] [L, R] [L,R]内不能出现4或62的次数
Code：
#include<bits/stdc++.h>
using namespace std;
const int N = 15;
int l, r, dp[N][N], len, a[N];
//a[i]表示第i位的数，dp[i][j]表示第i位且前位是pre的满足数的个数
int dfs(int pos, int pre, bool limit)
{
if(!pos) return 1; // 枚举位数到头了返回1
if( !limit && dp[pos][pre] != -1) return dp[pos][pre];
// 记忆化搜索，没有限制并且这个被搜过了就直接返回即可
int res = 0;
int mx = limit ? a[pos] : 9; // 判断是否受限
for(int i = 0; i <= mx; ++i)
{
// 不满足题意得
if(i == 4 || ( i == 2 && pre == 6)) continue;
res += dfs(pos - 1, i, limit && i == mx);
// 枚举下一位，且前一位是i，如果当前有限制且到达了最大，那么下一位也将受限
}
return limit ? res : dp[pos][pre] = res;
}
int cal( int x )
{
memset(dp, -1, sizeof dp); // 初始化
len = 0; // 获取该数的每一位
while ( x ) a[ ++ len] = x % 10 , x /= 10;
return dfs(len, 0, 1);
}
int main()
{
while(cin >> l >> r, l && r)
cout << cal(r) - cal(l - 1) << endl;
return 0;
}
windy数
H a r d \color{red}{Hard} Hard
题意：求区间 [ L , R ] [L, R] [L,R]之间相邻数字只差不小于 2 2 2的个数
- sol：初始时， p r e pre pre要设置为一个 ≤ − 2 \le -2 ≤−2的数，为的是找到目标数的首位
Code：
#include<bits/stdc++.h>
using namespace std;
const int N = 15;
int l, r, dp[N][N], len, a[N];
int dfs(int pos, int pre, int lead, bool limit)
{
if(!pos) return 1;
if( !limit && !lead && dp[pos][pre] != -1) return dp[pos][pre];
int res = 0;
int mx = limit ? a[pos] : 9;
for(int i = 0; i <= mx; ++i)
{
if(abs(pre - i) < 2) continue;
if(lead && !i) { // 继续往下找到符合数字的第一位
res += dfs(pos - 1, -2, 1, limit && i == mx);
}
else {
res += dfs(pos - 1, i, 0, limit && i == mx);
}
}
return limit ? res : dp[pos][pre] = res;
}
int cal( int x )
{
memset(dp, -1, sizeof dp);
len = 0;
while ( x ) a[ ++ len] = x % 10 , x /= 10;
return dfs(len, -2, 1, 1);
}
int main()
{
cin >> l >> r;
cout << cal(r) - cal(l - 1) << endl;
return 0;
}
花神的数论题
H
a
r
d
\color{red}{Hard}
Hard
题意：
s
u
m
i
sum_i
sumi表示
i
i
i的二进制中1的个数，求
∏
i
=
1
n
s
u
m
i
\prod_{i=1}^{n}sum_i
∏i=1nsumi
Sol：我们定义 G k G_k Gk为 ∑ i = 1 n ( s u m i = = k ) \sum_{i=1}^n (sum_i == k) ∑i=1n(sumi==k)，易知答案就为： ∏ i = 1 50 i G i \prod_{i=1}^{50} i^{G_i} ∏i=150iGi，利用数位dp求出 1 ∼ n 1 \sim n 1∼n的 G i G_i Gi，然后快速幂计算
Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod =10000007;
LL x,len, dp[64][64], a[64], G[64], P;
LL qpow( LL a, LL b)
{
LL res = 1;
while(b) {
if(b & 1) res = res * a % mod;
b >>= 1;a = a * a % mod;}
return res;
}
LL dfs( int pos, int sum, bool limit)
{
if(!pos) {
return sum == P;
}
if( !limit && dp[pos][sum] != -1) return dp[pos][sum];
LL res = 0;
int mx = limit ? a[pos] : 1;
for(int i = 0; i <= mx; ++i)
{
if(sum > P) continue;
res += dfs(pos - 1, sum + (i != 0), limit && i == mx);
}
return limit ? res : dp[pos][sum] = res;
}
LL cal( LL x )
{
len = 0;
while (x) a[ ++len] = x % 2, x /= 2;
for( P = 1; P < 50; ++P)
{
memset(dp, -1, sizeof dp);
G[P] = dfs(len, 0, 1);
}
LL ans = 1;
for(int i = 1; i < 50; ++i)
ans = ans * qpow(i, G[i])% mod;
return ans % mod;
}
int main()
{
cin >> x;
cout << cal(x) << endl;
return 0;
}
Beautiful numbers
题目链接:Beautiful numbers
H
a
r
d
\color{red}{Hard}
Hard
题意:
T组访问,求出
[
L
,
R
]
[L,R]
[L,R]之间的漂亮数.
漂亮数:能够被每个非零位整除的数
- Sol:
求区间内特殊性质数的个数,显然要数位DP.
首先,一个性质:一个数能被他的每个非零位整除,那么这个数也能被各数位的 l c m lcm lcm整除,又因为 1 ∼ 9 1 \sim 9 1∼9的 l c m lcm lcm为 2520 2520 2520,那么只要保证这个数能被 2520 2520 2520整除就是漂亮数.
考虑到数位DP存不下 9 e 18 9e18 9e18这么大的数,考虑取模.记录模数的同时,还要记录 l c m lcm lcm,这样的话DP数组会开到 d p [ 20 ] [ 2522 ] [ 2522 ] dp[20][2522][2522] dp[20][2522][2522],显然会MLE的,对于 l c m lcm lcm来说,他的因子只有 48 48 48个,其余的都是不符合的不用记录, l c m lcm lcm用哈希映射.
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
LL dp[22][2522][52];
int a[22];
int hah[2522], cnt;
int len;
LL gcd(LL a, LL b)
{
return b ? gcd(b, a%b) : a;
}
LL lcm(LL a, LL b)
{
return a / gcd(a, b) * b;
}
// 初始化,将2520的因子选出来
void init()
{
for(int i = 1; i <= 2520; ++i)
if(2520 % i == 0) hah[i] = ++cnt;
}
// 位数,当前的模2520的结果,当前的lcm,是否受限
LL dfs(int pos, int presum, int prelcm, bool limit)
{
if(!pos) {
// 能被整除即是漂亮数
return presum % prelcm == 0;
}
// 注意哈希映射
// 记忆化s
if(!limit && dp[pos][presum][hah[prelcm]] != -1) return dp[pos][presum][hah[prelcm]];
int mx = limit ? a[pos] : 9;
LL res = 0;
for(int i = 0; i <= mx; ++i)
{
int nowlcm = prelcm;
if(i) nowlcm = lcm(prelcm, i);
res += dfs(pos - 1, (presum * 10 + i) % 2520, nowlcm, i == mx && limit);
}
return limit ? res : dp[pos][presum][hah[prelcm]] = res;
}
LL calc(LL x)
{
len = 0;
while(x)
a[++len] = x % 10, x /= 10;
return dfs(len, 0, 1, 1);
}
void solve()
{
LL R , L;
cin >> L >> R;
cout << calc(R) - calc(L - 1) << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
memset(dp, -1, sizeof dp);
int T = 1;
init();
cin >> T;
while( T -- )
solve();
return (0-0);
}
求【L，R】区间满足某种性质数的平方和，立方和
恨7不成妻
H
a
r
d
\color{red}{Hard}
Hard
题目链接：Acwing 1086 / HDU4507
题意：
如果一个整数符合下面三个条件之一，那么我们就说这个整数和 7 有关：
- 整数中某一位是 7；
- 整数的每一位加起来的和是 7 的整数倍；
- 这个整数是 7 的整数倍。
现在问题来了：吉哥想知道在一定区间内和 7 无关的整数的平方和。
- sol：讲不清qwq
code：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 20, mod = 1e9 + 7;
int a[N], len;
int pow_10[N];
struct F{
int s0, s1, s2;
void operator += (const F &b){
s0 = (s0 + b.s0 ) % mod;
s1 = (s1 + b.s1 ) % mod;
s2 = (s2 + b.s2 ) % mod;
}
};
F dp[N][N][N];
F dfs(int pos, int m, int sum, bool limit) {
if(!pos) {
if(m && sum) return {1, 0, 0};
else return {0, 0, 0};
}
if(!limit && ~dp[pos][sum][m].s0) return dp[pos][sum][m];
int mx = limit ? a[pos] : 9;
F res = {0, 0, 0};
for(int i = 0; i <= mx; ++ i) {
if(i == 7) continue;
F t = dfs(pos - 1, (m * 10 + i) % 7, (sum + i) % 7, limit && i == mx);
int k = i * pow_10[pos - 1] % mod;
t.s2 = (t.s2 + 2 * k % mod * t.s1 % mod) % mod;
t.s2 = (t.s2 + k * k % mod * t.s0 % mod) % mod;
t.s1 = (t.s1 + k * t.s0 % mod) % mod;
res += t;
}
return limit ? res : dp[pos][sum][m] = res;
}
int calc(int x) {
len = 0;
while(x) a[++ len] = x % 10, x /= 10;
return dfs(len, 0, 0, 1).s2;
}
signed main()
{
memset(dp, -1, sizeof dp);
pow_10[0] = 1;
for(int i = 1; i < 20; ++ i)
pow_10[i] = (pow_10[i - 1] * 10) % mod;
int t, l, r;
cin >> t;
while(t -- ) {
cin >> l >> r;
cout << ( calc(r) % mod - calc(l - 1) % mod + mod) % mod << "\n";
}
}
不要666升级版
H
a
r
d
\color{red}{Hard}
Hard
子问题：不要666
- Sol：讲不清qwq
Code：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 20, mod = 1e9 + 7;
int a[N], len;
int pow_10[N];
struct F{
int s0, s1, s2, s3;
void operator += (const F &b){
s0 = (s0 + b.s0 ) % mod;
s1 = (s1 + b.s1 ) % mod;
s2 = (s2 + b.s2 ) % mod;
s3 = (s3 + b.s3 ) % mod;
}
};
F dp[N][N][N];
F dfs(int pos, int m, int sum, bool limit) {
if(!pos) {
if(m && sum) return {1, 0, 0};
else return {0, 0, 0};
}
if(!limit && ~dp[pos][sum][m].s0) return dp[pos][sum][m];
int mx = limit ? a[pos] : 9;
F res = {0, 0, 0};
for(int i = 0; i <= mx; ++ i) {
if(i == 6) continue;
F t = dfs(pos - 1, (m * 10 + i) % 6, (sum + i) % 6, limit && i == mx);
int k = i * pow_10[pos - 1] % mod;
t.s3 = (t.s3 + k % mod * k % mod * k % mod * t.s0 % mod) % mod;
t.s3 = (t.s3 + 3 * k % mod * t.s2 % mod + 3 * k % mod * k % mod * t.s1 % mod) % mod;
t.s2 = (t.s2 + 2 * k % mod * t.s1 % mod) % mod;
t.s2 = (t.s2 + k * k % mod * t.s0 % mod) % mod;
t.s1 = (t.s1 + k * t.s0 % mod) % mod;
res += t;
}
return limit ? res : dp[pos][sum][m] = res;
}
int calc(int x) {
len = 0;
while(x) a[++ len] = x % 10, x /= 10;
return dfs(len, 0, 0, 1).s3;
}
signed main()
{
memset(dp, -1, sizeof dp);
pow_10[0] = 1;
for(int i = 1; i < 20; ++ i)
pow_10[i] = (pow_10[i - 1] * 10) % mod;
int t, l, r;
// cin >> t;
while(cin >> l >> r) {
cout << ( calc(r) % mod - calc(l - 1) % mod + mod) % mod << "\n";
}
}