这道题也是道数位dp 因为0有前导0这一说卡了很久 最后发现用所有位数减1~9的位数就okay.....orzczl大爷 其他就跟51nod那道统计1出现次数一样啦
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
LL read(){
LL ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
LL f[][][],w[],cur=,ans1[],ans2[];
void prepare(){
w[]=; for(int i=;i<=;i++) w[i]=w[i-]*;
for(int i=;i<=;i++) f[][i][i]=;
for(int i=;i<=;i++)
for(int j=;j<=;j++)
for(int k=;k<=;k++){
for(int z=;z<=;z++)
f[i][j][k]+=f[i-][z][k];
if(j==k) f[i][j][k]+=w[i];
}
}
void work1(LL n){
int cur=;
if(!n){ans1[]=; return ;}
while(w[cur]>n) cur--;
LL tot=;
for(int i=;i<cur;i++) tot+=(w[i+]-w[i])*i;
tot+=(n-w[cur]+)*cur;
LL v=n/w[cur];
for(int i=;i<=;i++)
for(int j=;j<v;j++)
ans1[i]+=f[cur][j][i];
ans1[v]=ans1[v]+n%w[cur]+;
n=n%w[cur];
for(int i=cur-;i;i--){
v=n/w[i];
for(int j=;j<=;j++)
for(int k=;k<v;k++) ans1[j]+=f[i][k][j];
ans1[v]=ans1[v]+n%w[i]+;
n=n%w[i];
}
//printf("%lld %lld\n",tot,ans1[0]);
for(int i=;i<=;i++) tot-=ans1[i]; ans1[]=tot;
}
void work2(LL n){
int cur=;
if(!n){ans2[]=; return ;}
while(w[cur]>n) cur--;
LL tot=;
for(int i=;i<cur;i++) tot+=(w[i+]-w[i])*i;
tot+=(n-w[cur]+)*cur;
LL v=n/w[cur];
for(int i=;i<=;i++)
for(int j=;j<v;j++)
ans2[i]+=f[cur][j][i];
ans2[v]=ans2[v]+n%w[cur]+;
n=n%w[cur];
for(int i=cur-;i;i--){
v=n/w[i];
for(int j=;j<=;j++)
for(int k=;k<v;k++) ans2[j]+=f[i][k][j];
if(v) ans2[v]=ans2[v]+n%w[i]+;
n=n%w[i];
}
//printf("%lld %lld\n",tot,ans2[0]);
for(int i=;i<=;i++) tot-=ans2[i]; ans2[]=tot;
}
int main()
{
prepare();
work1(read()-); work2(read());
for(int i=;i<=;i++){
printf("%lld",ans2[i]-ans1[i]);
if(i!=) printf(" ");
}
return ;
}