浅谈数位 DP
本帖最后由 zhangjinxuan 于 2024-12-20 17:49 编辑浅谈数位 DP
Update Logs:
- 完成了未完成的部分。
更好的阅读体验。
本文章的作者与上处链接所指向的文章的作者是同一个人。
前言
本文全方面讲解了数位 DP 从基础的计数到入土的拓展（例如自动机、进退位和偏序），我认为我至少比 OI-wiki 写得好，但总有缺漏或错误之处，欢迎大佬指出。
这里我专门整理了一个数位 DP 专题的题单，欢迎收藏。
声明：请勿搬运。
引言
此处部分参考于 OI-wiki。
数位 DP 的题目一般是如下情形：
- 在一个区间范围内统计一些东西。
在区间范围很小的时候，显然可以暴力枚举，但是当区间范围很大的时候，就要使用数位 DP 优化。
为什么数位 DP 就能优化这一点呢？数位 DP 的核心思想大概就是，对于很多个数字，他们都有可能存在相同的贡献，比如在 P2602（分别统计一个范围内所有数位的出现次数） 一题中，数字 $12345$ 和数字 $54321$，$3$ 都在百位出现了 $2$ 次，如果统计的区间范围足够大，那么这个数字会更多，所以我们就可以使用计数的方法优化。
而 DP 是什么呢？比方说一道题目要统计 $1\sim n$ 的所有数字的数位和的和，会发现 $123456$ 和 $123457$ 这两个数字他们都有一个共同的前缀，这种前缀只有在暴力枚举的时候会增加复杂度，而 DP 就不会存在这一点。
因而，数位 DP 大概也就有两种分类，并且细分为多种写法：
- 数位计数。
- 纯数位计数。
- 拆分区间范围。
- 数位 DP。
- 纯 DP
- 枚举 LCP + DP。
更复杂的情况会在对应的位置讲解，不过不管怎样，都需要考察选手对于数位的深刻理解能力。
下文会介绍所有常用的数位 DP 写法，并且介绍部分简单的拓展。
希望您能在阅读下文之前评分和收藏，谢谢！
https://xxx.ilovefishc.com/album/202003/31/144219wdi4u2t8d33u22x3.gif
纯数位计数
P2602 数字计数
给定两个正整数 $a$ 和 $b$，求在 $$ 中的所有整数中，每个数码(digit)各出现了多少次。
$a\le b\le 10^{9}$，暴力枚举无法通过。
这道题目大概就是数位 DP 的模板题，但应该是计数类，我将会以计数的角度讲解。
拿到这到题目，第一反应应该是用 $$ 的答案减去 $$ 的答案，所以接下来就只讨论 $$ 的范围内。
接下来，把 $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$。
特别的，在统计零的时候，因为前面不能填写零，所以要特判一下。
这样，时间复杂度就变成了 $O(log b)$，比暴力枚举快了很多倍。
代码实现较为复杂，不过有助于加强对于数位的理解。
小结
这种类型一般没有值得拓展的地方（除了枚举 LCP），所以建议跳转下一节，如果您也是想要锻炼计数能力，推荐做这些题目：
- [信息与未来 2015] 求回文数（加强版）
- 计数
与数位相关的 DP
**** Hidden Message *****
小结
在这一段，你应该就能深刻地理解和数位相关的 DP，应该就能理解标记的作用，偏序关系等。
这里就能做出大部分的数位 DP 了，如果需要更进阶的用法，请查看下一章节，拓展与技巧。
枚举 LCP 的数位 DP
**** Hidden Message *****
实现细节
对于这种方法，有一种降低实现难度的方法，就是把小于等于转换为小于，对于高维的数位 DP 也就降低了实现复杂度。
拆分写法的数位 DP
**** Hidden Message *****
拓展与技巧
这里按照经典度和重要性综合参考排序。
**** Hidden Message *****
矩阵
状态很少甚至可以仍进矩阵中，找不到别的，只有 P2106 合适一点。
甚至还可以带上标记，例如求解 $0$ 到 $5555555\dots$ 中所有的 windy 数，也就必须要把标记也作为这个矩阵的一个转移对象。
怎么调试数位 DP 题目
这个一般只能凭经验，这里是我和我的同学（@small_john） 整理出来的经验：
- 输出转移了哪些状态。
- 把记忆化去掉，如果不一样了说明状态错了。
- 把记忆化去掉，改成普通的搜索，你就能输出每一个数字长什么样子。
总结
数位 DP 常用的也就有 4 种写法，这里再做整理：
- 数位计数。
- 纯数位计数。
- 拆分区间范围。
- 数位 DP。
- 纯 DP
- 枚举 LCP + DP。
对于数位计数，只需要理清楚数位之间的偏序关系即可。
而拆分区间范围也大概等同于枚举 LCP + DP 的方式，一般不常用。
标记本质上就是维护数位偏序关系，只要多做几道题目，基本都不难。
枚举 LCP + DP 是部分毒瘤题目常会存在的方式，往往需要特殊的转换。
这里我专门整理了一个数位 DP 专题的题单，欢迎收藏。
鸣谢 & 题外话
[*] 感谢 @small_john 提供精神支持和大部分技术支持！
[*] 感谢 @OIer_tan 提供精神支持和部分技术支持！
[*] 感谢 @Joker_Fish 提供精神支持！
[*] 感谢 @_RON_ 提供精神支持！
希望可以帮助到您！如果您对任何一处有疑问，欢迎提问或指正！
https://xxx.ilovefishc.com/album/202003/31/144219wdi4u2t8d33u22x3.gif
本帖最后由 zhangjinxuan 于 2024-12-9 21:08 编辑
纯胡说，没什么东西 @tommyyu @sfqxx @zsy0226 @Ewan-Ahiouy @元豪 @陈尚涵 @柿子饼同学 @学习编程中的Ben @高山 想起来之前做过的一个比较恶心的
CF1194G
哎, 退役了
#include <bits/stdc++.h>
using namespace std;
/*
首先把 x / y
换成k*dx / k*dy
枚举的是 x 和 y, 但是我们必须保证 k 相同, 并且 x, y 分别被 dx, dy 整除
于是乎我们状态中存下来 前 pos 位的 x, y 分别除以 dx, dy 的余数, 再存 x, y 中出现的数字
答案就是 余数都是 0 并且出现数字符合题意的状态的答案之和
举个栗子:
这个竖式的答案是 k, 我们按位枚举 k 的位数(这样保证了 k 相同), 现在 k 这一位是 i
______________
dx )A B j ...这里是 x 的位置, 在做除法, 枚举 x 的这一位为 j
_________
上一次的余数 = rx
那么这次的余数就是 (rx*10 + j) - i*dx, 这个余数要在 [0, dx) 的范围
再用状压把这次出现的数位 j 打上去即可
*/
const int N = 102;
const int P = 998244353;
// f(pos, sx, sy, rx, ry) 代表前 pos 位, x, y 带有的数字状态, x, y 除以 dx, dy 的余数
int f;
string s;
int num, n;
int dx, dy;
int ans;
// 分数值一样的一起算, 不然会算重
// 情况最多的是 1/2 = 2/4 = 3/6 = 4/8 共 4 组
// tot 是组数
int choice, tot;
// type == 0 表示是 x, type == 1 表示是 y
int Add(int st, int d, int type){
for(int i = 0; i < tot; i++){
if(choice == d){
st |= (1 << i);
return st;
}
}
return st;
}
int dfs(int pos, int sx, int sy, int rx, int ry, bool lim){
if(pos == n + 1){
// 没有余数, 并且 x 中出现 dx, y 中出现了 dy
if(!rx && !ry && (sx & sy)) return 1;
return 0;
}
auto& cur = f;
if(!lim && ~cur) return cur;
int res = 0;
int up = 9;
int newrx, newry;
if(lim) up = num;
// 枚举 k 的数位(竖式答案), x / dx == y / dy == k
for(int ki = 0; ki < 10; ki++){
// 枚举 x 的数位(竖式被除数)
for(int xi = 0; xi <= up; xi++){
newrx = (rx*10 + xi) - ki*dx;
if(newrx < 0) continue;
if(newrx >= dx) break;
// 枚举 y 的数位, 流程是一样的
// y 比 x 小, 所以不用管
for(int yi = 0; yi < 10; yi++){
newry = (ry*10 + yi) - ki*dy;
if(newry < 0) continue;
if(newry >= dy) break;
res = (res + dfs(pos + 1, Add(sx, xi, 0), Add(sy, yi, 1), newrx, newry, lim && (xi == up))) % P;
}
}
}
if(!lim) cur = res;
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> s;
n = s.size();
for(int i = 1; i <= n; i++){
num = s - '0';
}
// dx == dy 的情况, 这时每个数都满足条件, ans += num
for(int i = 1; i <= n; i++){
ans = (ans*10 + num) % P;
}
// 强制令 x > y (即 dx > dy), 这样只需要满足 x <= n 就行了
for(int i = 1; i < 10; i++){
for(int j = 1; j < i; j++){
if(__gcd(i, j) != 1) continue;
memset(f, -1, sizeof(f));
for(tot = 0; tot < 4; tot++){
if(i*(tot + 1) > 9) break;
choice = i*(tot + 1);
choice = j*(tot + 1);
}
dx = i, dy = j;
long long w = (dfs(1, 0, 0, 0, 0, 1)*2ll) % P;
ans = (ans + w) % P;
}
}
cout << ans;
return 0;
} noip分数线怎么还变高了...
哎这下完了 zhangjinxuan 发表于 2024-12-7 10:37
@tommyyu @sfqxx @zsy0226 @Ewan-Ahiouy @元豪 @陈尚涵 @柿子饼同学 @学习编程中的Ben @高山
退役了{:10_266:}开始搞化竞了 失踪人口回归{:10_257:}
失踪人口回归{:10_257:} NB!! 谢谢 谢谢 6 厉害！！！ 谢谢 感谢分享，看不懂嘻嘻{:5_108:} 1 zhangjinxuan 发表于 2024-12-7 10:37
@tommyyu @sfqxx @zsy0226 @Ewan-Ahiouy @元豪 @陈尚涵 @柿子饼同学 @学习编程中的Ben @高山
sry来晚啦~ 顶一顶 {:10_254:}{:10_254:} {:10_256:}学习一下
页:
[1]
2