题目描述
给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。
输入输出格式
输入格式：
输入文件中仅包含一行两个整数a、b，含义如上所述。
输出格式：
输出文件中包含一行10个整数，分别表示0-9在[a,b]中出现了多少次。
输入输出样例
输入样例#1：
1 99
输出样例#1：
9 20 20 20 20 20 20 20 20 20
说明
30%的数据中，a<=b<=10^6；
100%的数据中，a<=b<=10^12。
数位DP
#include#include #include #include using namespace std;int a[14];long long bit[14],dp[14][14],ans[10];long long dfs(int dep,int ty,bool lim,int k){ if(!dep) return ty; if(!lim && dp[dep][ty]!=-1) return dp[dep][ty]; long long ans=0; int up= lim ? a[dep] : 9; for(int i=0;i<=up;i++) { if(i==k) ans+=dfs(dep-1,ty+1,lim && i==up,k); else ans+=dfs(dep-1,ty,lim && i==up,k); } if(!lim) dp[dep][ty]=ans; return ans;}int main(){ long long l,r; bit[1]=10; for(int i=2;i<=13;i++) bit[i]=bit[i-1]*10; scanf("%lld%lld",&l,&r); while(r) a[++a[0]]=r%10,r/=10; for(int i=0;i<=9;i++) { memset(dp,-1,sizeof(dp)); ans[i]=dfs(a[0],0,1,i); } l--; if(!l) ans[0]--; int tmp=a[0]; a[0]=0; while(l) a[++a[0]]=l%10,l/=10; for(int i=0;i<=9;i++) { memset(dp,-1,sizeof(dp)); ans[i]-=dfs(a[0],0,1,i); } while(tmp!=a[0]) ans[0]-=bit[--tmp]; printf("%lld",ans[0]); for(int i=1;i<=9;i++) printf(" %lld",ans[i]);}