P2602 [ZJOI2010]数字计数[数位dp]

题目描述

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

输入输出格式

输入格式:

输入文件中仅包含一行两个整数 $a$、$b$,含义如上所述。

输出格式:

输出文件中包含一行10个整数,分别表示0-9在[a,b]中出现了多少次。

输入输出样例

输入样例#1:

1
1 99

输出样例#1:

1
9 20 20 20 20 20 20 20 20 20

说明

30%的数据中,$a\le b\le 10^6$;

100%的数据中,$ a \le b \le 10^{12}$。

题解

我是一位一位统的,然后前导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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int qmax(int &x,int y) {if (x<y) x=y;}
int qmin(int &x,int y) {if (x>y) x=y;}
ll read()
{
char s;
ll k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
if(s==EOF)exit(0);if(s=='-')base=-1,s=getchar();
while(isdigit(s)){k=k*10+(s^'0');s=getchar();}
return k*base;
}
void write(int x)
{
if(x<0){putchar('-');write(-x);}
else{if(x/10)write(x/10);putchar(x%10+'0');}
}
ll a,b,A[20],p,B;
ll dp[20],sum[20],ans[2][20];
ll dfs(int pos,int flag,int k,int f2)//k:统的数 f2:前导0
{
if (pos==0&&f2==0&&k==0) return 1;
if (pos==0) return 0;
if (flag&&dp[pos]!=0&&((k!=0)||(k==0&&f2!=0))) return dp[pos];//没有限制并且没有前导0
ll ans1=0;
if (!flag)//有限制
{
for (int i=0;i<A[pos];i++)
{
if (i==k&&(k!=0||f2==1)) ans1+=sum[pos];
ans1+=dfs(pos-1,1,k,i==0?f2:1);
}
if (A[pos]==k&&(k!=0||f2==1)) ans1+=(B%sum[pos]+1);
ans1+=dfs(pos-1,0,k,A[pos]==0?f2:1);
} else//没限制
{
for (int i=0;i<=9;i++)//枚举当前位
{
if (i==k&&(k!=0||f2==1)) ans1+=sum[pos];
ans1+=dfs(pos-1,1,k,i==0?f2:1);
}
}
if (flag&&((k!=0)||(k==0&&f2!=0))) dp[pos]=ans1;
return ans1;
}
void qans(ll x,int bj)
{
if (x==0) {ans[bj][0]++;return;};
B=x;
ll X=x;memset(A,0,sizeof(A));p=0;
while (X) A[++p]=X%10,X/=10;
for (int I=0;I<=9;I++) ans[bj][I]+=dfs(p+1,0,I,0);
}
int main()
{
sum[1]=1;
for (int i=2;i<=18;i++) sum[i]=sum[i-1]*10;
a=read();b=read();
qans(a-1,0);qans(b,1);
for (int i=0;i<=9;i++) printf("%lld ",ans[1][i]-ans[0][i]);
return 0;
}