题目的主要信息：

• 求在$[a,b][a,b]$中的所有十进制整数中，数字0-9各出现了多少次
• 30%的数据中，，100%的数据中，

具体做法：

我们设$dp[i][j][k]dp[i][j][k]$表示长度为i，开头为j的数中k的个数，一开始就推算dp数组中每个元素的值，可以枚举所有长度为$ii$的数字中首位和第二位的数字，有$dp[i][j][z]+=dp[i-1][k][z]dp[i][j][z]\; +=\; dp[i\; -\; 1][k][z]$，其中$ii$为数字位数，$jj$为开头的数字，$kk$为上一个长度开头的数字，$zz$为当前要统计的数码。

然后我们找到1到b的答案减去1到a-1答案，在找的时候分开统计答案，对于位数小于当前数的直接全部加上，剩余的拆分统计。

#include<iostream>
#include<vector>
#include<string.h>
using namespace std;

const int maxn = 15;  //最大数字不超过12位
long long dp[maxn][maxn][maxn]; //十进制数中长度为i，开头为j的数中k的个数
long long bin[maxn]; //i位中所有首位为i的数的个数
long long res[maxn]; //记录0~9个数
int d[maxn];
 
void init(){  //递推计算出每个整数
    bin[1] = 1; //1位首位为1只有1个
    for(int i = 2; i <= 13; i++) //后续都是前一个的10倍
        bin[i] = bin[i - 1] * 10;
    for(int i = 0; i <= 9; i++) //长度为1，以i开头中i的个数都是1
        dp[1][i][i]=1;
    for(int i = 2; i <= 13; i++)
        for(int j = 0; j <= 9; j++)
            for(int z = 0; z <= 9; z++){
                for(int k = 0; k <= 9; k++)
                    dp[i][j][z] += dp[i - 1][k][z]; //累加前面的
                dp[i][z][z] += bin[i - 1];
            }
}
 
void solve(long long x,int flag){ //计算1到x的所有数码出现次数
    int dnum = 0;  //记录当前数的位数
    long long y = x;
    memset(d, 0, sizeof(d));
    while(y){  //连除法计算当前x的位数
        d[++dnum] = y % 10; 
        y /= 10;
    }
    for(int i = 1; i <= dnum - 1; i++)//先计算位数小于当前数的位数
        for(int j = 1; j <= 9; j++)
            for(int k = 0; k <= 9; k++)
                res[k] += (dp[i][j][k] * flag); //累加，flag为1加，-1为减
    int temp = dnum;
    while(temp){//再计算位数等于当前数的位数
        for(int i = 0; i < d[temp]; i++){
            if(!i && temp == dnum)
                continue;//不能重复计算
            for(int j = 0; j <= 9; j++)
                res[j] += (dp[temp][i][j] * flag);
        }
        res[d[temp]] += (x % bin[temp] + 1) * flag;
        temp--;
    }
}
 
int main(){   
    init();
    long long a, b;
    cin >> a >> b;
    solve(b, 1); //计算1到b的所有数码次数
    solve(a - 1, -1);  //减去1到a-1的所有数码出现次数
    for(int i = 0; i <= 9; i++) //输出
        cout << res[i] << " ";
    cout << endl;
    return 0;
}

复杂度分析：

• 时间复杂度：$O(1)O(1)$，数字位数最多不超过12位，因此上述循环都是13和10的常数级循环
• 空间复杂度：$O(1)O(1)$，相对于数字$max(a,b)max(a,b)$，空间也属于常数级