1833. [ZJOI2010]数字计数【数位DP】

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)$
注意判断一下前导零不计算入总结果的情况

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #define LL long long

 using namespace std;

 LL ten[]={,,1e2,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12,1e13};

 LL a[],ans[],sum;

 LL Dfs(LL pos,LL zero,LL limit,LL k)

 {

     if (pos==) return ;

     if (!limit && !zero)

     {

         sum+=ten[pos]/*pos*k;

         return ten[pos];

     }

     else

     {

         LL up=limit?a[pos]:,cnt=;

         for (LL i=;i<=up;++i)

         {

             LL t=Dfs(pos-,zero && i==,limit && i==up,k);

             if (zero && i==) continue;

             ans[i]+=t*k;

             cnt+=t*k;

         }

         return cnt*k;

     }

 }

 void Solve(LL x,LL k)

 {

     LL pos=;

     while (x)

     {

         a[++pos]=x%;

         x/=;

     }

     Dfs(pos,true,true,k);

 }

 int main()

 {

     LL x,y;

     scanf("%lld%lld",&x,&y);

     Solve(y,);

     Solve(x-,-);

     for (LL i=;i<=;++i)

         printf("%lld ",ans[i]+sum);

     printf("%lld",ans[]+sum);

 }

巴特西