数位DP

常见的模板：询问 \(l\sim r\) 中有多少个满足给定条件的数，\(1\le l\le r\le 10^{18}\)。

这种问题，数位DP可以做到 \(O(\log v)\) 级别，其中 \(v\) 是 \(l,r\) 的值域。

思路

直接枚举会枚举大量不可能满足条件的数，可以从数位入手。

数位DP的算法流程如下：

1. 几个定义：

   • \(len(x)\) 表示 \(x\) 的位数。

   • \(d(x,i)\) 表示 \(x\) 的第 \(i\) 位上的数字。

2. 预处理，设 \(f_{i,j,...}\) 表示位数位 \(i\)，最高位为 \(j\)，满足给定条件的数的个数。

3. 统计答案，令 \(query(x)\) 表示 \(1\sim x-1\) 中满足给定条件的数的个数，答案为 \(query(r+1)-query(l)\)。

   1. 统计位数为 \(1\sim len(x)-1\) 的数。

   2. 统计位数为 \({len}(x)\) 的数。

      • 统计第 \(1\sim len(x)-1\) 位都与 \(x\) 相同，且第 \(len(x)\) 位不超过 \(d(x,len(x))\) 的数。注意，如果题目考虑前导零，则不进行该步骤。

      • 统计第 \(1\sim i\) 位都与 \(x\) 相同，且第 \(i\) 位不超过 \(d(x,i)\) 的数。

例题

luogu.CF1036C/CF1036C

设 \(f_{i,j,k}\) 表示所有位数为 \(i\)，最高位为 \(j\)，有 \(k\) 个数位上的数字为 \(1\sim 9\) 的数字个数。

转移：

\(f_{i,j,k}=\begin{cases}\displaystyle\sum_{c=0}^9 f_{i-1,c,k}\ (j=0)\\ \displaystyle\sum_{c=0}^9 f_{i-1,c,k-1}\ (j\ne 0,k\ne 0)\end{cases}\)

初始值：\(f_{1,0,0}=1,f_{1,1\sim 9,1}=1\)

定义 \(len(x)\) 表示 \(x\) 的位数，\(d(x,i)\) 表示 \(x\) 的第 \(i\) 为上的数字，\(query(x)\) 表示 \(1\sim x-1\) 中有多少个“好数”，答案为 \(query(r+1)-query(l)\)。

\(query(x)\) 由两部分组成：

1. 位数为 \(1\sim len(x)-1\) 的“好数”。

   总数为 \(\displaystyle\sum_{i=1}^{len(x)-1}\sum_{j=1}^9\sum_{k=1}^3 f_{i,j,k}\)

2. 位数为 \({len}(x)\) 的“好数”，因为要去掉前导零，把最高位单独考虑：

   • 考虑第 \(1\sim len(x)-1\) 位都与 \(x\) 相同，且第 \(len(x)\) 位不超过 \(d(x,len(x))\) 的“好数”，总数为 \(\displaystyle\sum_{i=1}^{d(x,len(x))-1}\sum_{j=0}^3 f_{len(x),i,j}\)

   • 考虑第 \(1\sim i\) 位都与 \(x\) 相同，且第 \(i\) 位不超过 \(d(x,i)\)，总数为 \(\displaystyle\sum_{i=1}^{len(x)-1}\sum_{j=0}^{d(x,i)-1}\sum_{k=0}^{3-cnt(i)}f_{i,j,k}\)，其中 \(cnt(i)\) 表示 \(x\) 的 \(i\sim len(x)-1\) 位中有多少位为 \(1\sim 9\)。

#include <bits/stdc++.h>
using namespace std;
int t, d[25];
long long l, r, f[25][25][25];
long long query(long long x) {
    int len = 0;
	long long ret = 0;

    while (x)
        d[++len] = x % 10, x /= 10;

    for (int i = 1; i < len; i++)
        for (int j = 1; j <= 9; j++)
            for (int k = 0; k <= 3; k++)
                ret += f[i][j][k];

    for (int i = 1; i < d[len]; i++)
        for (int j = 0; j <= 3; j++)
            ret += f[len][i][j];

    for (int i = len - 1, cnt = 0; i >= 1; i--) {
        if (d[i])
            cnt++;

        for (int j = 0; j < d[i]; j++)
            for (int k = 0; k <= 3 - cnt; k++)
                ret += f[i][j][k];
    }

    return ret;
}
int main() {
    cin >> t;
    f[1][0][0] = 1;

    for (int i = 1; i <= 9; i++)
        f[1][i][1] = 1;

    for (int i = 2; i <= 19; i++) {
        for (int j = 0; j <= 9; j++) {
            for (int k = 0; k <= 3; k++) {
                for (int c = 0; c <= 9; c++) {
                    if (!j)
                        f[i][j][k] += f[i - 1][c][k];
                    else if (k)
                        f[i][j][k] += f[i - 1][c][k - 1];
                }
            }
        }
    }

    while (t--) {
        cin >> l >> r;
        cout << query(r + 1) - query(l) << '\n';
    }

    return 0;
}