难度：省选/NOI-

题目描述

        给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。

输入格式

        输入文件中仅包含一行两个整数a、b，含义如上所述。

输出格式

        输出文件中包含一行10个整数，分别表示0-9在[a,b]中出现了多少次。

输入输出样例

Sample input

1 99

Sample output

9 20 20 20 20 20 20 20 20 20

说明

        30%的数据中，$a\leq b\leq 10^6$；
        100%的数据中，$a\leq b\leq 10^{12}$。

题解

        第一篇关于数位DP的文章。
        数位DP，顾名思义是在数位上进行的DP，这类题目通常方程不好列，但时间和空间复杂度比较低。可以说是人类智慧题。其实数位DP也是普通的DP，并不是什么高大上的东西。
        如果我们能够求出1~x的所有数码出现的次数，那么这个问题就解决了。因此下面考虑如何求1~x所有数，0~9的数码出现的次数。
        首先将这个x固定住，让它不参与状态的定义。然后对于这个x，令dp[x][s][y][z]表示x~0的数位，能不能超过原数（用y控制，y取0/1），能不能有前导0（用z控制，z取0/1），数码s的总出现次数。
        下面转移就行了，这里预处理了10的幂，存入bin数组。看下面代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
long long DP(int x, int y, bool isOK, bool isQ, long long p) {//x~0位,y这个数码出现几次,isOK控制是否可以超过，isQ能否有前导0。这里的p是操作数（就是上面的s）
    if (dp[x][y][isOK][isQ] != -1)return dp[x][y][isOK][isQ];//记忆化
    if (x == 0)return !isQ && y == 0 ? 0 : (isOK ? 1 : y <= p % 10);//递推边界
    if (isOK) {//能超过
        if (!isQ && y == 0)//不能有前导0
            return dp[x][y][isOK][isQ] = DP(x - 1, y, true, false, p) + 9ll * DP(x - 1, y, true, true, p);//对这一位取0特判
        return dp[x][y][isOK][isQ] = bin[x] + 10ll * DP(x - 1, y, true, true, p);//否则这一位随便取
    }
    dp[x][y][isOK][isQ] = 0;
    for (int i = 0; i <= p / bin[x] % 10; i++) {//取最高的数位
        if (i < p / bin[x] % 10) {//对于小于最高位的情况
            if (!isQ && y == 0)dp[x][y][isOK][isQ] += DP(x - 1, y, true, i != 0, p);//对首位0特判
            else dp[x][y][isOK][isQ] += (i == y) * bin[x] + DP(x - 1, y, true, true, p);
        } else {//最高位的情况
            if (!isQ && y == 0 && i == 0)dp[x][y][isOK][isQ] += DP(x - 1, y, false, false, p);
            else dp[x][y][isOK][isQ] += (i == y) * (p % bin[x] + 1) + DP(x - 1, y, false, true, p);
        }
    }
    return dp[x][y][isOK][isQ];
}

        读懂这个转移函数就可以了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>

using namespace std;
long long n, m, dp[15][15][2][2], bin[15];
long long ans[10];

long long DP(int x, int y, bool isOK, bool isQ, long long p) {//x~0位,y出现几次,isOK控制是否可以超过，isQ能否有前导0
    if (dp[x][y][isOK][isQ] != -1)return dp[x][y][isOK][isQ];
    if (x == 0)return !isQ && y == 0 ? 0 : (isOK ? 1 : y <= p % 10);
    if (isOK) {
        if (!isQ && y == 0)
            return dp[x][y][isOK][isQ] = DP(x - 1, y, true, false, p) + 9ll * DP(x - 1, y, true, true, p);
        return dp[x][y][isOK][isQ] = bin[x] + 10ll * DP(x - 1, y, true, true, p);
    }
    dp[x][y][isOK][isQ] = 0;
    for (int i = 0; i <= p / bin[x] % 10; i++) {/
        if (i < p / bin[x] % 10) {
            if (!isQ && y == 0)dp[x][y][isOK][isQ] += DP(x - 1, y, true, i != 0, p);
            else dp[x][y][isOK][isQ] += (i == y) * bin[x] + DP(x - 1, y, true, true, p);
        } else {
            if (!isQ && y == 0 && i == 0)dp[x][y][isOK][isQ] += DP(x - 1, y, false, false, p);
            else dp[x][y][isOK][isQ] += (i == y) * (p % bin[x] + 1) + DP(x - 1, y, false, true, p);
        }
    }
    return dp[x][y][isOK][isQ];
}

int main() {
    cin >> n >> m;
    memset(dp, -1, sizeof(dp)), bin[0] = 1;
    for (int i = 1; i <= 15; i++)bin[i] = bin[i - 1] * 10ll;
    for (int i = 0; i < 10; i++)ans[i] += DP(14, i, false, false, m);
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < 10; i++)ans[i] -= DP(14, i, false, false, n - 1);
    for (int i = 0; i < 10; i++)cout << ans[i] << " ";
    return 0;
}