0x5D 数位统计 DP

数位统计DP是与数字相关的一类计数问题。在这类题目中，一般给定一些限制条件，求满足限制条件的第 $K$ 小的数是多少，或者求在区间 $[L,R]$ 内有多少个满足限制条件的数。解决方法与上一节的最后一道例题“A Decorative Fence”类似，先用动态规划进行预处理，再基于拼凑思想，用“试填法”求出最终的答案。

【例题】启示录 FOJ3208

古代人认为666是属于魔鬼的数。不但如此，只要某数字的十进制表示中有三个连续的6，古代人也认为这个是魔鬼的数，比如666,1666,2666,3666,6663,16666,6660666等，统统是魔鬼的数。古代典籍中经常用“第 $X$ 小的魔鬼的数”来指代这些数，这给研究人员带来了极大的不便。为了帮助他们，你需要写一个程序，输入 $X$ ，输出对应的魔鬼数。 $X\leq 5*10^{7}$ ，每个测试点包含不超过1000组数据。

设 $F[i,3]$ 表示由 $i$ 位数字构成的魔鬼数有多少个， $F[i,j] (0 \leq j \leq 2)$ 表示由 $i$ 位数字构成的、开头已经有连续 $j$ 个6的非魔鬼数有多少个。注意，在计算 $F$ 时，我们允许前导0的存在。

考虑第 $i$ 位（最高位）是什么数字，容易得到状态转移方程：

动态规划完成后，我们先通过 $F[i,3]$ 确定第 $X$ 小的魔鬼数的位数。然后按照“试填法”的思想，从左到右依次考虑每个数位，同时记录当前末尾已经有连续的几个6。

从小到大枚举当前数位填什么数字，通过预处理的 $F$ 数组可以直接计算出后边的数位有多少种填法可以得到魔鬼数，与 $X$ 比较即可。详细步骤请看参考程序：

long long f[21][4];  
int t, n, m;  
void prework() {  
    f[0][0] = 1;  
    for (int i = 0; i < 20; i++) {  
        for (int j = 0; j < 3; j++) {  
            f[i + 1][j + 1] += f[i][j];  
            f[i + 1][0] += f[i][j] * 9;  
        }  
        f[i + 1][3] += f[i][3] * 10;  
    }  
}  
int main() {  
    prework();  
    cin >> t; // 数据组数  
    while (t--) {  
        scanf("%d", &n); // 题目中的 X  
        // 第 n 个魔鬼数有 m 位  
        for (m = 3; f[m][3] < n; m++) {  
            // 试填第 i 位，末尾已有 k 个 6（k = 3 也表示已经是魔鬼数）  
            for (int i = m, k = 0; i; i--) {  
                // 从小到大枚举第 i 位填的数字 j  
                for (int j = 0; j <= 9; j++) {  
                    // 求出后边的 i-1 位有多少种填法能让整个数是魔鬼数  
                    long long cnt = f[i - 1][3];  
                    if (j == 6 || k == 3)  
                        for (int l = max(3 - k - (j == 6), 0); l < 3; l++) cnt += f[i - 1][l];  
                    // 如果 cnt 比 n 小，说明第 n 个魔鬼数的第 i 位应该比 j 更大  
                    if (cnt < n) {  
                        n -= cnt;  
        }  
        // 否则，第 i 位就应该是 j  
        else {  
            if (k < 3) {  
                if (j == 6) k++; else k = 0;  
            }  
        }

} printf("%d",j); break; } } cout << endl; 1

【例题】月之谜 BZOJ1799

如果一个十进制数能够被它的各位数字之和整除，则称这个数为“月之数”。给定整数 $L$ 和 $R$ ，你需要计算闭区间 $[L, R]$ 中有多少个月之数。 $1 \leq L, R < 2^{31}$ ，每个测试点包含不超过3000组数据。

设 $F[i,j,k,l]$ 表示由 $i$ 位数字构成、各位数字之和是 $j$ 、对 $k$ 取模余数是 $l$ 的数有多少个。在计算 $F$ 时，允许前导0的存在。枚举第 $i$ 位的数字 $p$ ，得到状态转移方程：

闭区间 $[L, R]$ 中月之数的个数，等于 $[1, R]$ 中月之数的个数减去 $[1, L - 1]$ 中月之数的个数。接下来以 $[1, R]$ 为例进行说明。

我们还是采取“试填法”的思想，从高位到低位给每一位填数，只要填了一个比上限 $R$ 要小的数位，那么后边的数位无论是多少，整个数值都不会超过 $R$ 。此时就可以立即把动态规划预处理出的结果累加到答案中。只有在每一位上始终填写与上限 $R$ 相同的数字时，才需要继续向后扫描，所以最终的计算量是数值的“位数”级别的，非常小。

具体来说，我们枚举最终的各位数字之和sum，然后从左到右扫描每个数位，设当前正在处理第 $i$ 位（最高位为第 $N$ 位，最低位为第1位），当前已经填写的数字之和是 $t$ ，当前数值对sum取模余数是 $q$ 。我们从小到大枚举第 $i$ 位要填的数字 $p$ 。

1. 若 $p$ 小于上限 $R$ 在第 $i$ 位上的数字，则后边 $i - 1$ 位可以随便填。因为最终的数值能被 sum 整除，所以第 $1 \sim i$ 位构成的数值对 sum 取模余数应该是 $sum - q$ 。因此答案直接累加 $F[i - 1, sum - t - p, sum, (sum - q - p * 10^{i - 1}) \mod sum]$ 。

2. 否则，令 $t = t + p$ ， $q = (q + p * 10^{i - 1}) \mod sum$ ，开始处理第 $i - 1$ 位。

动态规划的计算量约为 $10 * 9^{7}$ ，每个测试点查询的计算量约为 $3000 * 10 * 9$ 。