[ZJOI2010] 数字计数

#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;
}