[ZJOI2010]数字计数
显然作差，这个很好理解。
然后就是要求出 $f(x)$ 这个东西。
我们考虑数位 DP。
有一个显然的性质，满 $i$ 位的数字，所有数码出现的次数都是一样的（当然除了前导 0，我们后面再讨论），设这个次数为 $dp(i)$，那么就会有 $dp(i)=10dp(i-1)+10^{i-1}$。
简单来说，第 $i$ 位从 0 到 9 枚举的时候，前面的 $i-1$ 位重复了 10 次相同的变换，那么就要加上 $10dp(i-1)$。
而第 $i$ 位本身又从 0 到 9 变换，当第 $i$ 位是个确定的数字的时候，后面 $i-1$ 位有多少种可能这一数码就会增加多少出现次数，所以要加上 $10^{i-1}$。
然后考虑如何求出 $f(x)$。我们利用 $dp(i)$。
从最高位到最低位捋一波。
比如说，最高位是 $a_1$，最低位是 $a_{len}$。假如这个上届现在这一位是 $a_i$，当这一位为 $[0,a_i-1]$ 的时候后面显然是随便取的，所以每一个数码都出现了 $a_i\times dp(i-1)$ 次。
当这一位取到 $a_i$ 的时候就要小心一点，我们后面的数字只能取到上界。所以说 $a_i$ 这个数码的增加次数只有这一部分。（后面这一部分的数码如何计算我们根本不用管，因为我们后面是会算到的。。。）
然后就是处理前导零问题，假设 1 到 $i$ 都是 0，那么 0 这个数码就要减少 $10^{i-1}$ 次的出现次数。
然后就寄算完了哈哈哈。
时间复杂度 $O(\log n)$。
代码：
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
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=15;
ll l,r;
ll ans1[N+5],ans2[N+5],dp[N+5],pw[N+5],a[N+5];
inline void Solve(ll x,ll *ans) {
ll tmp=x,len=0;
while(x) {a[++len]=x%10;x/=10;}
for(ll i=len;i>=1;i--) {
for(ll j=0;j<=9;j++) ans[j]+=dp[i-1]*a[i];
for(ll j=0;j<a[i];j++) ans[j]+=pw[i-1];
tmp-=pw[i-1]*a[i];ans[a[i]]+=tmp+1;ans[0]-=pw[i-1];
}
}
inline void Init() {
pw[0]=1ll;
for(ll i=1;i<=13;i++) {dp[i]=dp[i-1]*10ll+pw[i-1];pw[i]=pw[i-1]*10ll;}
}
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
inline void writes(ll x) {write(x);putchar(32);}
int main() {
l=read();r=read();
Init();
Solve(r,ans1);Solve(l-1,ans2);
for(ll i=0;i<=9;i++) {writes(ans1[i]-ans2[i]);}
return 0;
}
|