本文目的
距离上一次认认真真地写算法内容,已经过去一年多了,真是一看吓一跳,时间过得真快啊。过去的大半年没有怎么写题,都在准备托福和 GRE ,最近打算重新训练了,所以我把知识点都认认真真地过了一遍,并将各种原理、细节重新理解,将各种公式再次推导了一遍,不得不说收获良多,改天再展开细说。
复习到数位 DP 这部分时,想起来这是我在去年就想总结的内容。数位 DP 其实不算是很难的内容啦,很多时候只要会用模板就行。但如果学习的时候没有将填数字的原理和过程搞清楚的话,题目条件有些变化,可能就会在一些细节和边界处理上卡很久,写起来就底气不够了。
我以前在学习数位 DP 时,就处于“知其然而不知其所以然”的程度,题目稍微换个问法,我就要花很长时间设计思路、调试代码。经过了这么久的学习,对于数位 DP 也有了自己的一些见解。我一直都在践行费曼学习法,将学到的东西通俗易懂、逻辑通顺地输出,既能让自己的知识脉络更加清晰,又或许能够帮助到别人。这次重新训练算法,为了倒逼自己的学习质量,我打算连续写几篇关于算法学习的文章,于是就有了标题中的“系列”。
建议读者有一定的 DP 基础 ,比如对于基础的背包和线性 DP 问题,知道如何设计状态和转移。本文包含的习题都是比较经典的学习数位 DP 的题目,难度从易到难(我自己排的)。除了最后一道题包含一些额外的数论知识(也不难,有关最大公倍数的一些性质),其余题目都没有结合其它复杂算法。因此读者可以通过这些题目专注于学习数位 DP 的解题思路和代码实现,而不需要其它前置的复杂算法知识。
另外文中很多题目的代码在时空上都有优化的空间,或者有更加巧妙的做法。但本文旨在帮助数位 DP 入门级的同学理解其原理、学习典型的解题思路以及掌握基本的代码实现,因此我会尽可能地保持思路和方法的一致性,让数位 DP 原理更直观,细节更好把握,至于代码,能 AC 就好。
数位 DP 是什么
数位 DP 首先是一种 DP ,我们可以类比一下其它 DP 问题。比如背包问题,初始时背包为空,然后对于每个(种)物品作出抉择(取或不取,取多少个),将每次抉择都记录成当前的状态,两个(种)相邻物品被抉择之后的状态之间会涉及到状态的转移,而终点是对所有物品都作出了抉择,我们可以从终点里选出符合条件的结果作为答案。
在这个角度看,数位 DP 的过程是 一样的 。如下图,我们有一列数位,左边为高位,右边为低位,这一列数位对应背包,初始时这一列数位都为空,然后我们从高位到低位依次对每个数位进行抉择(填什么数),在两个数位被抉择后的状态进行转移,终点就是对所有数位都作出了抉择,最后我们在终点里统计符合条件的结果作为答案。
数位 DP 一般用于解决 统计在某个范围内符合特定条件的数的个数(这个范围一般是非负的) 这样的问题。最朴素的做法是枚举其范围内所有数,然后对于每个数都检验其是否符合条件。进一步的优化思路是,如果符合特定条件的数比较容易计算,且分布比较稀疏,那么就枚举一下这样的数,看看有多少个是在题目给定的范围内。
但是如果范围很大呢? int
和 long long
范围内就已经几乎无法用朴素的枚举来做了,更别说 1000 位以上的数了。我们来看一个具体的问题:统计一下在 $100$ 到 $2$ 的 $30$ 次方的范围内有多少个数满足数位上的数字之和为 $sum$ 。
显然范围是 $100$ 到 $2$ 的 $30$ 次方,条件是各位数位之和为 $sum$ 。枚举是没法枚举了,于是我们会尝试 将数的每个数位拆分 ,一位一位地看,本题涉及的数最多为十个数位( $2^{30}$ 为十位)。如下图,以十进制为例,假设我们已经填入的数字成为了一个数 $a$ ,当我们在其末尾填入一个新数字 $c$ 时,形成了一个新数 $b$ ,其中 $b=a\times 10+c$ 。
接着,我们对于所有组成的数,尝试着 针对题目的条件,用若干变量表示其当前的状态 ,比如本题,我们可以用 $cur\_sum$ 表示其当前已经填入的数字组成的数的各个数位之和。如下图,如果当前数 $x=145$ ,其状态为 $cur\_sum=10$ 在末尾加上了一个数字 $3$ ,那么新数就是 $y=x\times 10+3=1453$ ,其状态变化为 $cur\_sum’=cur\_sum+3=13$ 。
像这样,如果可以用当前数的状态以及新填入的数字来计算新数的状态的话,那么我们就可以一位一位地填数,直到填满数位的位置,而答案则可以在填数过程中被统计出来。对于这道题,就是在填完数位之后,统计一下满足 $cur\_sum==sum$ 的数的个数即可。
这样我们就不需要枚举实际数值,而是枚举数位,从而大大降低了时间复杂度。以上就是数位 DP 是解决什么问题以及大致过程,接下来会详细讲解数位 DP 实现思路。
实现思路
计数方法
在数位 DP 中,一般都会涉及到一个数值范围 $[l,r]$ ,问在这个范围内有多少个数满足要求。为了计算方便,如下图,我们往往会通过 $Get(r)-Get(l-1)$ 来得到答案,其中函数 $Get(x)$ 就是数位 DP 的实现,返回在 $[0,x]$ 的范围内,满足题目要求的数的个数。
事先说明,在初学时为了更好地把握细节,减少出错,我在接下来的推导会做两件事:
- 特判一下 $0$ 这个数,在数位 DP 中,只计算 $[1,x]$ 范围内符合要求的数的个数,这样在填数位的时候,保证组成的数都是正数。
- 不填前导零,也就是说,每个数的最高位必然是一个正数。
填数过程(重点)
我们再来看看在数位 DP 中是如何填数的,这是最细节、最抽象的部分,下面写得比较详细, 希望读者可以完全理解以下过程 ,只要理解了这个过程,剩下的就只有针对题目设计一些状态即可。
在填数过程中,我们遵循以下原则:
- 从高位往低位枚举数位。
- 若在某个数位填入一个数字,那么它后面所有数位都一定要填上数字。这样规定的目的是避免重复。如下图,比如我们在较高的连续数位中填入了 $145$ ,那么最终的数一定是 $145?????$ ,如果最终的数是 $145$ ,则应该在最低的三位填上。
- 保证填入的数字组成的数不能大于 $x$ 。
我们用上面的例题展示一下填数过程:令 $x=324783729$ ,求出在 $[1,x]$ 之间有多少个数满足数位上的数字之和为 $16$ 。
我们从第一位开始看,我们发现要么不填,如果填的话,可以填入 $1,2,3$ ,否则形如 $4????????$ 这样的数,一定在大于 $x$ 的。
然后我们来到了第二位,我们也可以不填,但如果要填数的话,可以填入什么数呢?我们来分类讨论一下:
-
如果在第一位中没有填数,意味着在这一位中填入的数字是最终组成的数的最高位,而且这一位可以填入 $[1,9]$ 任意一个数,因为无论是 $1???????$ 还是 $9???????$ (都只有 $8$ 位),都不会超过 $x=324783729$ (共有 $9$ 位)。
-
如果在第一位中填过了数,又可以再分类讨论一下:
-
如果第一位填入了 $1$ 或 $2$ ,那么在第二位可以填入 $[0,9]$ 任意一个数,因为 $19???????$ 和 $29???????$ 都是严格小于 $x$ 的。
- 如果第一位填入了 $3$ ,此时第二位就只能填 $[0,2]$ 之间的数了,因为如果填入了大于 $2$ 的数,比如 $33???????$ 或 $37???????$ ,都会大于 $x$ 。
接着,假设我们处理到了第七位,我们可以填入什么数呢?再来分析一下:
- 如果在之前没有填过数,那么这一位就是最高位,可以填入 $[1,9]$ 的任意一个数,最终的数值可能是 $1??, 2??, …, 9??$ 。
- 如果在之前填过数,又可以分成几种情况:
- 如果之前的数位没有填满,意味着形成的数的位数一定是小于九位,于是在第七位中可以填入 $[0,9]$ 任意一个数。
- 如果之前每个数位都填上了数:
- 如果存在某一数位上的数字严格小于 $x$ 对应数位的数字,意味着这个数一定严格小于 $x$ ,在第七位中可以填入 $[0,9]$ 任意一个数。
- 如果前面所有数位的数字都和 $x$ 的数位的数字相同,那么就只能填入 $[0,7]$ 中的数字了。
我们将以上过程总结成抽象的规律,假设当前正在对第 $i$ 位进行抉择(注意:为了方便后续的代码实现,我们规定 $i$ 从 $0$ 开始,如上述的第一位对应第 $i=0$ 位):
-
如果 $i=0$ :只能填入 $[1,num[i]]$ ,其中 $num[i]$ 为 $x$ 的最高位上的数字。
-
如果 $i>0$ :
- 如果第 $i$ 位的前面都没有填入过数,那么这一位就是最高位,那么可以填入 $[1,9]$ 任意一个数,因为以这一位为最高位的数,不可能超过 $x$ 。
- 如果第 $i$ 位的前面填过且没有填满数位,说明这一位不是组成的数的最高位,而且组成的数一定是严格小于 $x$ 的,因为数位比 $x$ 少,因此可以填入 $[0,9]$ 任意一个数。
- 如果第 $i$ 位的前面填过且填满了数位:
- 如果第 $i$ 位的前面存在某个数位的数字小于 $x$ 对应的数位,说明组成的数一定严格小于 $x$ ,因此可以填入 $[0,9]$ 任意一个数。
- 否则,第 $i$ 位的前面每个数位上的数都和 $x$ 前 $i-1$ 位相等,在第 $i$ 位就只能填入 $[0,num[i]]$ 中的数字,其中 $num[i]$ 是 $x$ 在第 $i$ 位上的数字。
将以上的过程重新归一下类,以便总结一下可以填入数字的范围:
- 如果当前填的数位(第 $i$ 位)前面没填过数,那么这就是最终组成的数的最高位,要从 $1$ 开始枚举,如果当前是整个数列的首位( $i=0$ ),则枚举到 $x$ 最高位上的数字 $num[i]$ ,否则可以枚举到 $9$ 。
- 如果当前填的数位(第 $i$ 位)之前没填满,或者填满了但存在某一位的数小于 $x$ 对应数位的数,则已经确定最终数是严格小于 $x$ ,那么可以填入的数字范围是 $[0,9]$ 。
- 剩下的情况就是第 $0$ 到第 $i-1$ 位都填满了,且每一位都和 $x$ 的 $[0,i-1]$ 位相等,此时在第 $i$ 位就只能填入 $[0,num[i]]$ 中的数字了,其中 $num[i]$ 为 $x$ 的第 $i$ 位上的数字。
接着,我们可以引入一个变量 $limit$ ,其意义为: 当前数位之前填入的所有数,是否都和 $x$ 对应数位的数相等 (通俗点说就是“是否都顶着 $x$ 对应数位的上限”)。上述的第一种情况,填入最终组成的数的最高位后,将对 $limit$ 进行初始化,稍后马上进行解释。当 $limit=0$ 时,代表上述第二种情况,没有达到 $x$ 的上限,我们可以在第 $i$ 位填入 $[0,9]$ 中的数字;当 $limit=1$ 时,代表上述第三种情况,已经达到 $x$ 的上限,我们只能在第 $i$ 位填入 $[0,num[i]]$ 中的数字,其中 $num[i]$ 为 $x$ 的第 $i$ 位上的数字。
我们思考一下,填完第 $i$ 位的数字后,当前的 $limit$ 该如何转移到第 $i+1$ 位的 $limit’$ 呢?同样地,分类讨论一下:
- 如果当前 $limit=0$ ,那么第 $i$ 位无论填入什么数,前面都已经出现某一位上的数字不等于 $x$ 的对应数位上的数字,最终的数都是严格小于 $x$ 的,所以第 $i+1$ 位的 $limit’$ 一定为 $0$ 。
- 如果当前 $limit=1$ :
- 如果当前填入的数小于 $num[i]$ ,从此往后的数位前面一定会存在至少一个(比如当前的第 $i$ 位)数位上的数字不等于 $x$ 的对应数位上的数字,那么第 $i+1$ 位的 $limit’$ 为 $0$ (也就是说最终组成的数一定是严格小于 $x$ 的)。
- 如果当前填入的数等于 $num[i]$ ,那么依然是“顶着 $x$ 对应数位的上限”,第 $i+1$ 位的 $limit’$ 为 $1$ 。
插图
最后,我们再看看在填入一个数的最高位时,如何定义 $limit$ 。这就比较容易了:
- 如果填的是第 $0$ 位:
- 如果填入的数小于 $x$ 的最高位 $num[0]$ ,$limit=0$ 。
- 如果填入的数等于 $x$ 的最高位 $num[0]$ ,$limit=1$ 。
- 如果填的数位不是第 $0$ 位,那么前面的数位没有数字,自然就不满足都与 $x$ 对应数位上的数相等这个条件,那么 $limit=0$ 。
至此,枚举数位的填数过程以及维护 $limit$ 变量的原理就已经叙述得差不多了,这部分是数位 DP 的精髓和重点,很多初学者在细节上理解得模模糊糊也是在这一部分。如果不太理解,建议多看几遍,一定要理解透彻。这个过程写成代码大概像这个样子(建议对照着上面的分类讨论,理解一下填入数字的范围以及 $limit$ 的转移计算):
// n 为数位长度
for (int i = 0; i < n; i++) {
// 枚举数位,一共有 n 个位置
for (int c = 1; c <= (i == 0 ? num[i] : 9); c++) {
// 在第 i 位填入 c ,这是最终数的最高位( c 从 1 开始枚举)
// 定义当前的 limit=(i==0&&c==num[i])
}
for (int limit = 0; limit <= 1; limit++) {
for (int c = 0; c <= (limit ? num[i] : 9); c++) {
// 在第 i 位填入 c ,这不是最终数的最高位( c 从 0 开始枚举)
// 填入后这个数后, limit' 为 (limit&&c==num[i])
}
}
}
状态设计和转移
这一部分,和其它的 DP 就大同小异了。别忘了,上面用于举例的问题还没解决:求出在 $[1,x]$ 之间有多少个数满足数位上的数字之和 $sum$ 为 $16$ ,其中 $x=324783729$ 。
在前面我们说过要 针对题目的条件,用若干变量表示其当前的状态 ,那么这题的条件是“数位上的数字之和”,因此我们用一个变量 $cur\_sum$ 表示已经填入的数字之和。那么我们可以写出 DP 数组 $dp[i,limit,cur\_sum]$ ,其代表的集合定义为对前 $i$ 位作出抉择后,前 $i$ 位是否和 $x$ 的前 $i$ 位相等(取决于 $limit$ ),且填入所有数字之和为 $cur\_sum$ 的所有方案,其表示的属性是数量。
转移过程写成代码如下:
// dp[i][limit][cur_sum]
// 其中 n 为数位长度, max_sum 为数位上的数字之和的最大值
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(2, vector<int>(max_sum + 1)));
for (int i = 0; i < n; i++) {
for (int c = 1; c <= (i == 0 ? num[i] : 9); c++) {
// 为什么这里和下面都是 i+1 呢
// 代码块下面给了说明
dp[i + 1][i == 0 && c == num[i]][c] += 1;
}
for (int limit = 0; limit <= 1; limit++) {
for (int cur_sum = 0; cur_sum <= max_sum; cur_sum++) {
for (int c = 0; c <= (limit ? num[i] : 9); c++) {
if (cur_sum + c <= max_sum) {
// 如果当前数位上的数字之和加上新填上的数不超过 max_sum
// 保证数组不越界
dp[i + 1][limit && c == num[i]][cur_sum + c] += dp[i][limit][cur_sum];
}
}
}
}
}
注意代码块中注释的地方,可能初学者会有些迷惑为什么是 $i+1$ ,这部分并不是数位 DP 的内容,这是 DP 的不同实现方式,是“从之前的第 $i-1$ 层状态得到当前的第 $i$ 层状态”,还是“从当前的第 $i$ 层状态推出后面的第 $i+1$ 层状态”。如果实在不懂,可以暂时记住这个写法,将学习重点放在数位 DP 上。但两种实现方式都推荐掌握,二者 没有任何本质区别 ,绝大部分题目两种写法都适用,但在某些场景中,其中一种的代码可能会更加好写。
统计答案
最后统计答案时,只需要在所有数位抉择之后, $limit$ 取值为 $0$ 或 $1$ 均可(若 $limit=1$ ,则说明这个数就是 $x$ ),状态恰好为题目条件的集合中,进行统计即可。
在本题中,最终答案就是 $dp[n][0][sum]+dp[n][1][sum]$ 。
代码实现和例题练习
好了,原理、实现思路都已经讲完了,上一部分是全文的重点,后面都是基于以上思路进行实践了。
在数位 DP 中,我们经常会用到的两种操作:
- 将数按位拆分成数组
- 将字符串表示的数减一
虽然比较简单,但为了让读者将更多精力放在理解数位 DP 的枚举和填数过程上,这里都给出代码实现:
// 将 k 按位拆分,最高位保存在 num[0]
vector<int> num;
while (k > 0) {
num.emplace_back(k % 10);
k /= 10;
}
// k 一共有 n 位
int n = (int) num.size();
reverse(num.begin(), num.end());
// 字符串 s 代表一个数(数位较长,必须用字符串读入)
// 将这个数减一,更新到 s 中,最高位保存在 s[0]
// 就是个高精度减法
reverse(s.begin(), s.end());
int i = 0;
while (s[i] == '0') {
++i;
}
--s[i];
--i;
while (i >= 0) {
s[i] = '9';
--i;
}
while ((int) s.size() > 1 && s.back() == '0') {
s.pop_back();
}
reverse(s.begin(), s.end());
AcWing 1084. 数字游戏 II
题目链接: AcWing 1084. 数字游戏 II
题意:
这题是上面讲解例题的变形,问在 $[l,r]$ 之间有多少个数的数位之和对 $m$ 取模为 $0$ 。
解题思路:
用 $dp[i,limit,cur\_sum]$ 表示前 $i$ 个数位已经做过抉择,当前数位之和为 $cur\_sum$ 的所有方案,最终答案为 $dp[n,0,sum]+dp[n,1,sum]$ ,其中 $(sum\mod m==0)$ 。
注意事项:
注意本题的 $l,r$ 都是正数,如果 $Get()$ 的第一个参数为 $0$ ,直接返回 $0$ 即可。前面说过,我这里给出的 DP 过程只处理正数,如果 $l,r$ 有可能取到 $0$ ,特判一下 $0$ 即可。后面的代码不再重复说明。
代码实现:
#include <bits/stdc++.h>
using namespace std;
int Get(int k, int m) {
if (k == 0) {
return 0;
}
vector<int> num;
while (k > 0) {
num.emplace_back(k % 10);
k /= 10;
}
int n = (int) num.size();
reverse(num.begin(), num.end());
const int max_sum = 100;
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(2, vector<int>(max_sum + 1)));
for (int i = 0; i < n; i++) {
for (int x = 1; x <= (i == 0 ? num[i] : 9); x++) {
dp[i + 1][i == 0 && x == num[i]][x] += 1;
}
for (int limit = 0; limit <= 1; limit++) {
for (int cur_sum = 0; cur_sum <= max_sum; cur_sum++) {
for (int x = 0; x <= (limit ? num[i] : 9); x++) {
if (cur_sum + x <= max_sum) {
dp[i + 1][limit && x == num[i]][cur_sum + x] += dp[i][limit][cur_sum];
}
}
}
}
}
int res = 0;
for (int sum = 0; sum <= max_sum; sum++) {
if (sum % m == 0) {
res += dp[n][0][sum] + dp[n][1][sum];
}
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int l, r, m;
while (cin >> l >> r >> m) {
cout << Get(r, m) - Get(l - 1, m) << '\n';
}
return 0;
}
AcWing 1085. 不要62
题目链接: AcWing 1085. 不要62
题意:
求在 $[l,r]$ 范围内,有多少个数不包含 $4$ 且不包含连续的 $62$ 。
解题思路:
用 $dp[i,limit,last]$ 表示对前 $i$ 位作出了抉择,末尾数是 $last$ 的所有方案,我们保证在填数字的时候不填入 $4$ ,并且在 $last=6$ 时,不填入 $2$ 即可。
代码实现:
#include <bits/stdc++.h>
using namespace std;
int Get(int k) {
if (k == 0) {
return 0;
}
vector<int> num;
while (k > 0) {
num.emplace_back(k % 10);
k /= 10;
}
int n = (int) num.size();
reverse(num.begin(), num.end());
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(2, vector<int>(10)));
for (int i = 0; i < n; i++) {
for (int x = 1; x <= (i == 0 ? num[i] : 9); x++) {
if (x != 4) {
dp[i + 1][i == 0 && x == num[i]][x] += 1;
}
}
for (int limit = 0; limit <= 1; limit++) {
for (int last = 0; last <= 9; last++) {
for (int x = 0; x <= (limit ? num[i] : 9); x++) {
if (x == 4 || (last == 6 && x == 2)) {
continue;
}
dp[i + 1][limit && x == num[i]][x] += dp[i][limit][last];
}
}
}
}
int res = 0;
for (int last = 0; last <= 9; last++) {
res += dp[n][0][last] + dp[n][1][last];
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int l, r;
while (cin >> l >> r) {
if (l == 0 && r == 0) {
break;
}
cout << Get(r) - Get(l - 1) << '\n';
}
return 0;
}
AcWing 1082. 数字游戏
题目链接: AcWing 1082. 数字游戏
题意:
求在 $[l,r]$ 范围内,有多少个数从左到右各位数字呈非下降关系。
解题思路:
用 $dp[i,limit,last]$ 表示对前 $i$ 位作出了抉择,末尾数是 $last$ 的所有方案,我们保证在填数字时不能填入比 $last$ 小的数即可。
代码实现:
#include <bits/stdc++.h>
using namespace std;
int Get(int k) {
if (k == 0) {
return 0;
}
vector<int> num;
while (k > 0) {
num.emplace_back(k % 10);
k /= 10;
}
int n = (int) num.size();
reverse(num.begin(), num.end());
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(2, vector<int>(10)));
for (int i = 0; i < n; i++) {
for (int x = 1; x <= (i == 0 ? num[i] : 9); x++) {
dp[i + 1][i == 0 && x == num[i]][x] += 1;
}
for (int limit = 0; limit <= 1; limit++) {
for (int last = 0; last <= 9; last++) {
for (int x = last; x <= (limit ? num[i] : 9); x++) {
dp[i + 1][limit && x == num[i]][x] += dp[i][limit][last];
}
}
}
}
int res = 0;
for (int last = 0; last <= 9; last++) {
res += dp[n][0][last] + dp[n][1][last];
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int l, r;
while (cin >> l >> r) {
cout << Get(r) - Get(l - 1) << '\n';
}
return 0;
}
推荐习题
后面的习题会比前面的更加复杂哦。
AcWing 1083. Windy数
题目链接: AcWing 1083. Windy数
题意:
求在 $[l,r]$ 范围内,有多少个数相邻两个数位之间的数字之差的绝对值至少为 $2$ 。
解题思路:
用 $dp[i,limit,last]$ 表示对前 $i$ 位作出了抉择,末尾数是 $last$ 的所有方案,我们保证在填入的数字和 $last$ 作差的绝对值至少为 $2$ 即可。
代码实现:
#include <bits/stdc++.h>
using namespace std;
int Get(int k) {
if (k == 0) {
return 0;
}
vector<int> num;
while (k > 0) {
num.emplace_back(k % 10);
k /= 10;
}
int n = (int) num.size();
reverse(num.begin(), num.end());
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(2, vector<int>(10)));
for (int i = 0; i < n; i++) {
for (int x = 1; x <= (i == 0 ? num[i] : 9); x++) {
dp[i + 1][i == 0 && x == num[i]][x] += 1;
}
for (int limit = 0; limit <= 1; limit++) {
for (int last = 0; last <= 9; last++) {
for (int x = 0; x <= (limit ? num[i] : 9); x++) {
if (abs(x - last) >= 2) {
dp[i + 1][limit && x == num[i]][x] += dp[i][limit][last];
}
}
}
}
}
int res = 0;
for (int last = 0; last <= 9; last++) {
res += dp[n][0][last] + dp[n][1][last];
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int l, r;
cin >> l >> r;
cout << Get(r) - Get(l - 1) << '\n';
return 0;
}
AcWing 1081. 度的数量
题目链接: AcWing 1081. 度的数量
题意:
求在 $[l,r]$ 范围内,有多少个数恰好为 $k$ 个互不相等的 $b$ 的整数次幂之和。
解题思路:
我们将每个数用 $b$ 进制来表示,因为题目要求是互不相等的次幂之和,所以每一位要么是 $0$ 要么是 $1$ 。用 $dp[i,limit,cnt]$ 表示对前 $i$ 位作出了抉择,已经填入了 $cnt$ 个 $1$ 的所有方案。
代码实现:
#include <bits/stdc++.h>
using namespace std;
int Get(int y, int k, int b) {
if (y == 0) {
return 0;
}
vector<int> num;
while (y > 0) {
num.emplace_back(y % b);
y /= b;
}
int n = (int) num.size();
reverse(num.begin(), num.end());
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(2, vector<int>(k + 1)));
for (int i = 0; i < n; i++) {
// 注意,整个填数过程只能填 0 或 1
// 在处理最高位的时候,只能填 1 ,直接填入即可
dp[i + 1][i == 0 && 1 == num[i]][1] += 1;
for (int limit = 0; limit <= 1; limit++) {
for (int cnt = 0; cnt <= k; cnt++) {
// 注意这里的条件,因为只能填入 0 和 1
// 要和 num[i] 取一个最小值
for (int x = 0; x <= (limit ? min(num[i], 1) : 1); x++) {
if (cnt + x <= k) {
dp[i + 1][limit && x == num[i]][cnt + int(x == 1)] += dp[i][limit][cnt];
}
}
}
}
}
int res = dp[n][0][k] + dp[n][1][k];
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int l, r, k, b;
cin >> l >> r >> k >> b;
cout << Get(r, k, b) - Get(l - 1, k, b) << '\n';
return 0;
}
AcWing 338. 计数问题
题目链接: AcWing 338. 计数问题
题意:
求在 $[l,r]$ 的所有数中, $[0,9]$ 这 $10$ 个数字一共出现了多少次。
解题思路:
这题我们可以分开算每个数字出现了多少次,一共做 $10$ 次数位 DP 。
假如当前我们算的是数字 $c$ 出现了多少次,用 $dp[i,limit,cnt]$ 表示对前 $i$ 位作出了抉择,且数字 $c$ 已经在前面数位中出现了 $cnt$ 次的所有方案,属性是数量。
转移时,如果填入的数字 $x==c$ ,那么转移到的状态 $cnt+1$ 。
最后统计时,枚举每个 $cnt$ ,将 $cnt\times (dp[n,0,cnt]+dp[n,1,cnt])$ 统计到答案里面去。
代码实现:
#include <bits/stdc++.h>
using namespace std;
int Get(int k, int c) {
if (k == 0) {
return 0;
}
vector<int> num;
while (k > 0) {
num.emplace_back(k % 10);
k /= 10;
}
int n = (int) num.size();
reverse(num.begin(), num.end());
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(2, vector<int>(10)));
for (int i = 0; i < n; i++) {
for (int x = 1; x <= (i == 0 ? num[i] : 9); x++) {
// 当 x == c 时,初始化到 cnt = 1
// 否则初始化到 cnt = 0
dp[i + 1][i == 0 && x == num[i]][x == c] += 1;
}
for (int limit = 0; limit <= 1; limit++) {
for (int cnt = 0; cnt <= 9; cnt++) {
for (int x = 0; x <= (limit ? num[i] : 9); x++) {
if (x != c) {
dp[i + 1][limit && x == num[i]][cnt] += dp[i][limit][cnt];
} else {
// 如果 x == c ,还要考虑数组越界问题
if (cnt + 1 <= 9) {
dp[i + 1][limit && x == num[i]][cnt + 1] += dp[i][limit][cnt];
}
}
}
}
}
}
int res = 0;
for (int cnt = 0; cnt <= 9; cnt++) {
res += cnt * (dp[n][0][cnt] + dp[n][1][cnt]);
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int l, r;
while (cin >> l >> r && l && r) {
if (l > r) {
swap(l, r);
}
for (int c = 0; c <= 9; c++) {
cout << Get(r, c) - Get(l - 1, c) << " \n"[c == 9];
}
}
return 0;
}
洛谷 P4127 同类分布
题目链接: 洛谷 P4127 同类分布
题意:
求在 $[l,r]$ 的所有数中,有多少个数能被其各位数字之和整除。
解题思路:
这题和上面的几道题有相似之处,直觉上,我们会想到要维护当前数位上的数字之和 $cur\_sum$ ,以及当前的数对数位上的数字之和取模的结果 $mod$ 。
留意一下, $cur\_sum$ 是当前之和,而当前数应该对最终的数字之和 $sum$ 取模,这个 $sum$ 是中间过程是未知的,但结果是一个定量。因此在对 $x$ 数位 DP 时,我们可以枚举 $sum$ ,枚举的范围是 $[1,S]$ ,其中 $S$ 为 $x$ 的位数乘 $9$ ,然后 DP 过程中间维护 $mod=cur\_sum \mod sum$ ,以及 $cur\_sum$ 。
也就是说用 $dp[i,limit,mod,cur\_sum]$ 表示对前 $i$ 位进行了抉择,当前数位上的数字和为 $cur\_sum$ ,$cur\_sum$ 对最终数位上的数字之和 $sum$ 取模的结果为 $mod$ 的所有方案。最终结果为 $dp[n,0,0,sum]+dp[n,1,0,sum]$ 。
注意事项:
本题的时间在没有开 O2优化
的情况下卡得比较紧,以下代码在没开的情况下是可以过的,所以在写的时候用了一些优化,比如:
- $S=9\times n+1$ ,这是最小的情况了,一般开数组都会习惯上预留多一点点。
- 使用滚动数组,这是计数类 DP 的常用技巧,建议掌握。
- 如果当前状态为空则不更新。
当然现在主流的比赛、平台都支持 O2优化
,所以问题不大。
代码实现:
#include <bits/stdc++.h>
using namespace std;
long long Get(long long k) {
if (k == 0) {
return 0;
}
vector<int> num;
while (k > 0) {
num.emplace_back(k % 10);
k /= 10;
}
int n = (int) num.size();
reverse(num.begin(), num.end());
// S 表示 x 的最大数位和加一,防止数组越界
const int S = 9 * n + 1;
long long res = 0;
// 枚举要取的最终数位和
for (int sum = 1; sum < S; sum++) {
vector<vector<vector<long long>>> dp(2, vector<vector<long long>>(sum, vector<long long>(S)));
for (int i = 0; i < n; i++) {
vector<vector<vector<long long>>> ndp(2, vector<vector<long long>>(sum, vector<long long>(S)));
for (int x = 1; x <= (i == 0 ? num[i] : 9); x++) {
ndp[i == 0 && x == num[i]][x % sum][x] += 1;
}
for (int limit = 0; limit <= 1; limit++) {
for (int mod = 0; mod < sum; mod++) {
for (int cur_sum = 0; cur_sum < S; cur_sum++) {
// 如果当前状态的值为 0 ,就没必要更新了,是个小优化
if (dp[limit][mod][cur_sum] > 0) {
for (int x = 0; x <= (limit ? num[i] : 9); x++) {
if (x + cur_sum < S) {
ndp[limit && x == num[i]][(mod * 10 + x) % sum][cur_sum + x] += dp[limit][mod][cur_sum];
}
}
}
}
}
}
swap(dp, ndp);
}
res += dp[0][0][sum] + dp[1][0][sum];
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
long long l, r;
cin >> l >> r;
cout << Get(r) - Get(l - 1) << '\n';
return 0;
}
CF 628D Magic Numbers
题目链接: CF 628D Magic Numbers
题意:
求在 $[l,r]$ 的所有数中,有多少个数对 $m$ 取模为 $0$ ,且所有的偶数数位为 $d$ ,所有奇数数位不出现 $d$ 。
解题思路:
用 $dp[i,limit,cur_mod,cnt]$ 表示对 $i$ 个数位进行了抉择,当前数对 $m$ 取模结果为 $mod$ ,一共在个数为奇偶性为 $cnt$ 个的数位上填数的所有方案,并且在填数时,如果当前是偶数数位,则只填 $d$ ,否则不能填 $d$ 即可。
注意事项:
本题的数值范围很大,所以要用字符串读入,用了上面提到的高精度减法。
其实也可以通过 $Get(r)-Get(l)+Check(l)$ 得到答案,其中 $Check(x)$ 为特判 $x$ 是否符合题意条件的函数。
注意事项:
本题题面没说 $0$ 是否能取,因此最好特判一下。
本题的空间要求比较大,也要用滚动数组。
代码实现:
#include <bits/stdc++.h>
using namespace std;
const int mod = (int) 1e9 + 7;
// minus 表示当前的数是否要减一
int Get(string s, bool minus, int m, int d) {
if (minus) {
// 如果 l 已经是 0 ,那么减一后是 -1 ,可以直接返回 0
if ((int) s.size() == 1 && s[0] == '0') {
return 0;
}
reverse(s.begin(), s.end());
int i = 0;
while (s[i] == '0') {
++i;
}
--s[i];
--i;
while (i >= 0) {
s[i] = '9';
--i;
}
while ((int) s.size() > 1 && s.back() == '0') {
s.pop_back();
}
reverse(s.begin(), s.end());
}
int n = (int) s.size();
vector<int> num(n);
for (int i = 0; i < n; i++) {
num[i] = (int) (s[i] - '0');
}
vector<vector<vector<int>>> dp(2, vector<vector<int>>(m, vector<int>(2)));
for (int i = 0; i < n; i++) {
vector<vector<vector<int>>> ndp(2, vector<vector<int>>(m, vector<int>(2)));
for (int x = 1; x <= (i == 0 ? num[i] : 9); x++) {
if (x != d) {
ndp[i == 0 && x == num[i]][x % m][1] += 1;
}
}
for (int limit = 0; limit <= 1; limit++) {
for (int cur_mod = 0; cur_mod < m; cur_mod++) {
for (int x = 0; x <= (limit ? num[i] : 9); x++) {
int& cur0 = dp[limit][cur_mod][0];
int& cur1 = dp[limit][cur_mod][1];
int& nxt0 = ndp[limit && x == num[i]][(cur_mod * 10 + x) % m][0];
int& nxt1 = ndp[limit && x == num[i]][(cur_mod * 10 + x) % m][1];
if (x == d) {
nxt0 = (nxt0 + cur1) % mod;
} else {
nxt1 = (nxt1 + cur0) % mod;
}
}
}
}
swap(dp, ndp);
}
// 因为题目没说是否包含 0 ,所以特判一下
int zero = (int) (d == 0);
int res = zero;
for (int limit = 0; limit <= 1; limit++) {
for (int cnt = 0; cnt <= 1; cnt++) {
res = (res + dp[limit][0][cnt]) % mod;
}
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int m, d;
cin >> m >> d;
string l, r;
cin >> l >> r;
cout << (Get(r, false, m, d) - Get(l, true, m, d) + mod) % mod << '\n';
return 0;
}
洛谷 P4317 花神的数论题
题意:
求 $[1,k]$ 中每个数在二进制表示下, $1$ 的个数的乘积。
解题思路:
将 $k$ 用二进制表示,进行数位 DP ,只能填 $0$ 或 $1$ 。然后用 $dp[i,limit,cnt]$ 表示对前 $i$ 位进行了抉择后,有 $cnt$ 个 $1$ 。
最后统计的时候,枚举 $cnt$ ,计算 $cnt^{(dp[n,0,cnt]+dp[n,1,cnt])}$ 。
代码实现:
#include <bits/stdc++.h>
using namespace std;
const long long mod = 10000007;
long long qp(long long a, long long b) {
long long res = 1;
while (b > 0) {
if (b & 1) {
res = res * a % mod;
}
a = a * a % mod;
b >>= 1;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
long long k;
cin >> k;
vector<int> num;
while (k > 0) {
num.emplace_back(k % 2);
k /= 2;
}
int n = (int) num.size();
reverse(num.begin(), num.end());
vector<vector<vector<long long>>> dp(n + 1, vector<vector<long long>>(2, vector<long long>(n + 1)));
for (int i = 0; i < n; i++) {
// 这里只能填入 1
for (int x = 1; x <= (i == 0 ? num[i] : 1); x++) {
dp[i + 1][i == 0 && x == num[i]][1] += 1;
}
for (int limit = 0; limit <= 1; limit++) {
for (int cnt = 0; cnt <= n; cnt++) {
// 这里只能填入 0 或 1
for (int x = 0; x <= (limit ? num[i] : 1); x++) {
if (x + cnt <= n) {
dp[i + 1][limit && x == num[i]][cnt + x] += dp[i][limit][cnt];
}
}
}
}
}
long long res = 1;
for (int cnt = 0; cnt <= n; cnt++) {
res = res * qp(cnt, dp[n][0][cnt] + dp[n][1][cnt]) % mod;
}
cout << res << '\n';
return 0;
}
洛谷 P3413 萌数
题目链接: 洛谷 P3413 萌数
题意:
求在 $[l,r]$ 的所有数中,有多少个数存在长度至少为 $2$ 的回文串。
解题思路:
这题我们只需要统计长度为 $2$ 或 $3$ 的回文串即可,因为更长的回文串必然包含长度为 $2$ 或 $3$ 的回文串。
用 $dp[i,limit,last0,last1,flag]$ 表示对前 $i$ 个数位进行抉择后,第 $i-1$ 个数位上的数字是 $last0$ ,第 $i$ 个数位上的数字是 $last1$ ,前面是否有回文串(用 $flag$ 标记, $flag=1$ 表示有)的所有方案。如果第 $i-1$ 或 $i$ 个数位上没有数字,则用一个不会出现在数位上的数表示,比如 $10$ 。
转移的话,是一个状态机模型,我们来分类讨论一下:
- 当 $flag=1$ :无论当前位如何抉择,都可以转移到自身。
- 当 $flag=0$ :只有 $x==last0$ 或 $x==last1$ 时,形成了长度为 $2$ 或 $3$ 的回文串,才转移到 $1$ ,否则转移到 $0$ 。
代码实现:
#include <bits/stdc++.h>
using namespace std;
const int mod = (int) 1e9 + 7;
int Get(string s, bool minus) {
if (minus) {
if ((int) s.size() == 1 && s[0] == '0') {
return 0;
}
reverse(s.begin(), s.end());
int i = 0;
while (s[i] == '0') {
++i;
}
--s[i];
--i;
while (i >= 0) {
s[i] = '9';
--i;
}
while ((int) s.size() > 1 && s.back() == '0') {
s.pop_back();
}
reverse(s.begin(), s.end());
}
int n = (int) s.size();
vector<int> num(n);
for (int i = 0; i < n; i++) {
num[i] = (int) (s[i] - '0');
}
vector<vector<vector<vector<vector<int>>>>> dp(n + 1, vector<vector<vector<vector<int>>>>(2, vector<vector<vector<int>>>(11, vector<vector<int>>(11, vector<int>(2)))));
for (int i = 0; i < n; i++) {
for (int x = 1; x <= (i == 0 ? num[i] : 9); x++) {
dp[i + 1][i == 0 && x == num[i]][10][x][0] += 1;
}
for (int limit = 0; limit <= 1; limit++) {
for (int last0 = 0; last0 <= 10; last0++) {
for (int last1 = 0; last1 <= 10; last1++) {
for (int x = 0; x <= (limit ? num[i] : 9); x++) {
int& cur0 = dp[i][limit][last0][last1][0];
int& cur1 = dp[i][limit][last0][last1][1];
int& nxt0 = dp[i + 1][limit && x == num[i]][last1][x][0];
int& nxt1 = dp[i + 1][limit && x == num[i]][last1][x][1];
nxt1 = (nxt1 + cur1) % mod;
if (x == last0 || x == last1) {
nxt1 = (nxt1 + cur0) % mod;
} else {
nxt0 = (nxt0 + cur0) % mod;
}
}
}
}
}
}
int res = 0;
for (int limit = 0; limit <= 1; limit++) {
for (int last0 = 0; last0 <= 9; last0++) {
for (int last1 = 0; last1 <= 9; last1++) {
res = (res + dp[n][limit][last0][last1][1]) % mod;
}
}
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
string l, r;
cin >> l >> r;
cout << (Get(r, false) - Get(l, true) + mod) % mod << '\n';
return 0;
}
HDU 6148 Valley Numer
题目链接: HDU 6148 Valley Numer
题意:
求在 $[l,r]$ 的所有数中,有多少个数是“山谷数”。“山谷数”的定义为“ 当一个数字,从左到右依次看过去数字没有出现先递增接着递减 ”。具体举例可以看原题链接。
解题思路:
这也是一个状态机模型,我们用 $dp[i,limit,last,state]$ 表示对前 $i$ 个数位进行了抉择,第 $i$ 个数位上的数字为 $last$ ,当前数的状态为 $state$ 的所有方案。关于 $state$ 的定义如下:
- $state==0$ :从第一个数字到第 $i$ 个数位的数所有数都相等。
- $state==1$ :从第一个数字到第 $i$ 个数位的数存在上升,且不存在下降。
- $state==2$ :从第一个数字到第 $i$ 个数位的数存在下降,且不存在上升。
- $state==3$ :从第一个数字到第 $i$ 个数位的数先下降,且正在上升。
我们来分类讨论一下:
- 当 $x==last$ :所有状态都转移到自身。
- 当 $x>last$ :$0$ 可以转移到 $1$ , $1$ 可以转移到 $1$ , $2$ 可以转移到 $3$ , $3$ 可以转移到 $3$ 。
- 当 $x<last$ :$0$ 可以转移到 $2$ , $2$ 可以转移到 $2$ 。
代码实现:
#include <bits/stdc++.h>
using namespace std;
const int mod = (int) 1e9 + 7;
int Get(string s) {
int n = (int) s.size();
vector<int> num(n);
for (int i = 0; i < n; i++) {
num[i] = (int) (s[i] - '0');
}
vector<vector<vector<vector<int>>>> dp(n + 1, vector<vector<vector<int>>>(2, vector<vector<int>>(10, vector<int>(4))));
for (int i = 0; i < n; i++) {
for (int x = 1; x <= (i == 0 ? num[i] : 9); x++) {
dp[i + 1][i == 0 && x == num[i]][x][0] += 1;
}
for (int limit = 0; limit <= 1; limit++) {
for (int last = 0; last <= 9; last++) {
for (int x = 0; x <= (limit ? num[i] : 9); x++) {
int& cur0 = dp[i][limit][last][0];
int& cur1 = dp[i][limit][last][1];
int& cur2 = dp[i][limit][last][2];
int& cur3 = dp[i][limit][last][3];
int& nxt0 = dp[i + 1][limit && x == num[i]][x][0];
int& nxt1 = dp[i + 1][limit && x == num[i]][x][1];
int& nxt2 = dp[i + 1][limit && x == num[i]][x][2];
int& nxt3 = dp[i + 1][limit && x == num[i]][x][3];
if (x > last) {
// 0 -> 1
nxt1 = (nxt1 + cur0) % mod;
// 1 -> 1
nxt1 = (nxt1 + cur1) % mod;
// 2 -> 3
nxt3 = (nxt3 + cur2) % mod;
// 3 -> 3
nxt3 = (nxt3 + cur3) % mod;
}
if (x < last) {
// 0 -> 2
nxt2 = (nxt2 + cur0) % mod;
// 2 -> 2
nxt2 = (nxt2 + cur2) % mod;
}
if (x == last) {
// 0 -> 0
nxt0 = (nxt0 + cur0) % mod;
// 1 -> 1
nxt1 = (nxt1 + cur1) % mod;
// 2 -> 2
nxt2 = (nxt2 + cur2) % mod;
// 3 -> 3
nxt3 = (nxt3 + cur3) % mod;
}
}
}
}
}
int res = 0;
for (int limit = 0; limit <= 1; limit++) {
for (int last = 0; last <= 9; last++) {
for (int state = 0; state < 4; state++) {
res = (res + dp[n][limit][last][state]) % mod;
}
}
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while (T--) {
string s;
cin >> s;
cout << Get(s) << '\n';
}
return 0;
}
SPOJ MYQ10 Mirror Number
题目链接: SPOJ MYQ10 Mirror Number
题意:
求在 $[l,r]$ 的所有数中,有多少个数满足以中心点轴对称。
解题思路:
首先要理解轴对称,意味着只能填入 $0,1,8$ 这三种数字。
我们填数的时候,因为要保证对称,也就是填到末尾的时候,要找到在前面对应数位填了什么数,而上面展示的常规填数过程是很难存储之前填过什么数的(一两个还行,多了就实现不了了)。
所以我们不妨从两边同时往中间填,也就是初始化 $i=0,j=n-1$ ,一直填到 $i\leq j$ 为止。我们用 $dp[i,limit_l,limit_r]$ 表示对左半部分的前 $i$ 个数进行抉择后(此时右半部分也填入了和左半部分对称的数),两边限制分别为 $limit_l$ 和 $limit_r$ 的所有方案。左半部分的 $limit_l$ 和常规数位 DP 的 $limit$ 一样,表示第 $i$ 位前的数字是否全都和原数的前 $i$ 位一样,而 $limit_r$ 表示当前右半部分的状态:
- $limit_r==0$ :填入的数字组成的数比原数的后 $i$ 个数位组成的数小
- $limit_r==1$ :填入的数字组成的数等于原数的后 $i$ 个数位组成的数
- $limit_r==2$ :填入的数字组成的数比原数的后 $i$ 个数位组成的数大
这样在填入一个新数 $x$ 时,转移如下:
- $x<num[j]$ : $0$ 可以转移到 $0$ , $1$ 可以转移到 $0$ , $2$ 可以转移到 $0$ 。
- $x==num[j]$ : $0$ 可以转移到 $0$ , $1$ 可以转移到 $1$ , $2$ 可以转移到 $2$ 。
- $x>num[j]$ : $0$ 可以转移到 $2$ , $1$ 可以转移到 $2$ , $2$ 可以转移到 $2$ 。
最后统计答案,如果左半部分 $limit_l==0$ ,那么右半部分 $limit_r$ 可以任意取值;如果如果左半部分 $limit_l==0$ ,那么右半部分 $limit_r$ 只能取 $0$ 或 $1$ 。
这样就结束了吗?还没有。
以上这个思路很巧妙,但其实只考虑了填入的数字数量和原数的数位数量相等的情况。我们发现如果最终填入的数字组成的数长度比原数长度小的话,其实维护右半部分的 $limit_r$ 是没有意义的,这时候, 几乎可以任意填数 。
因此,以上的数位 DP 做法,我们只算最终填入的数字组成的数长度比原数长度的情况下,满足条件的数有多少个。至于最终长度比原数小的情况,我们通过枚举最终长度来求解。枚举的范围是 $len=[1,n-1]$ ,其中 $n$ 为原数长度。对于每个 $len$ ,首位是不能填入 $0$ 的,于是只有 $1,8$ 两种选择,而中间位都有 $0,1,8$ 三种选择。因此对于每个 $len$ ,都将 $2\times 3^{(len+1)/2-1}$ 统计到答案中去即可。
代码实现:
#include <bits/stdc++.h>
using namespace std;
long long qp(long long a, long long b) {
long long res = 1;
while (b > 0) {
if (b & 1) {
res *= a;
}
b >>= 1;
a *= a;
}
return res;
}
long long Get(string s, bool minus) {
if (minus) {
if ((int) s.size() == 1 && s[0] == '0') {
return 0;
}
reverse(s.begin(), s.end());
int i = 0;
while (s[i] == '0') {
++i;
}
--s[i];
--i;
while (i >= 0) {
s[i] = '9';
--i;
}
while ((int) s.size() > 1 && s.back() == '0') {
s.pop_back();
}
reverse(s.begin(), s.end());
}
int n = (int) s.size();
vector<int> num(n);
for (int i = 0; i < n; i++) {
num[i] = (int) (s[i] - '0');
}
vector<vector<long long>> dp(2, vector<long long>(3));
for (int i = 0, j = n - 1; i <= j; i++, j--) {
vector<vector<long long>> ndp(2, vector<long long>(3));
if (i == 0) {
for (auto &x : {1, 8}) {
if (x > num[i]) {
break;
}
if (x < num[j]) {
ndp[x == num[i]][0] += 1;
}
if (x == num[j]) {
ndp[x == num[i]][1] += 1;
}
if (x > num[j]) {
ndp[x == num[i]][2] += 1;
}
}
}
for (int limit_l = 0; limit_l <= 1; limit_l++) {
for (auto &x : {0, 1, 8}) {
if (limit_l && x > num[i]) {
break;
}
if (x < num[j]) {
// 0 -> 0
ndp[limit_l && x == num[i]][0] += dp[limit_l][0];
// 0 -> 1
ndp[limit_l && x == num[i]][0] += dp[limit_l][1];
// 0 -> 2
ndp[limit_l && x == num[i]][0] += dp[limit_l][2];
}
if (x == num[j]) {
// 0 -> 0
ndp[limit_l && x == num[i]][0] += dp[limit_l][0];
// 1 -> 1
ndp[limit_l && x == num[i]][1] += dp[limit_l][1];
// 2 -> 2
ndp[limit_l && x == num[i]][2] += dp[limit_l][2];
}
if (x > num[j]) {
// 0 -> 2
ndp[limit_l && x == num[i]][2] += dp[limit_l][0];
// 1 -> 2
ndp[limit_l && x == num[i]][2] += dp[limit_l][1];
// 2 -> 2
ndp[limit_l && x == num[i]][2] += dp[limit_l][2];
}
}
}
swap(dp, ndp);
}
// 需要特判 0 ,0 也是对称的
int zero = 1;
long long res = zero;
for (int limit_r = 0; limit_r <= 2; limit_r++) {
res += dp[0][limit_r];
}
for (int limit_r = 0; limit_r <= 1; limit_r++) {
res += dp[1][limit_r];
}
for (int len = 1; len < n; len++) {
res += 2 * qp(3, (len + 1) / 2 - 1);
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while (T--) {
string l, r;
cin >> l >> r;
cout << Get(r, false) - Get(l, true) << '\n';
}
return 0;
}
CF 55D Beautiful numbers
题目链接: CF 55D Beautiful numbers
题意:
求在 $[l,r]$ 的所有数中,有多少个数可以被其数位上所有非零数字整除。
解题思路:
这题跟上面的题目有相似的地方,如果读者能够理解上面类似的题目,应该可以想到我们要维护这些变量:当前用了哪些数字、当前组成的数对已用数字取模的结果。
第一个变量好说(其实没这么简单,继续往下看就知道了),我们可以用二进制状态压缩来表示十个数字是否用到。
第二个变量呢?其实我们在 DP 过程中不着急将当前组成的数对已用数字进行取模,但是组成的数很大,数组肯定存不下,所以还是要找一个数进行取模。这个数就是 $[1,9]$ 的最小公倍数。
为什么这样可以呢?因为能被 $lcm(a,b,c,d)$ 整除的数,一定能被 $lcm(a,b)$ 或 $lcm(b,c,d)$ 整除。也就是说 $(x \mod lcm(a,b,c,d)) \mod lcm(a,b)==x\mod lcm(a,b)$ 。因此我们在过程中不断对这个数就是 $[1,9]$ 的最小公倍数取模即可。
因此我们用 $dp[i,limit,mod,mask]$ 表示对前 $i$ 个数位进行抉择后,当前数取模结果为 $mod$ ,当前已用数字为 $mask$ 的所有方案。但是我们会发现,这样的时间复杂度已经大概在 $10^9$ 左右,我们必须要进行优化。
我们可以从 $mask$ 入手,还能用什么方式表示已用数字呢?直接用已用数字的最小公倍数即可。我们计算可以得到 $[1,9]$ 取出任意的数字计算最小公倍数,一共只有 $48$ 个,这样我们的 $mask$ 从 $256$ 下降到了 $48$ 。
如何实现?我们将所有 $[1,9]$ 组合起来得到的公倍数从小到大排列,每个公倍数的下标就是其索引,如何用一个 $idx[i][x]$ 表示第 $i$ 个公倍数和 $x$ 的公倍数对应的公倍数索引,即可进行转移,具体可以看代码实现。
代码实现:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
// 求 [1,9] 所有数字组合的最小公倍数
vector<int> factors;
for (int mask = 0; mask < 1 << 10; mask++) {
int res = 1;
for (int bit = 1; bit < 10; bit++) {
if ((mask >> bit) & 1) {
res = lcm(res, bit);
}
}
factors.emplace_back(res);
}
// 离散化一下
sort(factors.begin(), factors.end());
factors.erase(unique(factors.begin(), factors.end()), factors.end());
// pos[factor] 表示 factor 在 factors 的下标
vector<int> pos(factors.back() + 1, -1);
for (int i = 0; i < (int) factors.size(); i++) {
pos[factors[i]] = i;
}
// idx[i][x] 表示 lcm(factors[i], x) 在 factors 的下标
vector<vector<int>> idx((int) factors.size(), vector<int>(10));
for (int i = 0; i < (int) factors.size(); i++) {
// 如果加入的是 0 ,则保持原样
idx[i][0] = i;
for (int x = 1; x <= 9; x++) {
idx[i][x] = pos[lcm(factors[i], x)];
}
}
// 求 [1,9] 的最小公倍数
int L = 1;
for (int x = 1; x <= 9; x++) {
L = lcm(L, x);
}
// 为了方便实现,这里使用 Lambda 函数
auto Get = [&](long long k) -> long long {
if (k == 0) {
return 0;
}
vector<int> num;
while (k > 0) {
num.emplace_back(k % 10);
k /= 10;
}
int n = (int) num.size();
reverse(num.begin(), num.end());
vector<vector<vector<long long>>> dp(2, vector<vector<long long>>(L, vector<long long>((int) factors.size())));
for (int i = 0; i < n; i++) {
vector<vector<vector<long long>>> ndp(2, vector<vector<long long>>(L, vector<long long>((int) factors.size())));
for (int x = 1; x <= (i == 0 ? num[i] : 9); x++) {
ndp[i == 0 && x == num[i]][x % L][pos[x]] += 1;
}
for (int limit = 0; limit <= 1; limit++) {
for (int mod = 0; mod < L; mod++) {
for (int j = 0; j < (int) factors.size(); j++) {
if (dp[limit][mod][j] != 0) {
for (int x = 0; x <= (limit ? num[i] : 9); x++) {
ndp[limit && x == num[i]][(mod * 10 + x) % L][idx[j][x]] += dp[limit][mod][j];
}
}
}
}
}
swap(dp, ndp);
}
long long res = 0;
for (int limit = 0; limit <= 1; limit++) {
for (int mod = 0; mod < L; mod++) {
for (int j = 0; j < (int) factors.size(); j++) {
// 如果取模结果对已用数字的最小公倍数取模为 0 ,则统计到答案里
if (mod % factors[j] == 0) {
res += dp[limit][mod][j];
}
}
}
}
return res;
};
int T;
cin >> T;
while (T--) {
long long l, r;
cin >> l >> r;
cout << Get(r) - Get(l - 1) << '\n';
}
return 0;
}
至此,数位 DP 的原理、思路以及基本的代码实现就已经完成了,不难发现,代码本身以及在运行时的时空上都有优化的空间,这是为了让初学者在理解时更加清楚填数字的过程,而不是抽象带过,死记硬背模板。下一篇我们来说说如何用更优雅的方式写出数位 DP 的代码吧。
我想问一下:在模版遍历的那里,第一个for循环是填入i位,且是最终数的最高位,并初始化limit。但是下面的for循环又是填入i位x,这应该怎么思考呢,
请问在第二个代码块中的 x 是啥
感谢指出,应该是新加入的数 $c$ 。
绪神加油!
Thank you!
我好像又明白一点了,底下的for循环是进行状态转移的循环,,把当前位置的x的所有可能性向后进行转移。。。不知道这种理解对不对
对的,你可以这么理解,第一个是初始化,只是在最高位填,第二个是对之前的状态(如果有的话)的转移。
牛的,写了好多,作者用心了
谢谢hh
niubility
谢谢hh
niubility