数位dp部分题解
前言
最近学了一种新的数位dp的状态表示，打算应用到以前做过的数位dp的题目。如果我们对数$N$进行数位dp，以前的状态定义$f(i,j)$表示所有数位大小为$i$且最高位是数字$j$的数的个数，如果还有其他约束条件那么再补充相应的状态即可。而新的状态定义则是$f(i,1)$和$f(i,0)$，其中$f(i,1)$表示所有数位大小为$i$且值不超过$N \bmod 10^i$的数的数量，相应的$f(i,0)$表示所有数位大小为$i$且值超过$N \bmod 10^i$的数的数量。其中$N \bmod 10^i$表示$N$在十进制下的最低有效$i$位数字构成的值，例如$123456789$的最低有效$6$位数字构成的值就是$456789$。
下面通过几道题目来运用这种新的做法。
数字游戏
科协里最近很流行数字游戏。
某人命名了一种不降数，这种数字必须满足从左到右各位数字呈非下降关系，如 $123$，$446$。
现在大家决定玩一个游戏，指定一个整数闭区间 $[a,b]$，问这个区间内有多少个不降数。
输入格式
输入包含多组测试数据。
每组数据占一行，包含两个整数 $a$ 和 $b$。
输出格式
每行给出一组测试数据的答案，即 $[a,b]$ 之间有多少不降数。
数据范围
$1 \le a \le b \le 2^{31}-1$
输入样例：
1 9 1 19
输出样例：
9 18
解题思路
定义状态$f(i,j,k)$满足以下条件的整数$n$的数量：
- $n$的数位大小为$i$，$0 \leq n < 10^i$。
- 若$n \leq N \bmod 10^i$，则$j=1$；否则$j=0$。
- $n$的最高位是数字$k$。
- $n$从左到右各位数字呈非递降。
对于确定的状态$f(i,j,k)$，我们可以枚举数位是$i+1$的数的最高位是哪个数字（记作$u$）来转移到数位大小是$i+1$的状态，状态转移方程就是$$f(i,j,k) \longrightarrow f(i+1,\ u < p_i \ \operatorname{or} \ u = p_i \ \operatorname{and} \ j, \ u) \quad (u \leq k)$$
其中$p_i$表示的是$N$在十进制下从低位（第$0$位）开始的第$i$位上的数字。然后再考虑一下是否需要处理前导$0$的情况，可以发现包含前导$0$并不会影响答案，因为包含前导$0$的数仍然满足从左到右各位数字呈非下降关系。因此最终答案就是$\sum\limits_{i=0}^{9}{f(sz,1,i)}$，其中$sz$是$N$在十进制下的数位个数。
AC代码如下，时间复杂度为$O(10^2 \cdot \log{N})$：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int N = 12; 5 6 int f[N][2][10]; 7 int p[N], sz; 8 9 int get(int x) { 10 if (!x) return 1; 11 sz = 0; 12 while (x) { 13 p[sz++] = x % 10; 14 x /= 10; 15 } 16 memset(f, 0, sizeof(f)); 17 for (int i = 0; i <= 9; i++) { 18 f[1][i <= p[0]][i]++; 19 } 20 for (int i = 1; i < sz; i++) { 21 for (int j = 0; j <= 1; j++) { 22 for (int k = 0; k <= 9; k++) { 23 for (int u = 0; u <= k; u++) { 24 f[i + 1][u < p[i] || u == p[i] && j][u] += f[i][j][k]; 25 } 26 } 27 } 28 } 29 int ret = 0; 30 for (int i = 0; i <= 9; i++) { 31 ret += f[sz][1][i]; 32 } 33 return ret; 34 } 35 36 int main() { 37 int a, b; 38 while (~scanf("%d %d", &a, &b)) { 39 printf("%d\n", get(b) - get(a - 1)); 40 } 41 42 return 0; 43 }
Windy数
Windy 定义了一种 Windy 数：不含前导零且相邻两个数字之差至少为 $2$ 的正整数被称为 Windy 数。
Windy 想知道，在 $A$ 和 $B$ 之间，包括 $A$ 和 $B$，总共有多少个 Windy 数？
输入格式
共一行，包含两个整数 $A$ 和 $B$。
输出格式
输出一个整数，表示答案。
数据范围
$1 \le A \le B \le 2 \times 10^9$
输入样例1：
1 10
输出样例1：
9
输入样例2：
25 50
输出样例2：
20
解题思路
定义状态$f(i,j,k)$满足以下条件的整数$n$的数量：
- $n$的数位大小为$i$，$0 \leq n < 10^i$。
- 若$n \leq N \bmod 10^i$，则$j=1$；否则$j=0$。
- $n$的最高位是数字$k$。
- $n$的所有相邻数位上的数相差至少为$2$。
状态转移方程为$$f(i,j,k) \longrightarrow f(i+1,\ u < p_i \ \operatorname{or} \ u = p_i \ \operatorname{and} \ j, \ u) \quad (|u - k| \geq 2)$$
这里就需要处理前导$0$的情况，这是因为前导$0$可能会使得数不满足相邻两个数字之差至少为$2$这个条件，比如$15$是满足条件的，而$015$就不满足条件了。为了避免前导$0$的情况，这时我们只需分别考虑$1 \sim sz$每一个数位大小，统计最高位的数字不是$0$的情况即可，有$\sum\limits_{i=1}^{sz}{\sum\limits_{j=1}^{9}{f(i,1,j)}}$。除此之外，当数位大小不足$sz$，即$i < sz$时，我们默认往高位补$0$（并非添加前导$0$），这时不管最低$i$位怎么填数字，整个数都不会超过$N$，因此还需要加上$\sum\limits_{i=1}^{sz-1}{\sum\limits_{j=1}^{9}{f(i,0,j)}}$。因此最终答案就是$$\sum\limits_{i=1}^{sz}{\sum\limits_{j=1}^{9}{f(i,1,j)}} + \sum\limits_{i=1}^{sz-1}{\sum\limits_{j=1}^{9}{f(i,0,j)}}$$
AC代码如下，时间复杂度为$O(10^2 \cdot \log{N})$：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int N = 15; 5 6 int f[N][2][10]; 7 int p[N], sz; 8 9 int get(int x) { 10 if (!x) return 0; 11 sz = 0; 12 while (x) { 13 p[sz++] = x % 10; 14 x /= 10; 15 } 16 memset(f, 0, sizeof(f)); 17 for (int i = 0; i <= 9; i++) { 18 f[1][i <= p[0]][i]++; 19 } 20 for (int i = 1; i < sz; i++) { 21 for (int j = 0; j <= 1; j++) { 22 for (int k = 0; k <= 9; k++) { 23 for (int u = 0; u <= 9; u++) { 24 if (abs(k - u) >= 2) f[i + 1][u < p[i] || u == p[i] && j][u] += f[i][j][k]; 25 } 26 } 27 } 28 } 29 int ret = 0; 30 for (int i = 1; i <= sz; i++) { 31 for (int j = 1; j <= 9; j++) { 32 ret += f[i][1][j]; 33 if (i < sz) ret += f[i][0][j]; 34 } 35 } 36 return ret; 37 } 38 39 int main() { 40 int a, b; 41 scanf("%d %d", &a, &b); 42 printf("%d", get(b) - get(a - 1)); 43 44 return 0; 45 }
数字游戏 II
由于科协里最近真的很流行数字游戏。
某人又命名了一种取模数，这种数字必须满足各位数字之和 $mod\ N$ 为 $0$。
现在大家又要玩游戏了，指定一个整数闭区间 $[a.b]$，问这个区间内有多少个取模数。
输入格式
输入包含多组测试数据，每组数据占一行。
每组数据包含三个整数 $a,b,N$。
输出格式
对于每个测试数据输出一行结果，表示区间内各位数字和 $mod\ N$ 为 $0$ 的数的个数。
数据范围
$1 \le a,b \le 2^{31}-1$,
$1 \le N < 100$
输入样例：
1 19 9
输出样例：
2
解题思路
定义状态$f(i,j,k)$满足以下条件的整数$n$的数量：
- $n$的数位大小为$i$，$0 \leq n < 10^i$。
- 若$n \leq N \bmod 10^i$，则$j=1$；否则$j=0$。
- $n$的各位数字之和模$m$为$k$。
状态转移方程为$$f(i,j,k) \longrightarrow f\left(i+1,\ u < p_i \ \operatorname{or} \ u = p_i \ \operatorname{and} \ j, \ (u+k) \bmod m\right)$$
可以发现不需要处理前导$0$的情况，因为对$0$求和后并不会影响模$m$的结果。因此最终答案就是$f(sz, 1, 0)$。
AC代码如下，时间复杂度为$O(10 \cdot m \cdot \log{N})$：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int N = 15, M = 110; 5 6 int a, b, m; 7 int f[N][2][M]; 8 int p[N], sz; 9 10 int get(int x) { 11 if (!x) return 1; 12 sz = 0; 13 while (x) { 14 p[sz++] = x % 10; 15 x /= 10; 16 } 17 memset(f, 0, sizeof(f)); 18 for (int i = 0; i <= 9; i++) { 19 f[1][i <= p[0]][i % m]++; 20 } 21 for (int i = 1; i < sz; i++) { 22 for (int j = 0; j <= 1; j++) { 23 for (int k = 0; k < m; k++) { 24 for (int u = 0; u <= 9; u++) { 25 f[i + 1][u < p[i] || u == p[i] && j][(u + k) % m] += f[i][j][k]; 26 } 27 } 28 } 29 } 30 return f[sz][1][0]; 31 } 32 33 int main() { 34 while (~scanf("%d %d %d", &a, &b, &m)) { 35 printf("%d\n", get(b) - get(a - 1)); 36 } 37 38 return 0; 39 }
不要62
杭州人称那些傻乎乎粘嗒嗒的人为 $62$（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有 $4$ 或 $62$ 的号码。例如：$62315,73418,88914$ 都属于不吉利号码。但是，$61152$ 虽然含有 $6$ 和 $2$，但不是 连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照号区间 $[n,m]$，推断出交管局今后又要实际上给多少辆新的士车上牌照了。
输入格式
输入包含多组测试数据，每组数据占一行。
每组数据包含一个整数对 $n$ 和 $m$。
当输入一行为“0 0”时，表示输入结束。
输出格式
对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。
数据范围
$1 \le n \le m \le 10^9$
输入样例：
1 100 0 0
输出样例：
80
解题思路
定义状态$f(i,j,k)$满足以下条件的整数$n$的数量：
- $n$的数位大小为$i$，$0 \leq n < 10^i$。
- 若$n \leq N \bmod 10^i$，则$j=1$；否则$j=0$。
- $n$的最高位是数字$k$。
- $n$中不含有数字$4$以及相邻的$62$。
状态转移方程为$$f(i,j,k) \longrightarrow f(i+1,\ u < p_i \ \operatorname{or} \ u = p_i \ \operatorname{and} \ j, \ u) \quad (u \ne 4 \ \operatorname{and} \ \neg (u=6 \ \operatorname{and} \ k=2 ))$$
可以发现不需要处理前导$0$的情况，因此最终答案就是$\sum\limits_{i=0}^{9}{f(sz,1,i)}$。
AC代码如下，时间复杂度为$O(10^2 \cdot \log{N})$：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int N = 15; 5 6 int f[N][2][N]; 7 int p[N], sz; 8 9 int get(int x) { 10 if (!x) return 1; 11 sz = 0; 12 while (x) { 13 p[sz++] = x % 10; 14 x /= 10; 15 } 16 memset(f, 0, sizeof(f)); 17 for (int i = 0; i <= 9; i++) { 18 if (i != 4) f[1][i <= p[0]][i]++; 19 } 20 for (int i = 1; i < sz; i++) { 21 for (int j = 0; j <= 1; j++) { 22 for (int k = 0; k <= 9; k++) { 23 for (int u = 0; u <= 9; u++) { 24 if (u == 6 && k == 2 || u == 4) continue; 25 f[i + 1][u < p[i] || u == p[i] && j][u] += f[i][j][k]; 26 } 27 } 28 } 29 } 30 int ret = 0; 31 for (int i = 0; i <= 9; i++) { 32 ret += f[sz][1][i]; 33 } 34 return ret; 35 } 36 37 int main() { 38 int a, b; 39 while (scanf("%d %d", &a, &b), a) { 40 printf("%d\n", get(b) - get(a - 1)); 41 } 42 43 return 0; 44 }
参考资料
F - Nim Editorial：https://atcoder.jp/contests/abc317/editorial/7047