- 1、计数问题
- 2、度的数量
- 3、数字游戏
- 4、Windy数
- 5、数字游戏 II
- 6、不要62
- 7、恨7不成妻
数位DP技巧：
- [X, Y] → f(Y) - f(X - 1)，f(N)表示 1 ~ N 中满足某种性质的个数。比如第一题计数问题；
- 利用树的角度考虑，比如度的数量。
ACWing 338
算法思路：一定要分情况讨论
首先，题目要求在[a, b]中0 ~ 9这10个数中分别出现的次数，那么我们先实现一个函数count(n, x)：求出从 1 ~ n 中 x 出现的次数，则在[a, b]中x出现的次数表示为cout(b, x) - count(a-1, x)（类似于前缀和）。
对count(n, x)函数，例如当x=1时，则count(n, 1)表示为从1 ~ n中找出1出现的次数。先求出1在1 ~ n中每一个位上出现的次数，则其总和即为count(n, 1)。
例如有abcdefg，则1在第四位出现可以表示为1 <= xxx1yyy <= abcdefg，即为表示在1 ~ abcdefg之间有多少个数的形式是xxx1yyy。分情况讨论：
- ① 若xxx = 000 ~ abc - 1时，xxx1yyy < abc1yyy <= abc1efg，则yyy 可取 000 ~ 999，总共有abc * 1000种选法；
- ② 若xxx = abc时：
- 若d < 1即d = 0时，则第四位为1即abc1yyy，但是abc1yyy > abc0efg，超出了范围，总共有0种选法；
- 若d = 1时，即abc1yyy，则yyy 只能取 000 ~ efg，总共有efg + 1种选法；
- 若d > 1时，则abcdefg > abc1yyy，故yyy可取000 ~ 999，共1000种选法。
由以上，依次类推，可以求出1在任意一位数上出现的次数，然后将每一个位上的1出现的次数累加起来，就能得到1在1 ~ n位中整个出现的次数。依次类推，可以求出1 ~ 9每一个数在1 ~ n中整个出现的次数。
边界情况：
- 当枚举数字0的时候，对于②不存在前导零，不用考虑；对于①，只能从001开始枚举。
# include2、度的数量# include using namespace std; int dgt(int n) // 计算整数n有多少位 { int res = 0; while (n) ++ res, n /= 10; return res; } int cnt(int n, int i) // 计算从1到n的整数中数字i出现多少次 { int res = 0, d = dgt(n); // d是n的位数 for (int j = 1; j <= d; ++ j) // 计算从右到左第j位上数字i出现多少次 { // l和r是第j位左边和右边的整数 (视频中的abc和efg); dj是第j位的数字 int p = pow(10, j - 1), l = n / p / 10, r = n % p, dj = n / p % 10; // 计算第j位左边的整数小于l (视频中xxx = 000 ~ abc - 1)的情况 if (i) res += l * p; // 如果i = 0, 左边高位不能全为0(视频中xxx = 001 ~ abc - 1) if (!i && l) res += (l - 1) * p; // 计算第j位左边的整数等于l，不能存在前导零 (视频中xxx = abc)的情况 if ( (dj == i) && (i || l) ) res += r + 1; if ( (dj > i) && (i || l) ) res += p; } return res; } int main() { int a, b; while (cin >> a >> b , a) { if (a > b) swap(a, b); for (int i = 0; i <= 9; ++ i) cout << cnt(b, i) - cnt(a - 1, i) << ' '; cout << endl; } return 0; }
ACwing 1081
题中引例的意思实质上是：找到区间[x,y]中的某些数，这些数的B进制(引例是B=2二进制) 表示中仅包含k = 2个1，其余为0。
假设我们需要求 [ 0 , N ] [0, N] [0,N]中满足某种性质的个数即数位DP技巧中的f[N]，若数 N N N是 n n n位数，其表示为 a n − 1 、 a n − 2 、 . . . 、 a 0 a_{n-1}、a_{n-2} 、... 、a_0 an−1、an−2、...、a0。
- 一定要注意审题：这个数恰好等于 K 个互不相等的 B 的整数次幂之和。这句话的意思就表明了 K 个互不相等的 B 的整数次幂前面的系数只能是0 or 1！！！所以在下面图中，比如结点 0 0 0 ~ a n − 1 − 1 a_{n-1}-1 an−1−1 仅有两个分支0 or 1，大于1的分支都不合法！
- 这里 N N N是已经转换为了 B B B进制下的数，比如： 19 19 19，在 3 3 3进制为 19 = ( 201 ) 3 19 =(201)_3 19=(201)3，即 19 = 2 × 3 2 + 0 × 3 1 + 1 × 3 0 19 = 2times3^2+0times3^1+1times3^0 19=2×32+0×31+1×30。
组合数的计算公式 C a b = C a − 1 b − 1 + C a − 1 b C_a^b=C_{a-1}^{b-1}+C_{a-1}^b Cab=Ca−1b−1+Ca−1b。代码中使用f[a][b]来表示：从a中选择b个数的方案数。
#include3、数字游戏#include #include #include using namespace std; const int N = 35; // 1 ≤ X ≤ Y ≤ 2^31−1，所以最多31位 int K, B; int f[N][N]; // f[a][b]：从a个数中选择b个数的方案数 void init() // 预处理f[a][b] { for (int i = 0; i < N; i ++ ) for (int j = 0; j <= i; j ++ ) if (!j) // 如果j == 0 f[i][j] = 1; else f[i][j] = f[i - 1][j] + f[i - 1][j - 1]; } int dp(int n) // 从0 ~ n里面求出满足要求的个数 { if (!n) return 0; // 判边界：因为 K >= 1 vector nums; // 存储n在B进制下的每一位 while (n) nums.push_back(n % B), n /= B; int res = 0, last = 0; // res结果，last前缀信息：前面几位上有几个1 for (int i = nums.size() - 1; i >= 0; i -- ) // 依次处理每一位 { int x = nums[i]; // x = a(n-1) // 处理左边：0 ~ x-1，由题只能填 0 or 1 if (x) // 只有 x>0 的时候才会有左边这个分支 { // 当前这一位填0：从 0 ~ i-1 的i个数选择 k-last 位填上1 res += f[i][K - last]; // 只有x > 1 时，当前位置才能填上 1 if (x > 1) { // 当前这一位填1：从 0 ~ i-1 的i个数中选择 k-last-1 位填上1 if (K - last - 1 >= 0) res += f[i][K - last - 1]; break; // 因为这一位上已经大于1了，而题目要求只能填 1 or 0，所以对应树的右分支a(n-1)无了 } else // x == 1，即 a(n-1) = 1，开始往下一层走 { last ++ ; if (last > K) break; } } // 处理右边：只有最后一个点的右分支a0 if (!i && last == K) res ++ ; } return res; } int main() { init(); int l, r; // 区间 cin >> l >> r >> K >> B; cout << dp(r) - dp(l - 1) << endl; return 0; }
ACwing 1082
算法思路
先求 0 ~ N 中不下降数的个数，记为f(N)。然后使用f(R) - f(L-1)即为所求。
首先，将
N
N
N拆分成成
n
n
n位数：
N
=
a
n
−
1
、
a
n
−
2
、
.
.
.
、
a
0
N=a_{n-1}、a_{n-2}、 ...、 a_0
N=an−1、an−2、...、a0
这里的预处理使用DP来解决。上一题是直接可以使用排列组合求出。
集合
f[i,j]：最高位为j，且一共有i位的不降数的集合的个数
集合划分
按照第i-2位上填的值来划分（第i-1位上为j）
若第i-2位上为k，若去掉第i-1位上的j，则剩下就表示为在剩余i-1中，最高位为k，一共i-1位不降数的个数，表示为f[i-1, k]。所以 f ( i , j ) = ∑ k = 0 9 f ( i − 1 , j + k ) f(i, j)= sum_{k=0}^9 f(i-1, j+k) f(i,j)=∑k=09f(i−1,j+k) 。
#include4、Windy数#include #include #include using namespace std; const int N = 15; int f[N][N]; // f[i][j]：一共有i位，且最高位为j的数的个数 void init() { for (int i = 0; i <= 9; i ++ ) f[1][i] = 1; for (int i = 2; i < N; i ++ ) for (int j = 0; j <= 9; j ++ ) for (int k = j; k <= 9; k ++ ) f[i][j] += f[i - 1][k]; } // 0 ~ n 里面满足要求的个数 int dp(int n) { if (!n) return 1; // n = 0 vector nums; while (n) nums.push_back(n % 10), n /= 10; int res = 0, last = 0; // last前缀信息：存储上一位数 for (int i = nums.size() - 1; i >= 0; i -- ) { int x = nums[i]; // a(n-1) = x // 考虑左边 for (int j = last; j < x; j ++ ) // 枚举[0, x-1]，同时保证后面一位大于前一位，即从last开始枚举 res += f[i + 1][j]; // 一共剩余i+1位 // 考虑右边：判断当前这一位能否填x if (x < last) // 右边分支不存在 break; last = x; // 考虑最后的右分支：最后一位数 if (!i) res ++ ; } return res; } int main() { init(); int l, r; while (cin >> l >> r) cout << dp(r) - dp(l - 1) << endl; return 0; }
ACwing 1083
算法思路
先求 1 ~ N 中Windy数的个数，记为f(N)。然后使用f(R) - f(L-1)即为所求。（注意是从1开始，不能包含前导零）
首先，将 N N N拆分成成 n n n位数： N = a n − 1 、 a n − 2 、 . . . 、 a 0 N=a_{n-1}、a_{n-2}、 ...、 a_0 N=an−1、an−2、...、a0
预处理
集合
f[i, j]：共有i位，最高位是j的Windy数的个数
集合划分
按次高位第j-1位来划分，次高位为k ∈ (0, 9)，所以
f
(
i
,
j
)
=
∑
k
=
0
9
f
(
i
−
1
,
k
)
，
其
中
∣
j
−
k
∣
≥
2
f(i, j)=sum_{k=0}^9f(i-1,k)，其中|j-k| ge2
f(i,j)=∑k=09f(i−1,k)，其中∣j−k∣≥2
#include5、数字游戏 II#include #include #include using namespace std; const int N = 11; int f[N][10]; void init() { for (int i = 0; i <= 9; i ++ ) f[1][i] = 1; for (int i = 2; i < N; i ++ ) for (int j = 0; j <= 9; j ++ ) for (int k = 0; k <= 9; k ++ ) if (abs(j - k) >= 2) f[i][j] += f[i - 1][k]; } int dp(int n) { if (!n) return 0; vector nums; while (n) nums.push_back(n % 10), n /= 10; int res = 0; // 记录上一位数的信息 // 因为第一位可以任意填，所以last只需要填一个能与0~9的差的绝对值都大于等于2的数即可 int last = -2; // 处理无前导零的方案 for (int i = nums.size() - 1; i >= 0; i -- ) { int x = nums[i]; // 处理左边分支 for (int j = i == nums.size() - 1; j < x; j ++ ) // 判断是处理第一个左分支不能为0 if (abs(j - last) >= 2) res += f[i + 1][j]; // 一共有 i+1 位 // 处理右边分支 if (abs(x - last) >= 2) last = x; else break; // 处理最后一位a0，它必是合法的 if (!i) res ++ ; } // 特殊处理有前导零的数 // 对于数字13，他是满足windy数定义的，那么加上前导0之后的013就不会被f[3][0]加进去 // 原因就是abs(0-1)<2，这样就导致答案 漏掉 for (int i = 1; i < nums.size(); i ++ ) for (int j = 1; j <= 9; j ++ ) res += f[i][j]; return res; } int main() { init(); int l, r; cin >> l >> r; cout << dp(r) - dp(l - 1) << endl; return 0; }
ACwing 1084
预处理
集合
f[i, j, k]：一共有i位，最高位是j，且给为数字之和模N的余数是k的方案数个数。
集合划分
按次高位i-1上的值为x来划分，即共有i-1位，最高位为x，且i-1位上的数字之和模N的余数是k-j的方案数。
于是
f
(
i
,
j
,
k
)
=
∑
x
=
0
9
f
(
i
−
1
,
x
,
(
k
−
j
)
m
o
d
N
)
f(i, j, k)=sum_{x=0}^9f(i - 1, x, (k - j)mod N)
f(i,j,k)=∑x=09f(i−1,x,(k−j)modN)
#include6、不要62#include #include #include using namespace std; const int N = 11, M = 110; int P; int f[N][10][M]; int mod(int x, int y) { // 因为 c++ 里面取模负数会得到负数，要得到正数需要处理一下 return (x % y + y) % y; } void init() { memset(f, 0, sizeof f); for (int i = 0; i <= 9; i ++ ) // 处理只有一位数的情况 f[1][i][i % P] ++ ; for (int i = 2; i < N; i ++ ) for (int j = 0; j <= 9; j ++ ) for (int k = 0; k < P; k ++ ) for (int x = 0; x <= 9; x ++ ) f[i][j][k] += f[i - 1][x][mod(k - j, P)]; } int dp(int n) { if (!n) return 1; vector nums; while (n) nums.push_back(n % 10), n /= 10; int res = 0; int last = 0; // 前缀信息：存储前面各位数之和 for (int i = nums.size() - 1; i >= 0; i -- ) { int x = nums[i]; // 左边分支 // (前面各位数之和last + 后面各位数之和sum) mod P = 0 // 所以sum = -last mod P for (int j = 0; j < x; j ++ ) res += f[i + 1][j][mod(-last, P)]; // 右边分支 last += x; // 最后右边分支a0 if (!i && last % P == 0) res ++ ; } return res; } int main() { int l, r; while (cin >> l >> r >> P) { init (); cout << dp(r) - dp(l - 1) << endl; } return 0; }
ACwing 1085
算法思路
先求 0 ~ N 中满足性质的个数，记为f(N)。然后使用f(R) - f(L-1)即为所求。
首先，将 N N N拆分成成 n n n位数： N = a n − 1 、 a n − 2 、 . . . 、 a 0 N=a_{n-1}、a_{n-2}、 ...、 a_0 N=an−1、an−2、...、a0
预处理
集合
f[i, j]：一共有i位数字，最高位是j的数字，其中不包含4和62的数字一共有多少个
集合划分
根据次高位来划分，因此有
f
(
i
,
j
)
=
∑
k
=
0
9
f
(
i
−
1
,
k
)
，
其
中
j
≠
4
,
k
≠
4
,
j
k
≠
62
f(i,j)=sum_{k=0}^9f(i-1,k)，其中jne4,kne4,jkne62
f(i,j)=∑k=09f(i−1,k)，其中j=4,k=4,jk=62。
#include7、恨7不成妻#include #include #include using namespace std; const int N = 35; int f[N][10]; void init() { for (int i = 0; i <= 9; i ++ ) if (i != 4) f[1][i] = 1; for (int i = 2; i < N; i ++ ) for (int j = 0; j <= 9; j ++ ) { if (j == 4) continue; for (int k = 0; k <= 9; k ++ ) { if (k == 4 || j == 6 && k == 2) continue; f[i][j] += f[i - 1][k]; } } } int dp(int n) { if (!n) return 1; vector nums; while (n) nums.push_back(n % 10), n /= 10; int res = 0; int last = 0; // 前缀信息：上一位的值，只要不是6即可 for (int i = nums.size() - 1; i >= 0; i -- ) { int x = nums[i]; // 左边 for (int j = 0; j < x; j ++ ) { if (j == 4 || last == 6 && j == 2) continue; res += f[i + 1][j]; } // 右边 if (x == 4 || last == 6 && x == 2) break; last = x; // 最后一个右分支 if (!i) res ++ ; } return res; } int main() { init(); int l, r; while (cin >> l >> r, l || r) cout << dp(r) - dp(l - 1) << endl; return 0; }
ACwing 1086
算法思路
先求 0 ~ N 中满足性质的个数，记为f(N)。然后使用f(R) - f(L-1)即为所求。
首先，将 N N N拆分成成 n n n位数： N = a n − 1 、 a n − 2 、 . . . 、 a 0 N=a_{n-1}、a_{n-2}、 ...、 a_0 N=an−1、an−2、...、a0
预处理
集合
f[i, j, a, b]：一共有i位，最高位是j，这个数本身模7的余数是a，这个数的各位数字之和模7的余数时b的情况下，所有数的平方和
#include#include #include #include using namespace std; typedef long long LL; const int N = 20, P = 1e9 + 7; struct F { // 分别表示A1、A2、...、At的0次方和，一次方和，平方和 int s0, s1, s2; } f[N][10][7][7]; int power7[N], power9[N]; int mod(LL x, int y) // 取得正余数 { return (x % y + y) % y; } void init() { for (int i = 0; i <= 9; i++) // 处理一位数 { if (i == 7) continue; auto &v = f[1][i][i % 7][i % 7]; v.s0++, v.s1 += i, v.s2 += i * i; } LL power = 10; for (int i = 2; i < N; i++, power *= 10) for (int j = 0; j <= 9; j++) { if (j == 7) continue; for (int a = 0; a < 7; a++) for (int b = 0; b < 7; b++) for (int k = 0; k <= 9; k++) { if (k == 7) continue; auto &v1 = f[i][j][a][b], &v2 = f[i - 1][k][mod(a - j * power, 7)][mod(b - j, 7)]; v1.s0 = mod(v1.s0 + v2.s0, P); v1.s1 = mod(v1.s1 + v2.s1 + j * (power % P) % P * v2.s0, P); v1.s2 = mod(v1.s2 + j * j * (power % P) % P * (power % P) % P * v2.s0 + v2.s2 + 2 * j * power % P * v2.s1, P); } } power7[0] = 1; for (int i = 1; i < N; i++) power7[i] = power7[i - 1] * 10 % 7; power9[0] = 1; for (int i = 1; i < N; i++) power9[i] = power9[i - 1] * 10ll % P; } // 余数不等于a，不等于b的情况 F get(int i, int j, int a, int b) { int s0 = 0, s1 = 0, s2 = 0; for (int x = 0; x < 7; x++) for (int y = 0; y < 7; y++) if (x != a && y != b) { auto v = f[i][j][x][y]; s0 = (s0 + v.s0) % P; s1 = (s1 + v.s1) % P; s2 = (s2 + v.s2) % P; } return {s0, s1, s2}; } int dp(LL n) { if (!n) return 0; LL backup_n = n % P; vector nums; while (n) nums.push_back(n % 10), n /= 10; int res = 0; LL last_a = 0, last_b = 0; // 上一个数本身的值 上一个数各位数之和 for (int i = nums.size() - 1; i >= 0; i--) { int x = nums[i]; for (int j = 0; j < x; j++) { if (j == 7) continue; int a = mod(-last_a * power7[i + 1], 7); int b = mod(-last_b, 7); auto v = get(i + 1, j, a, b); res = mod( res + (last_a % P) * (last_a % P) % P * power9[i + 1] % P * power9[i + 1] % P * v.s0 % P + v.s2 + 2 * last_a % P * power9[i + 1] % P * v.s1, P); } if (x == 7) break; last_a = last_a * 10 + x; last_b += x; if (!i && last_a % 7 && last_b % 7) res = (res + backup_n * backup_n) % P; } return res; } int main() { int T; cin >> T; init(); while (T--) { LL l, r; cin >> l >> r; cout << mod(dp(r) - dp(l - 1), P) << endl; } return 0; }
