数位 DP 唯一需要考虑的就是如何求不限定范围，只限定位数的情况下的方案数。
【Ural 1057】Amount of Degrees
求 $[x,y]$ 范围内恰好可以拆分为 $k$ 个 $b$ 的整数次幂（不重复）的数的个数。
$1\le x,y\le 2^{31}-1$，$1\le k\le 20$，$2\le b\le 10$。
拆分成前缀和的形式，$f(x)$ 表示 $[0,x]$ 范围内的解，则答案为 $f(y)-f(x-1)$。
问题等价于将数字转化为 $b$ 进制后 $1$ 的位数为 $k$ 的方案数。
数位 DP 的思想是从高位到低位沿着 $x$ 的上界进行枚举，每次累加这一位取不到上界时的方案数，本题中，这个方案数就是组合数。
时间复杂度为 $O(log^2n)$，瓶颈在于预处理组合数。
细节有：如果 $x$ 满足条件需要在最后累加进去，且一旦有一位上的数大于 $1$ 则代表后面若干位可以任意填 $1$，这时需要跳出循环，选择了 $k$ 个 $1$ 后也应跳出循环，此时后面的若干位应全部填 $0$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include <cstdio>
typedef long long int ll;
int k, b; ll c[35][35];
inline void prelude() {
c[0][0] = 1;
for(int i = 1; i <= 32; ++i) {
c[i][0] = 1;
for(int j = 1; j <= i; ++j) {
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
}
}
}
int bits[35], cnt = 0;
inline int solve(int num) {
cnt = 0;
while(num > 0) {
bits[cnt++] = num % b;
num /= b;
}
ll ans = 0; int curk = k;
for(int i = cnt; i > 0; --i) {
if(bits[i - 1] > 1) {
ans += c[i][curk];
break;
}
else if(bits[i - 1] == 1) {
ans += c[i - 1][curk];
--curk; if(curk < 0) break;
}
}
int cnt1 = 0;
for(int i = 0; i < cnt; ++i) {
if(bits[i] > 1) { cnt1 = -1; break; }
else cnt1 += bits[i];
}
return cnt1 == k ? ans + 1 : ans;
}
int main() {
prelude();
int x, y; scanf("%d %d %d %d", &x, &y, &k, &b);
printf("%d\n", solve(y) - solve(x - 1));
return 0;
}
|
【USACO Nov06】Round Numbers
【ZJOI 2010】数字计数
求对于 $[a,b]$ 的所有整数，$[0,9]$ 各出现多少次。
$1\le a\le b\le 10^{12}$。
问题转化为求 $[0,x]$ 的所有整数中 $[0,9]$ 的出现次数。
从高位开始枚举每一位，用数位 DP 解决的前提是可以在较短的时间内给出当前位不取上界时剩下位任取的结果，这里就是计算 $[0\dots 0,9\dots 9]$ 中 $[0,9]$ 的出现次数，它们是相同的，且可以方便地求出来。
注意下沿和上界。
当首位取 $0$ 时，可以先正常计算贡献，再枚举起始 $0$ 结束的位置除去多计算的 $0$ 的个数。
当继续沿着上界走时，对当前填入数字的贡献是后续填入不超过 $x$ 的所有低位的方案数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include <cstdio>
typedef long long int ll;
ll f[20], p[20];
inline void prelude() {
p[0] = 1; p[1] = 10; f[1] = 1;
for(int i = 2; i <= 15; ++i) {
p[i] = p[i - 1] * 10;
f[i] = f[i - 1] * 10 + p[i - 1];
}
}
int bits[20], cnt = 0;
inline void solve(ll num, ll ans[]) {
for(int i = 0; i <= 9; ++i) ans[i] = 0;
cnt = 0;
while(num > 0) {
bits[cnt++] = num % 10;
num /= 10;
}
for(int i = cnt; i > 0; --i) {
int &cur = bits[i - 1];
if(cur == 0) {
ll contribute = 0;
for(int j = i - 2; j >= 0; --j) {
contribute = contribute * 10 + bits[j];
}
ans[0] += contribute;
}
else {
if(i == cnt) {
for(int j = 0; j <= 9; ++j) ans[j] += f[i - 1];
for(int j = i - 2; j >= 0; --j) {
ans[0] -= p[j];
}
for(int j = 1; j <= cur - 1; ++j) {
ans[j] += p[i - 1];
for(int k = 0; k <= 9; ++k) {
ans[k] += f[i - 1];
}
}
ll contribute = 0;
for(int j = i - 2; j >= 0; --j) {
contribute = contribute * 10 + bits[j];
}
ans[cur] += contribute;
}
else {
for(int j = 0; j <= cur - 1; ++j) {
ans[j] += p[i - 1];
for(int k = 0; k <= 9; ++k) {
ans[k] += f[i - 1];
}
}
ll contribute = 0;
for(int j = i - 2; j >= 0; --j) {
contribute = contribute * 10 + bits[j];
}
ans[cur] += contribute;
}
}
}
for(int i = 0; i < cnt; ++i) {
++ans[bits[i]];
}
}
int main() {
prelude();
ll a, b; scanf("%lld %lld", &a, &b);
ll ansb[10], ansaso[10];
solve(b, ansb); solve(a - 1, ansaso);
for(int i = 0; i <= 9; ++i) {
printf("%lld%c", ansb[i] - ansaso[i], (i ^ 9) ? ' ' : '\n');
}
return 0;
}
|
【SCOI 2009】windy 数