「ZJOI2010」数字计数-数位dp

给定两个正整数$a$和$b$,求在$[a,b]$中的所有整数中,每个数码(digit)各出现了多少次。

链接

Luogu P2602

题解

比较入门的数位dp…很适合我这种蒟蒻。

令$dp[i][j]$为当倒数第$i$位为$j$时,后$i$位的数码总计(一个储存着十个整数的结构体,加减即为对位加减)。若$j=10$,则代表这位是前导$0$。(感觉这个搞法有点笨拙…巨佬能不能教教我…)

令$sum(i,j)$为有$i$数码有$j$个,其他均为$0$的状态。

则状态转移方程为:

$$dp[1][j] = sum(j,1)$$

$$dp[i][j] = sum(j,10^{i-1}) + \sum_{w = 0}^{9} dp[i-1][w]\; ,0\leq j \leq 9$$

$$dp[i][10] = \sum_{w = 1}^{10} dp[i-1][w]$$

计算答案时,这个实在不太好说…看代码的注释会更好理解…

代码

点击切换显示状态
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <cstdio>
using namespace std;
#define ll long long

ll a,b;

const int MAXN = 20;

struct sum{
ll num[10];
sum(int pos = -1,ll d = 1){
for(int i = 0;i<10;i++) num[i] = 0;
if(~pos)
num[pos] = d;
}
sum operator +(const sum a)const{
sum ans = sum();
for(int i = 0;i<=9;i++)
ans.num[i] = this->num[i] + a.num[i];
return ans;
}
sum operator *(const int a)const{
sum ans = sum();
for(int i = 0;i<=9;i++)
ans.num[i] = this->num[i] * a;
return ans;
}
sum operator -(const sum a)const{
sum ans = sum();
for(int i = 0;i<=9;i++)
ans.num[i] = this->num[i] - a.num[i];
return ans;
}
};

sum dp[MAXN][MAXN];
ll t[MAXN];
//dp[i][j] -> 后i位,倒数第i位为j,j == 10 代表为先导0

void init(){
scanf("%lld %lld",&a,&b);
t[0] = 1;
for(int i = 1;i<=15;i++)
t[i] = 10*t[i-1];
}

void build(){
for(int j = 0;j<=9;j++)
dp[1][j] = sum(j,1);
for(int i = 2;i<=15;i++){
for(int j = 0;j<=9;j++){
dp[i][j] = sum(j,t[i-1]);
for(int w = 0;w<=9;w++)
dp[i][j] = dp[i][j] + dp[i-1][w];
}
dp[i][10] = sum();
for(int w = 1;w<=10;w++)
dp[i][10] = dp[i][10] + dp[i-1][w];
}
}

sum getnum(ll a){
ll tmp = a;
sum ans = sum(0,1);
if(a == 0) return sum(0,1);
int num[15],cnt = 0;
while(a){
num[++cnt] = a % 10;
a/=10;
}
ans = ans + dp[cnt][10] - dp[cnt][0];
//加上在这一位有前导0,再除去在这一位是0的
for(int i = cnt;i>=1;--i){
for(int j = 0;j<num[i];++j)
ans = ans + dp[i][j];
//加上所有比当前位置小的数的数码
ans = ans + sum(num[i],tmp%t[i-1]+1);
//补上后面的数中不再计算的这一位的数码
}
return ans;
}

void solve(){
sum ans = getnum(b)-getnum(a-1);
for(int i = 0;i<=9;i++){
printf("%lld ",ans.num[i]);
}
printf("\n");
}

int main(){
init();
build();
solve();
return 0;
}