题解：P2602 [ZJOI2010] 数字计数

这个题一眼小学奥数，为什么要用数位 dp？

注意到：

• 百位数字一定时十位数字 出现次数为 ；
• 十位数字一定时个位数字 出现次数为 ；
• 则有

所以可以用 表示权重倍率，然后用相同的方法处理数字每一位，最后结果用 进行放缩即可。

注意到相关限制来自三个原数字位置：，也就是高位、当前和低位上的数字。设考虑在当前位置上填入数字 ，有以下限制：

• if (d < cur)，则可以随便填，对于更高位上可能数字 ，都有 可以选择，而对应的以 为最高位的个数又是 ，则有 ans[d] += (pre + 1) * scale；
• if (d == cur)，那么在更高位可能数字 的时候，包含当前位的较低位数字个数就变成了 个（包含后缀零），则有 ans[d] += pre * scale + suf + 1；
• if (d > cur)，那么更高位数字 而较低位数字也不会有限制，则有 ans[d] += pre * scale；

关于前导零，显然只有最高位会担心这个事情，且此时后缀数字随意填充，所以减去其对应的 即可。

基于此，我方代码如下：

#include<bits/stdc++.h>
#define LL long long

using namespace std;

LL n, m;
LL ans1[10], ans2[10];

inline void calc(LL num, LL *ans) {
    if (num <= 0)
        return;
    for (LL scale = 1; scale <= num; scale *= 10) {
        LL cur = (num / scale) % 10;
        LL pre = num / (scale * 10);
        LL suf = num % scale;
        for (int d = 0; d <= 9; ++d) {
            if (d < cur)
                ans[d] += (pre + 1) * scale;
            else if (d == cur)
                ans[d] += pre * scale + suf + 1;
            else
                ans[d] += pre * scale;
            if (d == 0)
                ans[d] -= scale;
        }
    }
}

int main() {
    scanf("%lld%lld", &n, &m);
    calc(m, ans2);
    calc(n - 1, ans1);
    for (int i = 0; i <= 9; ++i)
        printf("%lld ", ans2[i] - ans1[i]);
    return 0;
}