题目链接：传送门

题面

题目描述
给定两个正整数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大水题
由于a,b最大可取到$10^{12}$，复杂度O(n)及以上的算法显然不适用。
又因为要求的值是数字出现次数，所以考虑使用数位DP。

按照数位DP基本思路，容易得出子状态dp[i][j]表示第i位时，已经有j个当前数字时共有多少当前数字。

使用记忆化搜索，传参如下：

now :	当前位数，从最高位搜到1，当now==0时直接返回
digit :	当前正在求的数字（0～9）
sum :	当前digit出现次数
limit :	当前是否是可以填的数的最大值
zero :	有无前导0

初写数位DP容易错的点：若!limit &&!zero，才可以更新（返回）dp[now][sum]
其他按照数位DP模板敲基本就可以，具体见代码。

代码

#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<math.h>
#define re register int
using namespace std;
typedef long long ll;
ll read() {
    register ll x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {
        if(ch=='-')	f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') {
        x=10*x+ch-'0';
        ch=getchar();
    }
    return x*f;
}
const int Size=15;
ll a[Size],dp[Size][Size];
//dp[i][j]:第i位，已经有j个当前数字时共有多少当前数字 
ll dfs(int now,int digit,ll sum,bool limit,bool zero) {
	//now==0说明所有位数都搜过，则返回当前digit出现次数sum 
    if(!now)	return sum;
	//注意此处的判断条件 
    if(!limit && !zero && dp[now][sum]!=-1)	return dp[now][sum];
    ll up=9,ans=0;
    if(limit)	up=a[now];
	//搜索下一位时，注意sum要在无前导0时更新 
    for(int i=0; i<=up; i++)
        ans+=dfs(now-1,digit,sum+((!zero || i) && i==digit),limit && i==a[now],zero && !i);
    if(!limit && !zero)	dp[now][sum]=ans;
    return ans;
}
ll DP(ll x,int digit) {
	//注意本题中每次DP都要memset一次 
    memset(dp,-1,sizeof(dp));
    int cnt=0;
	//把x拆分成cnt个位 
    while(x) {
        a[++cnt]=x%10;
        x/=10;
    }
    return dfs(cnt,digit,0,true,true);
}
int main() {
    ll a=read();
    ll b=read();
    //把[a,b]转化为[0,b]-[0,a-1] 
    for(re i=0; i<=9; i++)	printf("%lld ",DP(b,i)-DP(a-1,i));
    return 0;
}