1 #include<cstdio> 2 #include<iostream> 3 #define ll long long 4 using namespace std; 5 struct data 6 { 7 ll s[10]; 8 }a[15][10],sum1,sum2; 9 ll f[18],l,r; 10 data operator +(data a1,data a2) 11 { 12 data t; 13 for(int i=0;i<=9;i++) 14 t.s[i]=a1.s[i]+a2.s[i]; 15 return t; 16 } 17 data suan(ll r) 18 { 19 int k; 20 data t; 21 for(int i=0;i<=9;i++) 22 t.s[i]=0; 23 if(!r) 24 { 25 t.s[0]=1; 26 return t; 27 } 28 for(k=15;f[k]>r;k--); 29 for(int i=1;i<k;i++) 30 for(int j=1;j<=9;j++) 31 t=t+a[i][j]; 32 t.s[0]++; 33 ll s12=r/f[k]; 34 for(int i=1;i<s12;i++) 35 t=t+a[k][i]; 36 ll s11=r%f[k]; 37 t.s[s12]+=s11+1; 38 for(k--;k;k--) 39 { 40 s12=s11/f[k]; 41 for(int i=0;i<s12;i++) 42 t=t+a[k][i]; 43 s11%=f[k]; 44 t.s[s12]+=s11+1; 45 } 46 return t; 47 } 48 int main() 49 { 50 scanf("%lld%lld",&l,&r); 51 f[1]=1; 52 for(int i=2;i<=15;i++) 53 f[i]=f[i-1]*10; 54 for(int i=0;i<=9;i++) 55 a[1][i].s[i]=1; 56 for(int i=2;i<=12;i++) 57 for(int j=0;j<=9;j++) 58 for(int k=0;k<=9;k++) 59 { 60 a[i][k]=a[i][k]+a[i-1][j]; 61 a[i][k].s[k]+=f[i-1]; 62 } 63 sum1=suan(r); 64 sum2=suan(l-1); 65 for(int i=0;i<9;i++) 66 printf("%lld ",sum1.s[i]-sum2.s[i]); 67 printf("%lld ",sum1.s[9]-sum2.s[9]); 68 return 0; 69 }
数位DP，先预处理，a[i][j]代表有i位，最高位为j的各数字和。