给出一个跟大部分题解不一样的做法,更加类似于算法提高课中数位DP两个的步骤：初始化、求解。

初始化

设 $f[i,j,k]$ 表示总共有 $i$ 位,且最高位为 $j$ 的所有数字中数字 $k$ 出现的次数,那么容易得出
$f[i,j,k]=\sum_{x=0}^{9} f[i-1,x,k]$
特别地,当 $j=k$ 时,需要再加上最高位出现的次数,即 $10^{i-1}$

求解

发现前导0对答案有影响,故有前导0的部分不能按照一般方法直接算出,这里将全集分成三种：

1. 位数小于n且无前导0的数
2. 位数等于n,最高位小于n且无前导0的数
3. 位数等于n,且最高位等于n的数

对于上述第一、二种情况,从 $1$ 到 $n$的位数$-1$ 循环位数 $i$, 从 $1$ 到 $9$ 循环最高位 $j$, res += f[i][j][k] 即可.
对于第三种情况,这时已经没有前导0的干扰了,便按照按位分类讨论的方式,从高到低循环位数 $i$,再从 $0$ 到 $a_i-1$ 循环最高位 $j$, res += f[i][j][k];此外,由于每次枚举最高位时都没有枚举到 $a_i$,所以每次还要特判一下从最高位开始到上一位结束是否有当前正在统计的数字,若有再加上其出现的次数:$n$的最高位 × $10^{i-1}$.

注意,上述求解方式从头到尾都没能统计n自己各位数字出现的次数,范围为 $[0,n)$

代码

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 15;
typedef long long ll;
ll l, r;
ll f[N][N][N];

ll quick_pow(ll a, ll b){  //快速幂求10的次方
    ll res = 1;
    while (b){
        if (b & 1)
            res *= a;
        b >>= 1;
        a *= a;
    }
    return res;
}

void init(){  //预处理f[i,j,k]
    for (int i = 0; i <= 9; i ++)  //边界
        f[1][i][i] = 1;

    for (int i = 2; i < N; i ++)  
        for (int j = 0; j <= 9; j ++){
            for (int k = 0; k <= 9; k ++)
                for (int h = 0; h <= 9; h ++)
                    f[i][j][h] += f[i - 1][k][h];
            f[i][j][j] += quick_pow(10, i - 1);
        }
}

ll dp(ll n, int a){  //a表示当前统计个数的数字
    if (!n) return 0;

    vector <int> num;
    while (n) num.push_back(n % 10), n /= 10;
    ll res = 0, len = num.size() - 1;

    for (int i = 0; i < len; i ++)  //情况1
        for (int j = 1; j <= 9; j ++)
            res += f[i + 1][j][a];

    for (int i = 1; i < num[len]; i ++)  //情况2
        res += f[len + 1][i][a];

    for (int i = len - 1; i >= 0; i --){  //情况3
        for (int j = 0; j < num[i]; j ++)
            res += f[i + 1][j][a];
        for (int j = len; j > i; j --)
            if (num[j] == a)
                res += num[i] * quick_pow(10, i);
    }
    return res;     

}

int main(){
    init();
    while (cin >> l >> r && l && r){
        if (l > r) swap(l, r);  //坑点
        for (int i = 0; i <= 9; i ++)
            cout << dp(r + 1, i) - dp(l, i) << " ";  //范围为[0,n)
        cout << endl;
    }
    return 0;
}