数位 DP


本页面将简要介绍数位 DP。

引入

数位是指把一个数字按照个、十、百、千等等一位一位地拆开,关注它每一位上的数字。如果拆的是十进制数,那么每一位数字都是 0~9,其他进制可类比十进制。

数位 DP:用来解决一类特定问题,这种问题比较好辨认,一般具有这几个特征:

  1. 要求统计满足一定条件的数的数量(即,最终目的为计数);

  2. 这些条件经过转化后可以使用「数位」的思想去理解和判断;

  3. 输入会提供一个数字区间(有时也只提供上界)来作为统计的限制;

  4. 上界很大(比如 ),暴力枚举验证会超时。

数位 DP 的基本原理:

考虑人类计数的方式,最朴素的计数就是从小到大开始依次加一。但我们发现对于位数比较多的数,这样的过程中有许多重复的部分。例如,从 7000 数到 7999、从 8000 数到 8999、和从 9000 数到 9999 的过程非常相似,它们都是后三位从 000 变到 999,不一样的地方只有千位这一位,所以我们可以把这些过程归并起来,将这些过程中产生的计数答案也都存在一个通用的数组里。此数组根据题目具体要求设置状态,用递推或 DP 的方式进行状态转移。

数位 DP 中通常会利用常规计数问题技巧,比如把一个区间内的答案拆成两部分相减(即

那么有了通用答案数组,接下来就是统计答案。统计答案可以选择记忆化搜索,也可以选择循环迭代递推。为了不重不漏地统计所有不超过上限的答案,要从高到低枚举每一位,再考虑每一位都可以填哪些数字,最后利用通用答案数组统计答案。

接下来我们具体看几道题目。

例题一

题目大意:给定两个正整数 ,求在 中的所有整数中,每个数码(digit)各出现了多少次。

方法一

解释

发现对于满 位的数,所有数字出现的次数都是相同的,故设数组 为满 位的数中每个数字出现的次数,此时暂时不处理前导零。则有 ,这两部分前一个是来自前 位数字的贡献,后一个是来自第 位的数字的贡献。

有了 数组,我们来考虑如何统计答案。将上界按位分开,从高到低枚举,不贴着上界时,后面可以随便取值。贴着上界时,后面就只能取 到上界,分两部分分别计算贡献。最后考虑下前导零,第 位为前导 时,此时 位也都是 ,也就是多算了将 位填满的答案,需要额外减去。

实现

方法二

解释

此题也可以使用记忆化搜索。 表示不贴上限、无前导零时,位数为 的答案。

详见代码注释

过程

例题二

题面大意:统计一个区间内数位上不能有 4 也不能有连续的 62 的数有多少。

解释

没有 4 的话在枚举的时候判断一下,不枚举 4 就可以保证状态合法了,所以这个约束没有记忆化的必要,而对于 62 的话,涉及到两位,当前一位是 6 或者不是 6 这两种不同情况我计数是不相同的,所以要用状态来记录不同的方案数。 表示当前第 位,前一位是否是 6 的状态,这里 只需要取 0 和 1 两种状态就可以了,不是 6 的情况可视为同种,不会影响计数。

实现

例题三

题目大意:给定一个区间 ,求其中满足条件 不含前导 且相邻两个数字相差至少为 的数字个数。

解释

首先我们将问题转化成更加简单的形式。设 表示在区间 中满足条件的数的数量,那么所求的答案就是

对于一个小于 的数,它从高到低肯定出现某一位,使得这一位上的数值小于 这一位上对应的数值。而之前的所有位都和 上的位相等。

有了这个性质,我们可以定义 表示当前将要考虑的是从高到低的第 位,当前该前缀的状态为 且前缀和当前求解的数字的大小关系是 表示等于, 表示小于)时的数字个数。在本题中,这个前缀的状态就是上一位的值,因为当前将要确定的位不能取哪些数只和上一位有关。在其他题目中,这个值可以是:前缀的数字和,前缀所有数字的 ,该前缀取模某个数的余数,也有两种或多种合用的情况。

写出 状态转移方程

这里的 就是当前枚举的下一位的值,而 就是当前能取到的最高位。因为如果 ,那么你在这一位上取的值一定不能大于求解的数字上该位的值,否则则没有限制。

我们发现,尽管前缀所选择的状态不同,而 的三个参数相同,答案就是一样的。为了防止这个答案被计算多次,可以使用

记忆化搜索 的方式实现。

实现

例题四

题面大意:假如手写下 之间所有整数,会有多少数看起来和在镜子里看起来一模一样?()

解释

注:由于这里考虑到的镜像,只有 的镜像是自己本身。所以,这里的「一模一样」并不是传统意义上的回文串,而是只含有 的回文串。

首先,在数位 DP 过程中,显然只有 能被选中。

其次,由于数值超过 long long 范围,所以 不再适用(高精度比较繁琐),而是需要对 是否合法进行判断,得出:

镜像解决了,如何判断回文?

我们需要用一个小数组记录一下之前的值。在未超过一半的长度时,只要不超上限就行;在超过一半的长度时,还需要判断是否和与之「镜面对称」的位相等。

需要额外注意的是,这道题的记忆化部分,不能用 memset,否则会导致超时。

实现

例题五

题面:我们称一个正整数 是幸运数,当且仅当它的十进制表示中不包含数字串集合 中任意一个元素作为其子串。例如当 时, 是幸运数, 不是幸运数。给定 ,计算不大于 的幸运数个数。答案对 取模。

,其中 表示字符串 的长度。 没有前导 ,但是 可能有前导

解释

阅读题面发现,如果将数字看成字符串,那么这就是需要完成一个多模匹配,自然而然就想到 AC 自动机。普通数位 DP 中,先从高到低枚举数位,再枚举每一位都填什么,在这道题中,我们也就自然地转化为枚举已经填好的位数,再枚举此时停在 AC 自动机上的哪个节点,然后从当前节点转移到它在 AC 自动机上的子节点。

表示当前从高到低已经填了 位(即在 AC 自动机上走过了 条边),此时停在标号为 的节点上,当前是否正好贴着上界。

至于题目中的「不包含」条件,只需在 AC 自动机上给每个模式串的结尾节点都打上标记,DP 过程中一旦遇上这些结尾节点就跳过即可。

转移很好想,详见代码主函数部分。

实现

此题可以很好地帮助理解数位 DP 的原理。

习题

Ahoi2009 self 同类分布

洛谷 P3413 SAC#1 - 萌数

HDU 6148 Valley Number

CF55D Beautiful numbers

CF628D Magic Numbers

贡献者:@WenzelTian@Qingchuan@Ir1d@ksyx@H-J-Granger@Alphnia@thredreams@Danni@mgt@sshwy@Henry-ZHR@GavinZhengOI@ouuan@Billchenchina@心旷神怡@hsfzLZH1

本页面最近更新:2/3/2023, 12:00:00 AM更新历史

发现错误?想一起完善? 在 GitHub 上编辑此页!

本页面的全部内容在 CC BY-SA 4.0SATA 协议之条款下提供,附加条款亦可能应用

评论

0 条评论
未登录用户


Copyright © 2016 - 2023 OI Wiki Team

最近更新:fd2ec2c, 2023-02-03

联系方式:Telegram 群组 / QQ 群组