Description

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

Input

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

Output

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

Sample Input

1 99

Sample Output

9 20 20 20 20 20 20 20 20 20

HINT

30%的数据中，a<=b<=10^6；

100%的数据中，a<=b<=10^12。

 

数位DP （废话）

我们可以知道，如果某一位开始没有限制的话，对每一位的$ans$是相同的且可以$O(1)$计算出来的

不妨这么考虑，假设有三位是没有限制的，那么一共有$10^3$种情况

每一位出现数字$x$的概率为$1/10$，那么三位加起来就是$3/10$

则数字$x$出现的次数为$10^3 * (3/10)$

注意判断一下前导零不计算入总结果的情况

 

1 #include
     
       2 #include
      
        3 #include
       
         4 #define LL long long 5 using namespace std; 6 LL ten[15]={
   1,10,1e2,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12,1e13}; 7 LL a[20],ans[10],sum; 8 LL Dfs(LL pos,LL zero,LL limit,LL k) 9 {10     if (pos==0) return 1;11     if (!limit && !zero)12     {13         sum+=ten[pos]/10*pos*k;14         return ten[pos];15     }16     else17     {18         LL up=limit?a[pos]:9,cnt=0;19         for (LL i=0;i<=up;++i)20         {21             LL t=Dfs(pos-1,zero && i==0,limit && i==up,k);22             if (zero && i==0) continue;23             ans[i]+=t*k;24             cnt+=t*k;25         }26         return cnt*k;27     }28 }29 30 void Solve(LL x,LL k)31 {32     LL pos=0;33     while (x)34     {35         a[++pos]=x%10;36         x/=10;37     }38     Dfs(pos,true,true,k);39 }40 41 int main()42 {43     LL x,y;44     scanf("%lld%lld",&x,&y);45     Solve(y,1); 46     Solve(x-1,-1);47     for (LL i=0;i<=8;++i)48         printf("%lld ",ans[i]+sum);49     printf("%lld",ans[9]+sum);50 }