【题目链接】
http://www.lydsy.com/JudgeOnline/problem.php?id=1833
【题意】
统计[a,b]区间内各数位出现的次数。
【思路】
设f[i][j][k]表示i位数，最高位为j，数位k出现的次数，则有递推式：
f[i][j][k]=sigma{ f[i-1][l][k] ,0<=l<=9 } + 10^(i-1)
第一项统计的是i-1位数中k的出现次数，后一项统计的是最高位k的出现数目。
将查询差分，对于一个数，先统计长度不超过len的，再统计长度=len但最高位比a[len]小的，再统计长度为len且最高位为a[len]的。
注意最后一项的统计，假设n为4321，我们要统计的就是:
4000..4299
4300..4319
4320..4321
假设我们要统计4000..4299，则有;
ans[k]+=f[3][3][k]
ans[4]+=321+1
【代码】
#include<cstdio>
#include<cstring>
#include<iostream>
#define FOR(a,b,c) for(int a=b;a<=c;a++)
using namespace std; typedef long long ll;
const int N = ; struct Node{
ll a[N];
Node() {
memset(a,,sizeof(a));
}
ll& operator[] (const int& x) {
return a[x];
}
};
Node operator + (const Node& x,const Node& y) {
Node tmp;
FOR(i,,) tmp.a[i]=x.a[i]+y.a[i];
return tmp;
} int len,a[N];
ll e[N]; Node f[N][N]; void init(ll n)
{
len=;
while(n) {
a[++len]=n%;
n/=;
}
FOR(i,,) f[][i][i]=;
FOR(i,,) FOR(j,,) {
FOR(k,,)
f[i][j]=f[i][j]+f[i-][k];
f[i][j][j]+=e[i-];
}
}
Node calc(ll n)
{
Node ans;
if(!n) return ans;
memset(f,,sizeof(f));
init(n);
FOR(i,,len-) FOR(j,,)
ans=ans+f[i][j];
FOR(i,,a[len]-) ans=ans+f[len][i];
n%=e[len-];
ans[a[len]]+=n+;
for(int i=len-;i;i--) {
for(int j=;j<a[i];j++) ans=ans+f[i][j];
n%=e[i-];
ans[a[i]]+=n+;
}
return ans;
} int main()
{
e[]=;
FOR(i,,) e[i]=e[i-]*10ll;
ll x,y;
scanf("%lld%lld",&x,&y);
Node ans1=calc(y) , ans2=calc(x-);
FOR(i,,) printf("%lld ",ans1[i]-ans2[i]);
printf("%lld\n",ans1[]-ans2[]);
return ;
}