https://vjudge.net/problem/UVA-1640
题意：统计区间[l,r]中0——9的出现次数
数位DP
注意删除前导0
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int ans[],a[],dp[][],bit[];
int dfs(int dep,int ty,bool lim,int k)
{
if(!dep) return ty;
if(!lim && dp[dep][ty]!=-) return dp[dep][ty];
int ans=,up= lim ? a[dep] : ;
for(int i=;i<=up;i++)
{
if(i==k) ans+=dfs(dep-,ty+,lim && i==up,k);
else ans+=dfs(dep-,ty,lim && i==up,k);
}
if(!lim) dp[dep][ty]=ans;
return ans;
}
int main()
{
int l,r;
bit[]=;
for(int i=;i<=;i++) bit[i]=bit[i-]*;
while(scanf("%d%d",&l,&r)!=EOF)
{
if(!l) return ;
if(l>r) swap(l,r);
memset(ans,,sizeof(ans));
a[]=;
while(r) a[++a[]]=r%,r/=;
for(int i=;i<=;i++)
{
memset(dp,-,sizeof(dp));
ans[i]=dfs(a[],,,i);
}
l--; if(!l) ans[]--;
int tmp=a[];
a[]=;
while(l) a[++a[]]=l%,l/=;
for(int i=;i<=;i++)
{
memset(dp,-,sizeof(dp));
ans[i]-=dfs(a[],,,i);
}
while(tmp!=a[]) ans[]-=bit[--tmp];
printf("%d",ans[]);
for(int i=;i<=;i++) printf(" %d",ans[i]);
printf("\n");
}
}
