浅谈数位 DP

zhangjinxuan

浅谈数位 DP

Update Logs:
- [2024/11/26 23:00] 完成了未完成的部分。

更好的阅读体验。

本文章的作者与上处链接所指向的文章的作者是同一个人。

前言

---

本文全方面讲解了数位 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 写法，并且介绍部分简单的拓展。

希望您能在阅读下文之前评分和收藏，谢谢！

                               
登录/注册后可看大图

zhangjinxuan

纯胡说，没什么东西

zhangjinxuan

@tommyyu @sfqxx @zsy0226 @Ewan-Ahiouy @元豪 @陈尚涵 @柿子饼同学 @学习编程中的Ben @高山

柿子饼同学

想起来之前做过的一个比较恶心的
CF1194G
哎, 退役了

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. /*
   
5.     首先把 x / y
   
6.     换成  k*dx / k*dy
   
7.     枚举的是 x 和 y, 但是我们必须保证 k 相同, 并且 x, y 分别被 dx, dy 整除
   
8.     于是乎我们状态中存下来 前 pos 位的 x, y 分别除以 dx, dy 的余数, 再存 x, y 中出现的数字
   
9.     答案就是 余数都是 0 并且出现数字符合题意的状态的答案之和
   
10. 
    
11.     举个栗子:
    
12.     这个竖式的答案是 k, 我们按位枚举 k 的位数(这样保证了 k 相同), 现在 k 这一位是 i
    
13.        ______________
    
14.     dx )  A   B   j ...这里是 x 的位置, 在做除法, 枚举 x 的这一位为 j
    
15.         _________
    
16.     上一次的余数 = rx
    
17.     那么这次的余数就是 (rx*10 + j) - i*dx, 这个余数要在 [0, dx) 的范围
    
18.     再用状压把这次出现的数位 j 打上去即可
    
19. */
    
20. 
    
21. const int N = 102;
    
22. const int P = 998244353;
    
23. 
    
24. // f(pos, sx, sy, rx, ry) 代表前 pos 位, x, y 带有的数字状态, x, y 除以 dx, dy 的余数
    
25. int f[N][16][16][10][10];
    
26. string s;
    
27. int num[N], n;
    
28. int dx, dy;
    
29. int ans;
    
30. // 分数值一样的一起算, 不然会算重
    
31. // 情况最多的是 1/2 = 2/4 = 3/6 = 4/8 共 4 组
    
32. // tot 是组数
    
33. int choice[2][4], tot;
    
34. 
    
35. // type == 0 表示是 x, type == 1 表示是 y
    
36. int Add(int st, int d, int type){
    
37.     for(int i = 0; i < tot; i++){
    
38.         if(choice[type][i] == d){
    
39.             st |= (1 << i);
    
40.             return st;
    
41.         }
    
42.     }
    
43.     return st;
    
44. }
    
45. 
    
46. int dfs(int pos, int sx, int sy, int rx, int ry, bool lim){
    
47.     if(pos == n + 1){
    
48.         // 没有余数, 并且 x 中出现 dx, y 中出现了 dy
    
49.         if(!rx && !ry && (sx & sy)) return 1;
    
50.         return 0;
    
51.     }
    
52. 
    
53.     auto& cur = f[pos][sx][sy][rx][ry];
    
54. 
    
55.     if(!lim && ~cur) return cur;
    
56. 
    
57.     int res = 0;
    
58.     int up = 9;
    
59.     int newrx, newry;
    
60.     if(lim) up = num[pos];
    
61. 
    
62.     // 枚举 k 的数位(竖式答案), x / dx == y / dy == k
    
63.     for(int ki = 0; ki < 10; ki++){
    
64. 
    
65.         // 枚举 x 的数位(竖式被除数)
    
66.         for(int xi = 0; xi <= up; xi++){
    
67.             newrx = (rx*10 + xi) - ki*dx;
    
68. 
    
69.             if(newrx < 0) continue;
    
70.             if(newrx >= dx) break;
    
71. 
    
72.             // 枚举 y 的数位, 流程是一样的
    
73.             // y 比 x 小, 所以不用管
    
74.             for(int yi = 0; yi < 10; yi++){
    
75.                 newry = (ry*10 + yi) - ki*dy;
    
76. 
    
77.                 if(newry < 0) continue;
    
78.                 if(newry >= dy) break;
    
79. 
    
80.                 res = (res + dfs(pos + 1, Add(sx, xi, 0), Add(sy, yi, 1), newrx, newry, lim && (xi == up))) % P;
    
81.             }
    
82.         }
    
83.     }
    
84. 
    
85.     if(!lim) cur = res;
    
86.     return res;
    
87. }
    
88. 
    
89. int main(){
    
90.     ios::sync_with_stdio(0);
    
91.     cin.tie(0);
    
92.    
    
93.     cin >> s;
    
94.     n = s.size();
    
95.     for(int i = 1; i <= n; i++){
    
96.         num[i] = s[i - 1] - '0';
    
97.     }
    
98. 
    
99.     // dx == dy 的情况, 这时每个数都满足条件, ans += num
    
100.     for(int i = 1; i <= n; i++){
     
101.         ans = (ans*10 + num[i]) % P;
     
102.     }
     
103. 
     
104.     // 强制令 x > y (即 dx > dy), 这样只需要满足 x <= n 就行了
     
105.     for(int i = 1; i < 10; i++){
     
106.         for(int j = 1; j < i; j++){
     
107.             if(__gcd(i, j) != 1) continue;
     
108. 
     
109.             memset(f, -1, sizeof(f));
     
110.             for(tot = 0; tot < 4; tot++){
     
111.                 if(i*(tot + 1) > 9) break;
     
112.                 choice[0][tot] = i*(tot + 1);
     
113.                 choice[1][tot] = j*(tot + 1);
     
114.             }
     
115.             dx = i, dy = j;
     
116. 
     
117.             long long w = (dfs(1, 0, 0, 0, 0, 1)*2ll) % P;
     
118. 
     
119.             ans = (ans + w) % P;
     
120.         }
     
121.     }
     
122. 
     
123.     cout << ans;
     
124.    
     
125.     return 0;
     
126. }

复制代码

柿子饼同学

noip分数线怎么还变高了...
哎这下完了

tommyyu

zhangjinxuan 发表于 2024-12-7 10:37
@tommyyu @sfqxx @zsy0226 @Ewan-Ahiouy @元豪 @陈尚涵 @柿子饼同学 @学习编程中的Ben @高山

退役了开始搞化竞了

sfqxx

失踪人口回归

baimups

失踪人口回归

zyx2012

NB!!

123456qax

谢谢

123456qax

谢谢

OKMY

6

学习编程中的Ben

厉害！！！

123456qax

谢谢

6bingame

感谢分享，看不懂嘻嘻

zhangjinxuan

1

Ewan-Ahiouy

zhangjinxuan 发表于 2024-12-7 10:37
@tommyyu @sfqxx @zsy0226 @Ewan-Ahiouy @元豪 @陈尚涵 @柿子饼同学 @学习编程中的Ben @高山

sry来晚啦~

sfqxx

顶一顶

trinityee

方少恒

学习一下