数位DP
常见的模板：询问 \(l\sim r\) 中有多少个满足给定条件的数，\(1\le l\le r\le 10^{18}\)。
这种问题，数位DP可以做到 \(O(\log v)\) 级别，其中 \(v\) 是 \(l,r\) 的值域。
思路
直接枚举会枚举大量不可能满足条件的数，可以从数位入手。
数位DP的算法流程如下：
-
几个定义：
-
\(len(x)\) 表示 \(x\) 的位数。
-
\(d(x,i)\) 表示 \(x\) 的第 \(i\) 位上的数字。
-
-
预处理，设 \(f_{i,j,...}\) 表示位数位 \(i\)，最高位为 \(j\)，满足给定条件的数的个数。
-
统计答案，令 \(query(x)\) 表示 \(1\sim x-1\) 中满足给定条件的数的个数，答案为 \(query(r+1)-query(l)\)。
-
统计位数为 \(1\sim len(x)-1\) 的数。
-
统计位数为 \({len}(x)\) 的数。
-
统计第 \(1\sim len(x)-1\) 位都与 \(x\) 相同，且第 \(len(x)\) 位不超过 \(d(x,len(x))\) 的数。注意，如果题目考虑前导零，则不进行该步骤。
-
统计第 \(1\sim i\) 位都与 \(x\) 相同，且第 \(i\) 位不超过 \(d(x,i)\) 的数。
-
-
例题
设 \(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\sim len(x)-1\) 的“好数”。
总数为 \(\displaystyle\sum_{i=1}^{len(x)-1}\sum_{j=1}^9\sum_{k=1}^3 f_{i,j,k}\)
-
位数为 \({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;
}