[ZJOI2010] 数字统计
题目
给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。
INPUT
输入文件中仅包含一行两个整数a、b，含义如上所述
OUTPUT
输出文件中包含一行10个整数，分别表示0-9在[a,b]中出现了多少次。
SAMPLE
INPUT
1 99
OUTPUT
9 20 20 20 20 20 20 20 20 20
解题报告
第二道数位$dp$，找着点感觉了？
首先，我们预处理出来从低向高位数第$i$位数，每个数码出现的次数，递推式很简单
$$f[i]=10*f[i-1]+10^{i-1}$$
我们分两部分考虑即可，第$i$位为该数字的数有$10^{i-1}$个，后$i-1$位数该该数字出现的次数为$f[i-1]$，前面的数共有$10$种可能（允许前导0），故$f[i]=10*f[i-1]+10^{i-1}$
然后考虑如何统计答案。
对于低于该数位数的数，我们可以去除前导零，对上式进行变形（具体式子见代码），求和即可
对于位数等于该数位数的数，我们可以逐位枚举统计，利用处理出来的$f$数组和$10^{i}$进行转移即可
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long L;
L a,b,f[],pw[],ans[];
int num[],top;
inline void solve(L x,int flag){
if(!x)return;
top=;L ret(x);
while(x){num[++top]=x%;x/=;}
for(int i=;i<top;++i)
for(int j=;j<=;++j)
ans[j]+=flag*(*f[i-]+(j?pw[i-]:));
for(int i=top;i;--i){
ret-=num[i]*pw[i-];ans[num[i]]+=(ret+)*flag;
for(int j=(i==top);j<num[i];++j)ans[j]+=pw[i-]*flag;
for(int j=;j<=;++j)ans[j]+=f[i-]*(num[i]-(i==top))*flag;
}
}
int main(){
freopen("countzj.in","r",stdin);freopen("countzj.out","w",stdout);
scanf("%lld%lld",&a,&b);
pw[]=;for(int i=;i<=;++i)f[i]=*f[i-]+pw[i-],pw[i]=pw[i-]*;
solve(b,);solve(a-,-);
printf("%lld",ans[]);for(int i=;i<=;++i)printf(" %lld",ans[i]);
}