题目描述
给定两个正整数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。
Solution：
本题数位DP板子题。
常规套路，对于每个数码的情况，处理的方法都是相同的，所以我们可以枚举当前求的数码，并定义状态$f[i][j]$表示到了第$i$位有$j$个当前数码时往后会出现当前数码的个数。
转移就常规枚举当前位的值，然后统计个数咯，由于本题不能有前导零，稍微处理下限制条件就ok了。
代码：
/*Code by 520 -- 9.16*/ #include<bits/stdc++.h> #define il inline #define ll long long #define RE register #define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++) #define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--) using namespace std; int num[15],top,dig; ll n,m,f[15][15]; ll dfs(int pos,int lead,int limit,ll sum){ if(!pos) return sum; if(!limit&&lead&&f[pos][sum]!=-1) return f[pos][sum]; ll tp=0; For(i,0,limit?num[pos]:9) tp+=dfs(pos-1,i||lead,i==num[pos]&&limit,sum+((i||lead)&&(i==dig))); if(!limit&&lead) f[pos][sum]=tp; return tp; } il ll solve(ll x){ memset(f,-1,sizeof(f)); top=0; while(x) num[++top]=x%10,x/=10; return dfs(top,0,1,0); } int main(){ cin>>n>>m; while(dig<10) cout<<solve(m)-solve(n-1)<<' ',dig++; return 0; }