朴素dp

#include <bits/stdc++.h>
#define int long long
using namespace std;
int L, R;
int d[15], dlen; // x 数位分解后 d[dlen]~d[1]
int num[15];     // num[i]: d[i]~d[1] 构成的数
int p10[15];     // p10[i]: 10^i
int dp[15];      // dp[i]：满 i 位数时每个数字的出现次数（包括前导 0，三位数的 0 是 000）
int dp0[15];     // dp0[i]：满 i 位数时 0 的出现次数（不包括前导 0，三位数没有 0）
void init()
{
    p10[0] = 1;
    for (int i = 1; i <= 12; i++)
    {
        p10[i] = p10[i - 1] * 10;
        dp[i] = dp[i - 1] * 10 + p10[i - 1];
        // dp[i] = p10[i] * i / 10; 也可以
    }
    dp0[1] = 1;
    for (int i = 2; i <= 12; i++)
        dp0[i] = dp[i - 1] * 9 + dp0[i - 1]; // 满i-1位数前面补1~9
}
// 计算 0~x 有多少个数字 dig
int cal(int x, int dig)
{
    if (x == 0)
        return dig == 0;
    // d[]
    dlen = 0;
    for (int i = x; i != 0; i /= 10)
        d[++dlen] = i % 10;
    // num[]
    num[0] = 0;
    for (int i = 1; i <= dlen; i++)
        num[i] = num[i - 1] + d[i] * p10[i - 1];
    // cal
    int sum = 0;
    if (dig != 0)
    {
        for (int i = dlen; i >= 1; i--)
        {
            int now = d[i];
            for (int j = 0; j < now; j++)
            {
                sum += dp[i - 1];
                if (j == dig)
                    sum += p10[i - 1];
            }
            if (now == dig)
                sum += num[i - 1] + 1;
        }
    }
    else
    {
        sum += dp0[dlen - 1]; // 最高位填0
        for (int j = 1; j < d[dlen]; j++)
            sum += dp[dlen - 1]; // 最高位填非0
        // 最高位填了 d[dlen] 后看看其他位怎么填
        for (int i = dlen - 1; i >= 1; i--)
        {
            int now = d[i];
            for (int j = 0; j < now; j++)
            {
                sum += dp[i - 1];
                if (j == dig)
                    sum += p10[i - 1];
            }
            if (now == dig)
                sum += num[i - 1] + 1;
        }
    }
    return sum;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    init();
    cin >> L >> R;
    for (int i = 0; i <= 9; i++)
    {
        cout << cal(R, i) - cal(L - 1, i) << " ";
    }
    cout << "\n";
    return 0;
}

记忆化搜索

#include <bits/stdc++.h>
#define int long long
using namespace std;
int L, R;
int dp[15][10];  // limit 和 zero 为假时记忆化搜索 dp[pos][dig]
int d[15], dlen; // d[dlen]~d[1]
int num[15];     // num[i]: d[i]~d[1] 构成的数
int p10[15];     // p10[i]: 10^i
// 做到了第 pos 位，是否顶到了上限，之前是否都填的 0，待统计得数字
int dfs(int pos, bool limit, bool zero, int dig)
{
    if (pos == 0)
        return 0;
    // 算过了没贴边的结果的话就直接返回
    if (!limit && !zero && dp[pos][dig] != -1)
        return dp[pos][dig];
    // 当前这一位的上限
    int up = limit ? d[pos] : 9;
    int sum = 0;                        // 记录方案数
    for (int now = 0; now <= up; now++) // 枚举当前这一位
    {
        if (zero && now == 0)
        {
            if (pos != 1)
                sum += dfs(pos - 1,
                           limit && now == d[pos],
                           zero && now == 0,
                           dig);
            else
                sum += (dig == 0);
        }
        else if (now == dig && limit && now == d[pos])
            sum += num[pos - 1] + 1 +
                   dfs(pos - 1,
                       limit && now == d[pos],
                       zero && now == 0,
                       dig);
        else if (now == dig)
            sum += p10[pos - 1] +
                   dfs(pos - 1,
                       limit && now == d[pos],
                       zero && now == 0,
                       dig);
        else
            sum += dfs(pos - 1,
                       limit && now == d[pos],
                       zero && now == 0,
                       dig);
    }
    // 如果前面没贴边.并且没有前导0，就记忆化一下
    if (!limit && !zero)
        dp[pos][dig] = sum;
    return sum;
}
// 计算 0~x 有多少个数字 dig
int cal(int x, int dig)
{
    if (x == 0)
        return dig == 0;
    // d[]
    dlen = 0;
    for (int i = x; i != 0; i /= 10)
        d[++dlen] = i % 10;
    // num[]
    num[0] = 0;
    for (int i = 1; i <= dlen; i++)
        num[i] = num[i - 1] + d[i] * p10[i - 1];
    // dfs
    return dfs(dlen, true, true, dig);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    p10[0] = 1;
    for (int i = 1; i <= 12; i++)
        p10[i] = p10[i - 1] * 10;
    cin >> L >> R;
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i <= 9; i++)
        cout << cal(R, i) - cal(L - 1, i) << " ";
    cout << "\n";
    return 0;
}