Update Logs:
- [2024/11/26 23:00] 完成了未完成的部分。
前言
我上一篇写的专栏个人还是认为过于少了，直到后来，做到各种各样的毒瘤题，我才知道我的认知是有多么渺小。
这个故事首先告诉我们井底之蛙。
本人已经做出了洛谷主题库上大部分的数位 DP 题目（至少写这篇文章的时候是 35/38 道），因此我认为我还是有信心来为大家讲解数位 DP 的。
本文全方面讲解了数位 DP 从基础的计数到入土的拓展（例如自动机、进退位和偏序），我认为我至少比 OI-wiki 写得好，但总有缺漏或错误之处，欢迎大佬指出。
这里我专门整理了一个数位 DP 专题的题单，欢迎收藏。
声明：请勿搬运。
引言*
*：此处部分参考于 OI-wiki。
数位 DP 的题目一般是如下情形：
在区间范围很小的时候，显然可以暴力枚举，但是当区间范围很大的时候，就要使用数位 DP 优化。
为什么数位 DP 就能优化这一点呢？数位 DP 的核心思想大概就是，对于很多个数字，他们都有可能存在相同的贡献，比如在 P2602 一题中，数字 12345 和数字 54321，3 都在百位贡献了 2 次，如果统计的区间范围足够大，那么这个数字会更多，所以我们就可以使用计数的方法优化。
而 DP 是什么呢？比方说一道题目要统计 1\sim n 的所有数字的数位和的和，会发现 123456 和 123457 这两个数字他们都有一个共同的前缀，这种前缀只有在暴力枚举的时候会增加复杂度，而 DP 就不会存在这一点。
因而，数位 DP 大概也就有两种分类，并且细分为多种写法：
更复杂的情况会在对应的位置讲解，不过不管怎样，都需要考察选手对于数位的深刻理解能力。
下文会介绍所有常用的数位 DP 写法，并且介绍部分简单的拓展。
纯数位计数
P2602 [ZJOI2010] 数字计数
给定两个正整数 a 和 b，求在 [a,b] 中的所有整数中，每个数码(digit)各出现了多少次。
这道题目大概就是数位 DP 的模板题，但应该是计数类，我将会以计数的角度讲解。
拿到这到题目，第一反应应该是用 [0,b] 的答案减去 [0,a-1] 的答案，所以接下来就只讨论 [0,b] 的范围内。
接下来，把 b 从高到低从左到右画在一个纸板上，就像这样（b=362579）：
| \text{Digits} |
3 |
6 |
2 |
5 |
7 |
9 |
而下一步就是考虑每一种数字会在每一位出现多少次，或者说枚举每一位，钦定这一位填某个数字，这个东西的枚举量级显然不大，可以枚举，比方说我们枚举到左数 4 位，填的数字是 4。
| \text{Digits} |
3 |
6 |
2 |
5 |
7 |
9 |
| \text{Number} |
? |
? |
? |
4 |
? |
? |
其中问号表示我们并不确定，根据数位 DP 的思想，此时我们应该快速求解这样的数字一共多少个，并且小于上面的数字。
这时候数位 DP 的另一个重要思想就有了，那就是大小关系。
回想以下我们如何比较两个数字的大小，显然就是从高位向低位比较，遇到不同的就直接以他们的大小关系作为结果。
放在这个当中也是一样的，既然当前的位置小于原位置，那么前面的所有就一定要小于原数字，后面的不需要管，因为这里已经至少有一个小于原数位的了，此时的贡献也就显然是 362 \times 100。
而大于原数位时同理，假设填的是 5，则贡献为 361 \times 100，因为前面的是必须要严格小于的，但是既然前面都有严格小于的了，后面的又可以随便填写了。
接下来就剩下等于的情况了。
| \text{Digits} |
3 |
6 |
2 |
5 |
7 |
9 |
| \text{Number} |
? |
? |
? |
5 |
? |
? |
我们注意到等于的数位对于答案没有影响，所以这种数位我们忽略掉就可以了，贡献就是前后的数字拼起来，即 36279。
特别的，在统计零的时候，因为前面不能填写零，所以要特判一下。
代码实现较为复杂，不过有助于加强对于数位的理解。
小结
这种类型一般没有值得拓展的地方（除了枚举 LCP），所以建议跳转下一节，如果您也是想要锻炼计数能力，推荐做这些题目：
- [信息与未来 2015] 求回文数（加强版）
- [HAOI2010] 计数
与数位相关的 DP
这就需要考察选手对于标记的理解能力，具体来说就是从高位向低位 DP 的过程中维护一个标记表示“前面有没有卡满原数字”。这种 DP 一般使用记忆化搜索实现。
同样的，一些复杂的题目可能还需要对前导零处理。
P2657 [SCOI2009] windy 数
题意和简化
不含前导零且相邻两个数字之差至少为 2 的正整数被称为 windy 数。windy 想知道，在 a 和 b 之间，包括 a 和 b ，总共有多少个 windy 数？
这种时候使用传统计数的做法就不行了，因为我们很难直接去枚举每一位钦定然后计数了。
同样用 [0,b] 的答案减 [0,a-1] 的答案，下面均讨论 [0,b] 的求法。
不考虑大小；不考虑前导 0
先考虑一种简单的情形：
统计位数为 n 的所有十进制 windy 数，不足的补前导零，即接受 \textbf{00123}。
这种情况就是模板的 DP，只需要记录上一个数字填写的是什么即可。
也就是 dp_{i,lst} = dp_{i+1,lst+j},\vert j\vert \ge 2。
然后考虑这种数字必须要小于给定数字的范围，这时候应该怎么做（仍然考虑前导零）？
不考虑前导 0；考虑大小关系
考虑再次将原数字画在一个纸板上，再次以上一个例子举例。
| \text{Digits} |
3 |
6 |
2 |
5 |
7 |
9 |
| \text{Number} |
? |
? |
? |
? |
? |
? |
DP 的过程本质就是一个一个填数的过程，接下来思考这个填数过程中需要知道些什么。
再一次回想数字大小比较的过程，由于我们是从高位向低位做，所以只要前面比较出来了，后面的就都不需要管了。
那即使比较出来了我也不能 return dp[i] = 0; 啊。
这样，我们就不如引入一个标记，先命名为 lim，这个表示前面填写的数字是否都填满了，也就是前面还有没有比较出来，比如这个样子：
| \text{Digits} |
3 |
6 |
2 |
5 |
7 |
9 |
| \text{Number} |
3 |
6 |
2 |
\color{red}? |
? |
? |
在红色问号处，此时的 lim 标记就是前面还没有比较出来。
然后我们讨论一下，当 lim 标记为 0/1 的时候，情况分别如何。
如果 lim 标记为 0，即没有比较出来，那么当前的数位就必须小于原数位，在这个例子就是 0\sim5，而转移呢？当填写的是 0\sim4 的时候，这个东西就已经比较出来了，那么就 lim 就转为 1，否则如果填写的是 5，则 lim 不变。
如果 lim 标记为 1，那既然都都比较出来了就可以随便填了，毕竟前面也不可能出现填之后大于原数字的情况，填 0\sim 9 都可以。
处理前导 0
现在我们有三个状态了，可是还差一个前导零。
前导 0 也是同理，记录 zero 标记。表示前面是否出现过非 0 数字，如果出现过，那么就可以随便填，否则也就不能填写 0 了。
参考代码
这样直接按照这种方法模拟就能写出来一个很长的代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
int d[18], m;
long long l, r, f[21][11][2][2];
long long calc(int i, int last, int zero, int limited) { // 计算 1~i 之间有多少个数字满足题面条件
// 参数：i 表示到了哪一位，last 表示上一位的值，zero 表示 i 之前是否出现过非零的数字
// limited 表示之前是否有一位没有等于原数最大值
if (i == m + 1) return zero;
if (f[i][last][zero][limited] != -1) return f[i][last][zero][limited];
long long res = 0;
if (i == 1) {
if (m == 1) {
return d[1];
} else {
for (int j = 0; j <= d[1]; ++j) {
res += calc(i + 1, j, (j != 0), (j != d[1]));
}
}
} else {
if (limited) { // 0 ~ 9 随便填，只要满足要求即可
if (zero)
for (int j = 0; j <= 9; ++j) {
if (abs(last - j) >= 2) res += calc(i + 1, j, 1, 1);
}
else {
for (int j = 0; j <= 9; ++j) {
res += calc(i + 1, j, (j != 0), 1);
}
}
} else { // 只能填 0 ~ d[i] 的位置，并满足要求
for (int j = 0; j <= d[i]; ++j) {
if (abs(last - j) >= 2) res += calc(i + 1, j, (bool)(zero | j), (j != d[i]));
}
}
}
return f[i][last][zero][limited] = res;
}
signed main() {
scanf("%lld%lld", &l, &r);
for (long long tr = r; tr; tr /= 10)
d[++m] = tr % 10;
for (int i = 1, j = m; i < j; ++i, --j) swap(d[i], d[j]);
memset(f, 255, sizeof(f));
long long tmp = calc(1, 0, 0, 0);
if (l != 1) {
m = 0;
memset(d, 255, sizeof(d));
for (long long tr = l - 1; tr; tr /= 10)
d[++m] = tr % 10;
for (int i = 1, j = m; i < j; ++i, --j) swap(d[i], d[j]);
memset(f, 255, sizeof(f));
tmp -= calc(1, 0, 0, 0);
}
printf("%lld\n", tmp);
return 0;
}
这个代码大概分为了三部分，第一个是对答案差分，第二个是分解数位，第三个就是正常的 DP 了。
参考代码 2
上一种的代码可能很长（因为是远古时期写的），这里给出一个我比较喜欢的一种压行写法：
long long calc(int i, int last, int zero, int limited) { // 计算 1~i 之间有多少个数字满足题面条件
// 参数：i 表示到了哪一位，last 表示上一位的值，zero 表示 i 之前是否出现过非零的数字
// limited 表示之前是否有一位没有等于原数最大值
if (i == m + 1) return zero; // 数字不能为 0
if (f[i][last][zero][limited] != -1) return f[i][last][zero][limited];
long long res = 0;
for (int j = 0; j <= max(d[i], limited * 9); ++j) {
if (zero && abs(j - last) < 2) continue;
res += calc(i + 1, j, (zero || j), limited || (j != d[i]));
}
return f[i][last][zero][limited] = res;
}
如果想要更为简单的题目，可以尝试 P8764，不需要前导零，换了进制而已。
AT_abc336_e Digit Sum Divisible
定义一个正整数的数位和为其十进制下每个数位的数字的和，如 2024 的数位和为 2+0+2+4=8。
一个正整数 n 被称为好数当且仅当 n 是它的数位和的倍数。
给定 N，求 [1,N] 中好数的个数。1\le N\le 10^{14}。
我们首先想一想，固定数位和应该怎么做。
在不考虑倍数的情况下，数位和固定的数字应该是很好求解的，只要记录一个状态即可。
那考虑模 k 为 0，这种可以动态维护吗？
显然是可以的，假设我们动态维护的余数是 D，则转移到新的数字，新的余数就是 (10D+x)\bmod k。
可是数位和和余数不可能同时维护，那就在 DP 前事先枚举，数位和的量级是 O(10\log_{10}N)，不超过 130，枚举的复杂度是接受的。
这也是正常 DP 常见的出题方式，枚举一开始不知道的小量级东西。
赛时代码：
#include <bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
long long n;
int d[16], top;
long long f[131][16][131][131][2];
/*
设计状态： f[i][j][k][l] 表示要求数位和为 i，考虑到了第 j 位，对数位和取余数为 k，目前数位和为 l 的方案数
*/
long long dfs(int i, int j, int k, int l, int limited) {
if (j == top + 1) {
return l == i && k == 0;
}
if (f[i][j][k][l][limited] != -1) return f[i][j][k][l][limited];
long long tmp = 0;
for (int t = 0; t <= max(limited * 9, d[j]); ++t) {
tmp += dfs(i, j + 1, (k * 10 + t) % i, l + t, (limited || (t != d[j])));
}
return f[i][j][k][l][limited] = tmp;
}
int main() {
scanf("%lld", &n);
for (long long t = n; t; t /= 10) {
d[++top] = t % 10;
}
for (int i = 1, j = top; i < j; ++i, --j) swap(d[i], d[j]);
memset(f, 255, sizeof(f));
long long ans = 0;
for (int i = 1; i <= 130; ++i) {
ans += dfs(i, 1, 0, 0, 0);
}
printf("%lld\n", ans);
return 0;
}
实现细节
一般使用记忆化搜索实现，这里给出理由：
小结
在这一段，你应该就能深刻地理解和数位相关的 DP，应该就能理解标记的作用，偏序关系等。
这里就能做出大部分的数位 DP 了，如果需要更进阶的用法，请查看下一章节，拓展与技巧。
枚举 LCP 的数位 DP
P10959 月之谜
数位 DP 往往会和多测结合，比如 P10959，这个题目仅为上一道题目的加强，增加了多测，但数据范围是 10^{9}。
枚举数位和显然是不能优化的，现在唯一的问题就在于 dp 的复杂度。
我们首先注意到当放满标记（即 lim）为 1 的时候，后面是可以随便填的，这个值是确定的，但是每一次都会重新计算，所以我们优化这个过程即可。
具体来说，lim=0 的时候，只有 O(\log_{B}N) 种可能，且当 lim=0 的时候，1\sim i 所填写的一定是原数字串的最长公共前缀（LCP）。
例如下面这个例子：
| \text{Digits} |
3 |
6 |
2 |
5 |
7 |
9 |
| \text{Number} |
3 |
6 |
2 |
\color{red}? |
? |
? |
注意到上面这个例子的 lim=0，也就注意到 lim=0 当且仅当 1\sim i 的位置是原串的 LCP，显然 LCP 就是可以枚举的！枚举这个东西后，后面的就可以随便填。
随便填写是什么？就是 lim=1！这个东西就是一开始预处理的内容！
具体的实现，可以先只针对 lim=1 的时候进行 DP，对于其他情况直接枚举 LCP 即可。
需要注意的是，在枚举 LCP 之后，再枚举当前位的数字，后面就一定能随便填了！
具体的流程如下：
- 枚举 LCP，则最长公共前缀。
- 在其下一位填写比原数位小的数字。
- 后面的部分直接用事先预处理来的 DP 值计算。
代码实现：
#include <bits/stdc++.h>
using namespace std;
long long n;
int dig[12], top, pw10[12];
long long f[93][12][93][93];
/*
设计状态： f[j][k][l] 表示要求数位和为 i，考虑到了第 j 位，对数位和取余数为 k，目前数位和为 l 的方案数
*/
long long dfs(int i, int j, int k, int l) {
if (j == -1) {
return l == i && k == 0;
}
if (f[i][j][k][l] != -1) return f[i][j][k][l];
long long tmp = 0;
for (int t = 0; t <= 9; ++t) {
tmp += dfs(i, j - 1, (k + pw10[9 - j] * t) % i, l + t);
}
return f[i][j][k][l] = tmp;
}
int solve(int n) {
if (n == 0) return 0;
int yn = n;
for (int i = 9; i >= 0; --i) {
dig[i] = n % 10;
n /= 10;
}
long long ans = 0;
for (int yi = 1; yi <= 90; ++yi) {
long long tmp = 0, l = 0, k = 0;
for (int i = 0; i <= 9; ++i) {
for (int j = 0; j < dig[i]; ++j) {
int yl = l + j, yk = k + j * pw10[i];
tmp += dfs(yi, 8 - i, yk % yi, yl);
}
l += dig[i];
k += dig[i] * pw10[i];
}
tmp += (k % yi == 0 && l == yi);
ans += tmp;
}
return ans;
}
signed main() {
memset(f, 255, sizeof(f));
pw10[9] = 1;
for (int i = 8; i >= 0; --i) pw10[i] = pw10[i + 1] * 10;
int l, r;
while (~scanf("%d%d", &l, &r)) {
printf("%d\n", solve(r) - solve(l - 1));
}
return 0;
}
时间复杂度分析：
记数位长度为 l，进制为 B。
- 原代码 O(T(l^4B^4))。
- 新的代码，首先处理 lim=1 的复杂度是 O(l^4B^4)，然后每一次求解也就都是 O(lB^3)，可以通过本题。
这种方法也是 DP 常用的优化方法，主要思想在于对于十分频繁且几乎固定的状态，可以采用事先预处理的方法，并且枚举复杂度低的东西（这里就是 LCP），以应对多测的复杂情形。
P3791 普通数学题
定义 d(x) 表示 x 的约数个数，d(0)=0。
给定 n,m,x，求 \displaystyle\sum_{i=0}^n \sum_{j=0}^m d(i\oplus j\oplus x)。
还有一种可能就是纯计数，我们注意到，如果我们把 n,m 转二进制再枚举两个的 LCP，后面就会有一大段是可以随便填写的。
我们注意到如果后面一大段都随便填写的话，那么这个答案的和就将是一个 d 的前缀和，就像这样：
| n |
1 |
0 |
1/\color{red}0 |
? |
? |
? |
? |
| m |
1 |
1 |
0 |
1/\color{red}0 |
? |
? |
? |
具体的，枚举 LCP 之后也要像前面一样枚举当前的数字，比如在这个例子中，就枚举 0，不过既然需要要求后面的是小于原数字的，那么就不能在对应的位置填写 1。
这样的话，所有数字的可能性（假设 x=0）就是在 0100000\sim 0101111 之间 d 的前缀和乘 2，d 的前缀和是很好求解的，而为什么是乘二（其实这个不固定，和枚举的 LCP 相关），读者可以自行推导。
如果 x\neq 0 的时候，那么一定就是前面会被异或，后面则不影响。
实现细节
对于这种方法，有一种降低实现难度的方法，就是把小于等于转换为小于，对于高维的数位 DP 也就降低了实现复杂度。
拆分写法的数位 DP
还是用 P2602 来举例，假设 b=315794，统计 [0,315794] 之间的数字个数，可以拆分为 [0,9] 之间的答案 + [10,99] 的答案 + [100,999] 之间的答案 ……，一直到这个区间包含 315794 为止。
然后就可以统计 [100000, 315794] 之间的答案了，怎么统计呢，让我们一位一位看。
- 第 1 位：[100000,299999]。
- 第 2 位：[300000,309999]。
- 第 3 位：[310000,314999]。
- 第 4 位：[315000,315699]。
- 第 5 位：[315700,315789]。
- 第 6 位：[315790,315793]。
最后单独统计本身即可。
其实这种情况就是枚举 LCP 方法的拓展，一般只会在与数位长度及其相关的时候且很复杂的时候才会运用。
大部分时候都可以用其他方法代替，本人一般不常用。
其他数位 DP 优化
有一种不是很常用的方法，就是在状态数量很少、转移复杂度却比较大的情况下，可以直接去计算出转移到下一个状态的方案数量，具体参考拓展与技巧中的 Lucas 定理一栏，有一个神奇的例题。
还有一种优化，就是数位 DP 的题目通常状态数量比较少，但是有些时候不得不定义更高维度的 DP 数组，这时候就可以使用哈希表优化，具体参考 CF55D。
拓展与技巧
这里按照经典度和重要性综合参考排序。
多维数位 DP
多维数位 DP 通常指的是有多个数字要满足固定的偏序关系。
之前的例题也多处涉及了，这种情况一般都是有两个上界，只需要同时做就行，如果有下界的情况呢？就可以再用一个和下界相关的标记来处理即可。
不过要是这么写的话，常数就会巨大，因为这种情况根本跑不满，建议使用 0/1/2（贴下界，贴上界，啥都不贴）的方式，或者哈希表来优化。
用标记处理更复杂的偏序关系
从左往右
前面所提到的标记一般都是维护小于的，如何同时维护大于呢？
其实也很简单，就看有没有贴这个分界点即可。
比如说这个问题：
很好地让你维护与 $x$ 的所有偏序关系，这种情况就用 $0/1/2$ 来维护，其中 $lim=1$ 表示前面与 $x$ 相等，$lim=0$ 表示前面小于 $x$，$lim=2$ 表示前面大于 $x$。
而转移显然，如果 $lim\neq 1$，那么显然都比较出来了，一定不会影响结果。
但 $lim=1$ 的时候说明还没有比较出来，也就会有影响了。
所以对于从左往右，我们总结出来以下三点：
- 如果标记为 $0$ 或 $2$ 或等于原数位则不变。
- 如果小于原数位，更新标记为 $0$。
- 如果大于原数位，更新标记为 $2$。
#### 从右往左
在某些极端情况，甚至一定需要从右往左进行 DP（例题需要两者都有），而从右往左是否类似呢？让我们探究一下。
|$\text{Digit}$|$3$|$1$|$2$|$5$|$9$|
|:-:|:-:|:-:|:-:|:-:|:-:|
|$\text{Number}$|$?$|$?$|$\color{red} ?$|$5$|$9$|
同样地去使用标记，$0$ 表示小于，$1$ 表示等于，$2$ 表示大于，不过由于是后缀，情况肯定有所不同。
当标记为 $1$ 的时候，后面的一切肯定都没有影响，就直接根据当前为填写的情况确定即可，对于上面这个例子，当填写 $0\sim1$ 的时候转移至 $0$，填写 $3\sim9$ 的时候转移至 $2$，否则还是 $1$。
而标记为 $2$ 的时候，就像这样：
|$\text{Digit}$|$3$|$1$|$2$|$5$|$9$|
|:-:|:-:|:-:|:-:|:-:|:-:|
|$\text{Number}$|$?$|$?$|$\color{red} ?$|$9$|$2$|
如果当前填写的数字是小于原数位的，那么标记就会直接更改为 $0$，如果是大于等于显然就不变。
标记为 $1$ 的时候同理，所以我们总结出来以下三点：
- 如果大于原数位，更新标记为 $2$。
- 如果等于原数位，不变。
- 如果小于原数位，更新标记为 $0$。
#### [P9129 [USACO23FEB] Piling Papers G](https://www.luogu.com.cn/problem/P9129)
> 给定长度为 $n(1\leq n\leq 300)$ 的整数序列 $a(1\leq a_i\leq 9)$，和整数区间 $[A,B](1\leq A\leq B\leq 10^{18})$，有 $q$ 次询问，每次询问给出 $l,r$。每次询问开始，你有一个空串 $x$，你可以正序对 $a_{l\sim r}$ 进行操作，操作有三种：$x\rightarrow\overline{x+a_i}$，$x\rightarrow\overline{a_i+x}$，或者什么也不做，求 $\overline{x}$ 的取值在 $[A,B]$ 的不同的操作方案数，对 $10^9+7$ 取模。
**可以尝试先独立思考本题目。**
首先转化一下，选择一些数字，有序的把他们扔到一个双端队列的前面或后面，考虑倒着做，那这个就是一个类似于双端栈的结构，可由于大小不固定，就强制要求这个固定为数位的长度，对于小于数位长度的，直接用组合数计算即可。
那这个就是区间 DP，考虑一定要求填满所有的数位，则就这样 DP，$dp_{l,r,dl,dr,ll,lr}$ 表示目前要处理 $a[l,r]$，现在的数字还有 $dl\sim dr$ 这一段区间没有填写，$ll$ 表示左边标记，$lr$ 表示右边标记，比如这个例子：
|$\text{Digit}$|$3$|$2$|$6$|$7$|$1$|$2$|$5$|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|$\text{Number}$|$2$|$9$|$?$|$?$|$?$|$9$|$2$|
这种情况也就是 $dl=3, dr=1,ll=0,lr=2$，的情况，最终我们一定是希望 $dr = dl + 1\land(ll=0 \lor (ll=1\land lr\le 1))$，即所有数字都填完了，且整体是小于原数字的。
这里的左右合并其实也很好理解，左边如果等于就看右边，如果小于就直接就是小于，如果是大于则就不管他了。
~~甚至还是一个很好的分治。~~
不过需要注意的是，因为我们是从两边开始填写，所以应该是 $A[l,r]$ 倒着来填写，即从 $r$ 填写到 $l$。
附上石山。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, q, a[304], ans[50004], dp[304][20][20][3], digs[20], tot, pw2[304], frc[304], inv[304];
vector<pair<int, int>> qrs[304];
const int p = 1e9 + 7;
int C(int n, int m) {
if (n < m) return 0;
return frc[n] * inv[m] % p * inv[n - m] % p;
}
int dfs(int l, int r, int dl, int dr, int llim, int rlim) {
if (llim == 0) return C(r - l + 1, dr - dl + 1) * pw2[dr - dl + 1] % p;
if (llim == 2) return 0;
if (r == l - 1) return rlim <= 1 && (dl > dr);
if (dl > dr) return rlim <= 1;
assert(llim == 1);
if (dp[r][dl][dr][rlim] != -1) return dp[r][dl][dr][rlim];
int ans = dfs(l, r - 1, dl, dr, llim, rlim);
if (a[r] > digs[dl]) ans += dfs(l, r - 1, dl + 1, dr, 2, rlim);
else if (a[r] == digs[dl]) ans += dfs(l, r - 1, dl + 1, dr, 1, rlim);
else ans += dfs(l, r - 1, dl + 1, dr, 0, rlim);
if (a[r] > digs[dr]) ans += dfs(l, r - 1, dl, dr - 1, llim, 2);
else if (a[r] == digs[dr]) ans += dfs(l, r - 1, dl, dr - 1, llim, rlim);
else ans += dfs(l, r - 1, dl, dr - 1, llim, 0);
return dp[r][dl][dr][rlim] = ans % p;
}
void solve(int x, int w) {
if (x < 0) return;
if (x == 0) {
for (int i = 1; i <= q; ++i) {
ans[i] += w;
}
return;
}
tot = 0;
while (x) {
digs[++tot] = x % 10;
x /= 10;
}
for (int l = 1, r = tot; l < r; ++l, --r) swap(digs[l], digs[r]);
for (int l = 1; l <= n; ++l) {
memset(dp, 255, sizeof(dp));
for (auto i : qrs[l]) {
if (i.first - l + 1 >= tot || 1) {
(ans[i.second] += dfs(l, i.first, 1, tot, 1, 1) * w) %= p;
}
for (int j = 0; j <= min(i.first - l + 1, tot - 1); ++j) {
ans[i.second] += (w * C(i.first - l + 1, j) * pw2[j] % p);
}
}
}
}
signed main() {
pw2[0] = 1; for (int i = 1; i <= 300; ++i) pw2[i] = pw2[i - 1] * 2 % p;
frc[0] = frc[1] = inv[0] = inv[1] = 1;
for (int i = 2; i <= 300; ++i) {
frc[i] = frc[i - 1] * i % p;
inv[i] = (p - p / i) * inv[p % i] % p;
}
for (int i = 2; i <= 300; ++i) (inv[i] *= inv[i - 1]) %= p;
ios::sync_with_stdio(0); cin.tie(0);
int x, y;
cin >> n >> x >> y;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
cin >> q;
for (int i = 1; i <= q; ++i) {
int l, r;
cin >> l >> r;
qrs[l].push_back({r, i});
}
solve(y, 1);
solve(x - 1, -1);
for (int i = 1; i <= q; ++i) {
cout << (ans[i] % p + p) % p << "\n";
}
return 0;
}
```
这里运用到了一个优化，就是当左边已经确定是小于的时候，后面同样可以用组合数算，如果是大于的时候，直接 `return 0` 即可。
### 加减法进退位
#### [P9387 [THUPC 2023 决赛] 巧克力 ](https://www.luogu.com.cn/problem/P9387)
博弈论的知识不会在这里涉及，您可以把这道题理解为如下题目：
> 给定数字 $N,M,X$，请求出满足如下条件的三元组 $(a,b,c)$ 的数量：
> - $b\neq0$
> - $a+b+c\le N \lor a+b+c=M$
> - $a\oplus c\oplus(a+b+c) = X$
首先这里会有一个加号，这样就特别不好做，考虑倒着做，按照人定义的加法，是需要进位的，而且是从右往左做。
加法很难从左往右做，所以才会考虑倒着做。
具体的，定义状态 $dp_{i,limn,eqm,carry,bzero}$ 表示考虑第 $i$ 位，相对于 $n$ 的偏序关系为 $limn$，是否等于 $eqm$，当前进位的个数为 $carry$，$b$ 是否为 $0$。
除了进位标记都会转移，让我们思考进位标记带来的影响。
这就像我们做小学二年级作竖式一样，我们会在进位位置的左边一位的右下角写一个角标，表示在算到那一位的时候需要累加的数字，对于二进制，就像这样：
||$0$|$0$|$1$|$0$|$1$|$1$|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:
|$+$|$0_1$|$1_1$|$1$|$0_1$|$1_1$|$1$|
|$=$|$1$|$0$|$0$|$1$|$1$|$0$|
不难发现一个位能够向前一位产生的进位就是当前位置的累加和对 $2$ 下取整的数字，而且当加的总数字个数是 $n$ 的时候，至多只会有 $n-1$ 次进位，在这道题中 $n=3$。
于是我们就可以很方便地从右往左进行 DP 了。
```cpp
int dfs(int i, int carry, int nlim, int eqm, int bzero) {
if (i == 64) {
return (carry == 0 && bzero) * (eqm + (nlim <= 1));
}
if (dp[i][carry][nlim][eqm][bzero] != -1) return dp[i][carry][nlim][eqm][bzero];
int ans = 0;
int ndig = (n >> i) & 1;
int mdig = (m >> i) & 1;
int xdig = (X >> i) & 1;
for (int f = 0; f < 8; ++f) {
int a = (f & 1), b = !!(f & 2), c = !!(f & 4);
int reald = (a + b + c + carry) & 1;
if ((reald ^ a ^ c) != xdig) continue;
ans += dfs(i + 1, (a + b + c + carry) >> 1, (reald > ndig ? 2 : (reald < ndig ? 0 : nlim)), (eqm && (reald == mdig)), (bzero || b));
}
return dp[i][carry][nlim][eqm][bzero] = ans % p;
}
```
如果您确实想要完整做出这道题目，我可以告诉您 $\text{SG}(x)=x$，所以这就是为什么是异或地原因。
而对于前缀地异或和，是有结论的，具体满足如下条件：
- 当 $n\bmod 4=0$ 时，$\bigoplus_{i=1}^{N} i=N$。
- 当 $n\bmod 4=1$ 时，$\bigoplus_{i=1}^{N} i=1$。
- 当 $n\bmod 4=2$ 时，$\bigoplus_{i=1}^{N} i=N+1$。
- 当 $n\bmod 4=3$ 时，$\bigoplus_{i=1}^{N} i=0$。
有了这个结论，您甚至还可以做出 [AT_arc133_d](https://www.luogu.com.cn/problem/AT_arc133_d)，具体不在此处展开。
这样的话，减法也就是退位，与上文同理。
#### [[SDOI2016] 储能表](https://www.luogu.com.cn/problem/P4067)
在有些情况，这种加减法进退位产生的贡献甚至可以直接计算，题目如下：
> 求 $$\displaystyle\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} \max((i \oplus j)-k,0)$$。
如果从低位向高位，那么显然就要求在最后的时候不能退位即可，如果我们考虑从高位向低位 DP，那么就可以转换成统计所有 $(i \oplus j)-k\ge0$ 的 $(i \oplus j)-k$ 的和，这样的话考虑结果记录两个值，一个是满足这个条件的数字的出现次数，一个是这样的贡献总和。
那么在减法退位的时候，直接计算出减法的贡献，然后直接减去即可。
具体的，我们知道转移到另一个状态的方案数量和贡献和，那么对于当前的贡献和就是退位的贡献乘方案数量，再加上转移到另一个状态的贡献和，方案数正常累加即可。
给出核心代码：
```cpp
int dfs1(int x, int li, int lj, int gek) { // li, lj = lim i, lim j，gek 表示大于 k 的标记（大于等于和大于没区别）
if (x == M + 1) return 1;
if (dp1[x][li][lj][gek] != INF) return dp1[x][li][lj][gek];
int ans = 0;
for (int i = 0; i <= max(dgn[x], li); ++i) {
for (int j = 0; j <= max(dgm[x], lj); ++j) {
if (((i ^ j) < dgk[x]) && !gek) continue;
ans += dfs1(x + 1, li || (i != dgn[x]), lj || (j != dgm[x]), gek || ((i ^ j) > dgk[x]));
}
}
return dp1[x][li][lj][gek] = ans % p;
}
int dfs2(int x, int li, int lj, int gek) {
if (x == M + 1) return 0;
if (dp2[x][li][lj][gek] != INF) return dp2[x][li][lj][gek];
int ans = 0;
for (int i = 0; i <= max(dgn[x], li); ++i) {
for (int j = 0; j <= max(dgm[x], lj); ++j) {
if (((i ^ j) < dgk[x]) && !gek) continue;
int gs = (1ll << (M - x)); // 计算当前位 - k 的贡献
if (((i ^ j) < dgk[x])) gs *= -1; // 退位
else if ((i ^ j) == dgk[x]) gs *= 0; // 相同就消掉了
else gs *= 1; // 正常贡献
gs %= p;
(ans += gs * dfs1(x + 1, li || (i != dgn[x]), lj || (j != dgm[x]), gek || ((i ^ j) > dgk[x])) % p);
(ans += dfs2(x + 1, li || (i != dgn[x]), lj || (j != dgm[x]), gek || ((i ^ j) > dgk[x])));
}
}
return dp2[x][li][lj][gek] = ans % p;
}
```
有些时候，甚至可以只记录后面的位数，比如在加减的数字很小的时候，那么直接记录后面的几位以及前面的连续 $1/0$ 段也是可以的，具体可以参考 CCPC Jinan 2020 L, Bit Sequence，读者可以自行思考。
### Lucas 定理
回想 Lucas 定理，在求解 $C_{n}^{m}$ 且模数很小的时候，可以将 $n,m$ 转换成 $p$ 进制。对于每一**位**来算，然后乘起来。
会发现这个也是拆数位的思想，代表的题目有 [P8688](https://www.luogu.com.cn/problem/P8688) 和 [P7976](https://www.luogu.com.cn/problem/P7976)。
甚至在模 $2$ 的情况下，$C_{n}^{m} \equiv [n~ \&~ m = n]\pmod 2$，这里的 $\&$ 是位运算。
### 套自动机
参考 [P7717](https://www.luogu.com.cn/problem/P7717)，需要套一层 trie 树节点，顺便结合了贪心的思想。
[P3311](https://www.luogu.com.cn/problem/P3311) 则是一个裸的套 AC 自动机的题目。
有些时候套的可能不止自动机，也有可能是一个压缩后的状态，比如 [CF1073E](https://www.luogu.com.cn/problem/CF1073E)。
某些极端情况甚至可能套计算几何的叉积，或者是插头 DP（不过我没有见过）。
### Nim 游戏（SG 函数）
可参考上文的“加减法进退位”中的例题 1。
其主要的思想就是博弈论中的 $\text{SG}$ 函数，具体来说如果一个博弈游戏分为多个局面，那么先手是否可以获胜就取决于每个局面的 $\text{SG}$ 函数的异或和是否为 $0$。
再深入一点，即 $\text{SG}$ 函数具体的求解方式，这个不在讨论的范畴之中，可以自行查阅相关文献了解。
这也就是为什么 Nim 游戏类型的数位 DP 题目也是可以用数位 DP 来解决的。
### 矩阵
状态很少甚至可以仍进矩阵中，找不到别的，只有 [P2106](https://www.luogu.com.cn/problem/P2106) 合适一点。
甚至还可以带上标记，例如求解 $0$ 到 $5555555\dots$ 中所有的 windy 数，也就必须要把标记也作为这个矩阵的一个转移对象。
## 怎么调试数位 DP 题目
这个一般只能凭经验，这里是我和我的同学（@small_john） 整理出来的经验：
- 输出转移了哪些状态。
- 把记忆化去掉，如果不一样了说明状态错了。
- 把记忆化去掉，改成普通的搜索，你就能输出每一个数字长什么样子。
## 总结
数位 DP 常用的也就有 4 种写法，这里再做整理：
- 数位计数。
- 纯数位计数。
- 拆分区间范围。
- 数位 DP。
- 纯 DP
- 枚举 LCP + DP。
对于数位计数，只需要理清楚数位之间的偏序关系即可。
而拆分区间范围也大概等同于枚举 LCP + DP 的方式，一般不常用。
标记本质上就是维护数位偏序关系，只要多做几道题目，基本都不难。
枚举 LCP + DP 是部分毒瘤题目常会存在的方式，往往需要特殊的转换。
这里我专门整理了一个[数位 DP 专题](https://www.luogu.com.cn/training/643020)的题单，欢迎收藏。
## 鸣谢 & 题外话
- 感谢 @[small_john](https://www.luogu.com.cn/user/581316) 提供精神支持和大部分技术支持！
- 感谢 @[OIer_tan](https://www.luogu.com.cn/user/700210) 提供精神支持和部分技术支持！
- 感谢 @[Joker_Fish](https://www.luogu.com.cn/user/530468) 提供精神支持！
- 感谢 @[_RON_](https://www.luogu.com.cn/user/1127258) 提供精神支持！
希望可以帮助到您！如果您对任何一处有疑问，欢迎提问或指正！
你说得对，但是 @CuteChat 学这个东西前后相隔了 11 个月。