\(Description\)
题面
给定两个数\(a,b\)，求\([a,b]\)内，数码\(0-9\)出现的次数
\(Solution\)
话说这道题就是P1554梦中的统计的强化版，记得这道题刚学\(OI\)的时候做过（指梦中的统计）。对于这道题而言，朴素做法只有\(30pts\)，面对庞大的数据范围只能使用数位\(DP\)了
这题难点在于\(1.\)设计状态,\(2.处理两个边界\)
考虑设计状态为\(dp[i][j][k]\)表示当前考虑第\(i\)位(编号方式从低位到高位)，当前位置是\(j\)，对于第\(i\)位是\(j\)的所有数中，\(k\)的出现次数
转移过程是\(dp[i][j][k]=\sum\limits_{g=1}^9dp[i-1][g][k]\)，因为一位数后面接的有可能是\(0-9\)。需要注意的是\(j=k\)时需要加上这一位的答案，仅考虑到第\(i\)位，那么第\(i\)位的数会出现\(10^{i-1}\)次，因此答案\(+10^{i-1}\)
上面的转移过程是\(O(10^3logn)\)左右的，但可以更快（其实也不需要），每次枚举完一位记录一下\(\sum\limits_{g=1}^9dp[i-1][g][k]\)即可。
\(O(10^2logn)\)完全没问题
void pre()
{
pow[0]=1;
for(re int i=1;i<=12;++i) pow[i]=pow[i-1]*10;
for(re int i=0;i<=9;++i) dp[1][i][i]=1,sums[i]=1;
for(re int i=2;i<=12;++i)
{
for(re int j=0;j<=9;++j)
for(re int k=0;k<=9;++k)
{
dp[i][j][k]+=sums[k];
if(j==k) dp[i][j][k]+=pow[i-1];
}
for(re int j=0;j<=9;++j) sums[j]=0;//一开始写的sum[j]=0，挂掉了
for(re int j=0;j<=9;++j)
for(re int k=0;k<=9;++k)
sums[k]+=dp[i][j][k];
}
}计数过程处理前导零的常用思路：先处理所有\(i(i<len)\)位数的答案，这个在上一篇说过
计数过程比较重要的两个边界，一个是最终边界注意提前\(+1\)，这样可以考虑最后一位，还有一个是：每次逼近完一位需要先确定这一位（让他和边界的这一位相等），再考虑下一位，注意确定这一位的过程要考虑对答案的影响，因为之前逼近过程没有计算，这里很容易出错
举个例子：\(12xxx\)，第二高位会逼近到\(1\)，直接到下一位，但是\(2\)忽略了，因此要加入\(2\)的答案，也就是\(12xxx%1000+1\)
更多细节看代码吧
\(Code\)
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define re register
#define ll long long
using namespace std;
inline ll read()
{
ll x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll a,b,pow[20],dp[20][12][12];//dp[i][j][k]表示当前是第i位，当前位是j，后面任意贡献的k有多少个
ll tmp[20],ans[20],sums[20],cnt=0;
void pre()
{
pow[0]=1;
for(re int i=1;i<=12;++i) pow[i]=pow[i-1]*10;
for(re int i=0;i<=9;++i) dp[1][i][i]=1,sums[i]=1;
for(re int i=2;i<=12;++i)
{
for(re int j=0;j<=9;++j)
for(re int k=0;k<=9;++k)
{
dp[i][j][k]+=sums[k];
if(j==k) dp[i][j][k]+=pow[i-1];
}
for(re int j=0;j<=9;++j) sums[j]=0;//一开始写的sum[j]=0，挂掉了
for(re int j=0;j<=9;++j)
for(re int k=0;k<=9;++k)
sums[k]+=dp[i][j][k];//降低一点常数
}
}
void ask(ll x)
{
memset(tmp,0,sizeof(tmp));
cnt=0;
if(x==0)
{
tmp[0]=1;
return;
}
ll t=x,now=0,last;
while(t){t/=10;cnt++;}
for(re int i=1;i<=cnt-1;++i)//处理前导零
for(re int j=1;j<=9;++j)
for(re int k=0;k<=9;++k)
tmp[k]+=dp[i][j][k];
now=x/pow[cnt-1];
for(re int j=1;j<now;++j)
for(re int k=0;k<=9;++k)
tmp[k]+=dp[cnt][j][k];
last=now;
x%=pow[cnt-1];
for(re int i=cnt-1;i>=1;--i)
{
tmp[last]+=x;//这里要特别判断边界，到了12xxx的第一个x要把前面2统计上，个数就是12xxx%1000+1
//又因为我们边界预先加了一，所以个数就是12xxx%1000，比如199会处理成200，如果计算2后有多少数会计算1个，但实际这个数是不存在的，因此不用%后+1
now=x/pow[i-1];
for(re int j=0;j<now;++j)
for(re int k=0;k<=9;++k)
tmp[k]+=dp[i][j][k];
x%=pow[i-1];
last=now;//更新
}
}
int main()
{
a=read(),b=read();
pre();
ask(b+1);
for(re int i=0;i<=9;++i) ans[i]=tmp[i];
ask(a);
for(re int i=0;i<=9;++i)
{
ans[i]-=tmp[i];
printf("%lld ",ans[i]);
}
return 0;
}