数位DP
Orz iwtwiioi
学习了一下用记忆化搜索来捉题的新姿势……但没学会TAT,再挖个坑(妈蛋难道对我来说数位DP就是个神坑吗……sigh)
//BZOJ 1833
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
typedef long long LL;
LL getint(){
LL v=,sign=; char ch=getchar();
while(ch<''||ch>'') {if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<='') {v=v*+ch-''; ch=getchar();}
return v*=sign;
}
/*******************tamplate********************/ LL f[],c[],a[],p[];
LL dfs(int x,int dig,int front,int line){
if (!x) return ;
if (!front && !line && f[x]!=-) return f[x];
LL last=(line ? a[x] : ), tot=;
F(i,,last){
if (front && i==) tot+=dfs(x-,dig,,line&&i==last);
else if (i==dig){
if (i==last && line) tot+=c[x-]++dfs(x-,dig,,line && i==last);
else tot+=p[x-]+dfs(x-,dig,,line && i==last);
}
else tot+=dfs(x-,dig,,line&& i==last);
}
if (!front && !line) f[x]=tot;
return tot;
}
LL getans(LL x,LL dig){
memset(f,-,sizeof f);
LL t=x; int len=;
while(t) a[++len]=t%,t/=,c[len]=c[len-]+a[len]*p[len-];
return dfs(len,dig,,);
}
int main(){
// freopen("input.txt","r",stdin);
LL a=getint(),b=getint();
p[]=; F(i,,) p[i]=p[i-]*;
rep(i,) printf("%lld ",getans(b,i)-getans(a-,i));
printf("%lld\n",getans(b,)-getans(a-,));
return ;
}