数位 DP

概述

• 数位 DP 是以从数学意义上的位数出发来 DP 为特点的一类 DP。

• 下述特点中的一部分可能对计数类以外的不适用。

• 状态设计通常包含“考虑到第几位”和“是否已经比上界小”。

• 初始化通常为 \(dp_{0,\dots}=1\) 或 \(dp_{n+1,\dots}=1\)，视从高位向低位或从低位向高位而不同。

• 转移的话，除了以位为层之外，没有太多共同点。

• 实现上常常把 DP 的形式拆掉...这让设计的 DP 状态多没面子啊...

• 下面主要分两类来谈。

计数式问题

• 典型代表如 \(\text{P2518 [HAOI2010] 计数}\)（拆 DP） 和 \(\text{P2657 [SCOI2009] windy 数}\)（不能拆），较为经典的变种有 \(\text{P4127 [AHOI2009] 同类分布}\)。

• 特点是其要求往往是“计算 \([L,R]\) 内具有某种性质的数字个数”，且实现思路通常为差分，并会记录“是否已经比上界小”。

• 状态通常为 \(dp_{i,0/1/,\dots}\)，表示安排完高/低 \(i\) 位，是否已经比上界小，（其他题目要求的性质，），的总方案数。

  • 所谓“是否已经比上界小”，就是是否在只比较更高位的前提下小于 \(lim\)，这代表着后面可以乱填了。

  • 从高位开始的较为常用，因为其转移较为自由，下面以默认从高位开始位前提来谈。

• 初始化通常为 \(dp_{n+1,0,\dots}=1\)。

• 状态转移上，我个人觉得顺推比较舒服。大概就是暴力枚举下一位，计算性质满足情况，然后填表过去。

  • 大部分情况下，尝试逆推然后加速转移是不可行的，因为计数式问题的奇怪要求往往导致离散的转移起点。

• 复杂度 \(O(\log_k v)\)，其中 \(k\) 为进制。辅助维开销可能很大，此时不能忽略其复杂度。

P2518 [HAOI2010] 计数

• 题意：给出一个元素为 \(1\sim 9\) 的可重集 \(S\)，求向其任意排列插入任意个 \(0\) 生成的所有数字中有多少个比 \(v\) 小，禁止前导零。保证 \(v\) 也是由这个集合生成的。

• 数据范围：记 \(n\) 为 \(v\) 在十进制下的位数，则 \(n\leqslant 50\)。下面所有题不再给出数据范围，因显然数据范围充分小。

• 设计 DP 如下：

  • 状态设计：\(dp_{i,0/1,sta}\) 表示考虑了高 \(i\) 位，是否已经比 \(v\) 小，还剩 \(sta\) 里面的数字可以用的总方案数。

    • 这里我们把所有生成的 \(\leqslant v\) 的数字都强行补前导零补到 \(n\) 位，于是变成一个排列问题。

  • 初始化：记 \(n\) 为 \(v\) 的位数，\(dp_{n+1,0,full}=1\)。

  • 状态转移方程：\(dp_{i,0/1,sta}\to dp_{i-1,0/1,sta'}\)。不太好形式化，用自然语言说就是选 \(sta\) 里面一个数使得生成出的数到目前为止仍然 \(\leqslant lim\)，然后转过去。

• 然而实际上我并不是这么实现的。考虑设计一个辅助 DP 如下：

  • 状态设计：\(tp_i\) 表示 \(n\sim i+1\) 位与 \(lim\) 相同的数的数量。

  • 实际上这根本没必要 DP，这东西就是个组合连乘（在剩余的位里面选出 \(num_i\) 个位置放 \(i\)），本质是可重集排列数，即 \(\dfrac{(\sum\limits_{i=0}^{k-1} num_i)!}{\prod\limits_{i=0}^{k-1}num_i!}\)。

• 于是问题变成暴力枚举哪一位开始不一样了，然后直接加对应的 \(tp\)。

• 个人认为舒服得多。奇怪的限制不强的时候，把“已经更小”视为“可以乱搞”然后直接统计方案数是有力的手段。

• 复杂度 \(O(kn)\)，其中 \(k\) 为进制（暴力枚举下一位和求组合的时候都得遍历每个数字）。

• \(k\) 太大的时候怎么办？

• 有一个基于可重集排列和康托展开的 \(O(n\log k)\) 更优解：

  • 考虑我们和康托展开主要区别是什么：康托展开计算下一位有多少种方式更小，我们则是将这些方式都扩展出来然后统计。

  • 那么尝试回到康托展开，总体思路是先认为相等的数码不同，最后除以算重的次数。

  • 不妨认为前 \(i-1\) 位相同，我们计算第 \(i\) 位更小的方案数，以 \(4,2,0,2,5,4\) 为例：

    • 第一位（最高位）更小：

      • 填 \(0\)：\(1\times 5!\)。

      • 填 \(2\)：这是关键！本位上可以从两个 \(2\) 里面选一个，于是是 \(2\times 5!\)。

      • 填 \(4\)：相同，考察下一位。注意 \(4\) 此时有两个，所以后面的所有方案乘上 \(2\) 的全局系数！

    • 第二，...位更小：略。

  • 最后我们除以 \(\prod\limits_{i=0}^{k-1}num_i=1!2!2!1!\)（阶乘顺序按数码从小到大）。

  • 回过头来考察，为什么是对的？

    • 对于第一位放 \(0\)：确实是 \(\dfrac{5!}{1!2!2!1!}\) 种。

    • 对于第一位放 \(2\)：后面的方案实际上有 \(\dfrac{5!}{1!1!2!1!}\) 种，这里却除了 \(1!2!2!1!\)。不对吗？

    • 对的！这里对 \(2\) 除了 \(2!\)，看似后面只有一个 \(2\) 除多了，但不要忘记“本位上可以从两个 \(2\) 里面选一个”（将对应影响提前算上了）！故实际为 \(\dfrac{2\times 5!}{1!2!2!1!}=\dfrac{5!}{1!1!2!1!}\)。

    • 全局系数也是同样的原理。

  • 故只需要按下式计算即可：\(ans=\dfrac{\sum\limits_{i=n}^{1}(\sum\limits_{j=0}^{a_i-1}num_j-get(a_i-1))\times (i-1)!\times factor}{\prod\limits_{i=0}^{k-1} num_i!}\)。

    • 其中 \(a_i\) 表示从高到低的第 \(i\) 位上数字，\(factor\) 为因高位相同而产生的全局系数，初始为 \(1\)。

    • 每次算完后，请 \(ins(a_i,1),factor\times=num_{a_i},--num_{a_i}\)。事实上这个 \(num\) 的和大概是用另一个 ta 来维护。

    • 之所以看起来和康托展开是反的是因为我们从高位向低位走，康托展开的排列是从前往后考虑。

  • 于是可以 \(O(n\log k)\) 高效解决。

P2657 [SCOI2009] windy 数

• 题意：求 \(\in [L,R]\) 的相邻两位数字之差不超过 \(2\) 的数字个数。

• 设计 DP：

  • 状态设计：\(dp_{i,0/1,0/1,0\sim 10}\) 表示考虑高 \(i\)，是否已经小，结尾为 \(0\sim 9\) 或未开始（放 \(10\)）的方案数。

  • 初始化：\(dp_{n+1,0,10}=1\)。。

  • 状态转移：\(dp_{i,0/1,j}\to dp_{i-1,0/1,[0,j-2]\bigcup[j+2,9]}\)。\(10\) 的转移相对特殊，不想写了。注意这里的转移是 \(O(k)\) 的。

• 其实这个东西也可以拆，就是不是很好拆，需要 \(tp_{i,0\sim 9}\) 这样来。难写程度大概和这个没开始的辅助维是卧龙凤雏。

• 复杂度 \(O(k^2n)\)，其中 \(k\) 为进制。

P2602 [ZJOI2010] 数字计数

• 题意：求每个数码在 \([L,R]\) 的所有数字中的出现次数之和。

• 设计 DP：这个 DP 不太典型......

  • 状态设计：\(dp_{i,0/1,0\sim 9}\) 表示考虑完高 \(i\) 位，是否已经小，末尾是什么的方案数。
    • 事实上，一旦已经小，我们就立马计数（后面是 \(10^{rest}\)），然后后面的容易统计（不行就再拉一个 DP），前面的每个数码加上这个方案数。

• 复杂度 \(O(k^2n)\)。

P4127 [AHOI2009] 同类分布

• 题意：求 \(\in [L,R]\) 的各位数码之和能整除自身的数的个数。

• 这个的主要难点在于看出应该暴力枚举位和 \(sum\)。然后可以这么 DP：

  • 状态设计：\(dp_{i,0/1,req,rest}\) 表示考虑完高 \(i\) 位，是否已经小，位和离 \(sum\) 还差多少，当前 \(\bmod sum\) 的余数是多少。

  • 初始化：\(dp_{n+1,0,sum,0}=1\)。

  • 状态转移：无非还是暴力枚举下一位，然后计算转移到哪。

• 复杂度 \(O(n^3k^3)\)，状态 \(O(n\times sum\times sum=n^3k^2)\)，转移 \(O(k)\)。

P4317 花神的数论题

• 题意略。

• 暴力枚举有几位是 \(1\)，然后照旧 \(dp_{i,j,1}\) 表示考虑完高 \(i\) 位，还要放 \(j\) 个 \(1\)，是否已经小的方案数。

• 于是变成快速幂。除暴力枚举和二进制外平凡。\(O(n^3k^2)\)？这个 \(k\)...有必要吗？把辅助维都算进去了？

CF55D Beautiful numbers

• 题意：求 \([L,R]\) 间可被自身每一位上数字（\(0\) 除外）整除的数字个数。

• 还是用那一招，暴力枚举。

• 暴力枚举有哪些数字，\(2^{9}\) 然后记录 \(9\) 个余数？

  • 烦死了拜托，转移写死人。

  • 而且这样出来的状态 \(O(n\times 2^{10})\)，转移 \(O(10^2)\)，枚举量 \(O(2^{10})\)，\(T=10\)，寄了，这还没考虑容斥。

• 转而考虑枚举最小公倍数。发现不同的最小公倍数只有 \(48\) 种，上界为 \(2520\)，于是显然有 \(O(n\operatorname{lcm})\) 的状态，\(O(10)\) 的转移和 \(O(48)\) 的枚举量。

• 总复杂度 \(O(Tn\operatorname{lcm}k\times cnt(lcm))\approx 2.4\times 10^8\)，\(4s\)，这很 CF。

• 这就完了？不好意思，这个做法得容斥。考虑一个不含 \(3\) 但可以被 \(3\) 整除的数字，它显然会被错误地计算。

• 容斥很烦。考虑再开一维 \(dp_{i,rest,\operatorname{lcm}}\)，其中 \(\operatorname{lcm}\) 为当前各位上的数字的最小公倍数，显然这可以压成 \(48\)。

• 可是这样复杂度炸了。怎么办？

• 舍弃枚举！把 \(rest\) 的取模对象固定为 \(2520\)，等 DP 结束的时候检查 \(rest\bmod \operatorname{lcm}\)。

• 那完事了。这个转化确实还挺妙的，枚举的目的是使得状态可以接受，那么没有必要进行不能减小状态的枚举（或者虽然减小但是亏本的枚举）。

P5674 【SWTR-02】Magical Gates

• 题意：求 \(\sum\limits_{i=l}^r ppc(i)\) 和 \(\prod\limits_{i=l}^r ppc(i)\)。

• 数据范围：\(T\leqslant 10,l,r\leqslant 10^{1000}\)。

• 这鬼畜的数据范围...读入都是个大问题...不过我们大概率是把它转成二进制处理，先当字符串读进来然后处理成二进制 vector 吧。

• 老规矩，考虑做到 \(1\) 是什么情况然后容斥。唔，显然还是要枚举 \(ppc\) 来计数，用换底公式可知这玩意也就不到 \(2^{3322}\)，我们后面记 \(len=3323\)（因为还有第 \(0\) 位），一个方便的办法是不断地拆 lowbit，具体地，每次算 lowbit 长的一段的情况然后递归，复杂度 \(O(len^2)\)，最后求逆元可以忽略不计，中间的 \(2\) 的次幂可以直接预处理（反正也就最多到 \(2^{len}\)），足够通过本题。

位权式问题

• 典型代表如 \(\text{P2647 最大收益}\)。

• 位权式问题归在数位 DP 里，真的只能说是沾边。

• 特点是转移式带有某种位权色彩，仿佛逐位地放上去数字一样。

• 没有其他的共性，因为我目前就只找到一道题...所以也就无所谓抽象出共性了...看例题那边吧。

P2647 最大收益

• 题意：有 \(n\) 个物品，每个物品有两个属性 \(v,w\)，选择某个物品可以获得 \(v_i\) 的收益并使还没有被选的所有物品的 \(v=v-w_i\)。求最大总收益。

• 数据范围：\(n\leqslant 3\times 10^3,v,w\leqslant 2\times 10^5\)。

• 这个东西显然处处透着不对劲，乍一看无后效性似乎是不可能的。

• 想办法找一点性质：时光倒流。我们认为实际上较早选取的物品是较晚决策的，并将所有已经决策的物品的 \(v\) 削减。

• 于是看起来它只有前效性了，我们来设法 DP：

  • 状态设计：\(dp_{i,j}\) 表示考虑了前 \(i\) 个物品，选了 \(j\) 个的最大总价值。

  • 初始化：\(dp_{0,0}=0\)。

  • 状态转移方程：\(dp_{i,j}=\max(dp_{i-1,j},dp_{i-1,j-1}+v_i-w_i\times (j-1))\)。

• 但是这仍然不一定对；也许我们是先选后面的再选前面的。怎么办？

• 不妨假设我们已经决定了选哪些物品。我们来考虑最优的选取顺序是怎样的：一定是先选 \(w\) 大的，后选 \(w\) 小的。

• 那完事了。将物品按 \(w\) 降序排序，然后上去跑上面的 DP。贪心和 DP 的优雅结合。复杂度 \(O(n^2)\)。

• 为什么是数位？嗯...我认为那个 \(j-1\) 是位权，我们是在从低向高地用 \(w\) 填这个数字的每一位。

复杂数位 DP

P7961 [NOIP2021] 数列

• 题意：

  • 定义合法序列为满足如下条件的自然数序列 \(a\)：

    • \(|a|=n,a_i\leqslant m\)。

    • \(S=\sum\limits_{i=1}^n 2^{a_i},ppc(S)\leqslant K\)。

  • 定义序列 \(a\) 的权值为 \(\prod\limits_{i=1}^nv_{a_i}\)。

  • 求所有合法序列的权值和，序列是有序序列。

• 数据范围：\(K\leqslant n\leqslant 30,m\leqslant 100\)。

• 这道题乍一看就十分凶险。我们来找一些性质吧。

• 首先，把 \(a\) 的顺序舍弃。顺序唯一的影响是答案统计，这个我们设法用组合数来解决。

• 然后发现限制主要是在 \(S\) 上。于是考虑以 \(S\) 的每一位为核心状态，问题来了，从高向低还是从低向高？

• 从低向高！这里我们要处理 \(1\) 的个数，从高向低的做法显然有后效性的，因为进位是有向的。而从低向高考虑的话，低 \(i\) 位一定是确定不变的。

• 那么我们来设法设计 \(dp\)，设计出来就算成功。

  • 状态设计：\(dp_{i,j,k,l}\) 表示

    • 考虑完 \(S\) 的低 \(i\) 位（认为位权为 \(1\) 的是第 \(0\) 位）。

    • 当前 \(a\) 已经决定了 \(j\) 个。

    • 当前 \(ppc(S)=k\)，这个只考虑低 \(i\) 位的，更高位不考虑。

    • 要对 \(i+1\) 这位进 \(k\) 。

    • 的所有方案的权值和。

  • 初始化：显然我们没有 \(dp_{-1}\) 可供初始化使用，故考虑直接暴力把 \(dp_{0,x,\dots}\) 转出来作为初始化。

  • 状态转移：

    • 暴力枚举在第 \(i+1\) 位上放多少个 \(1\)，即有多少个 \(a\) 等于 \(i+1\)，计算出对应的 \(k,l\) 来转移。

      • 转移系数为 \(C(n-k,num)\times v_{i+1}^{num}\)，其中 \(num\) 为枚举的多少个 \(1\)。记得初始化 \(v\) 的 \(0\sim n\) 次方。

• 状态数 \(O((m+\log_2 n)n^3)\)，转移 \(O(n)\)，总复杂度 \(O((m+\log_2 n)n^4)\approx 8\times 10^7\)，足够通过本题。

• 之所以这里有一个 \(+\log_2 n\) 是因为进位可能进到比 \(m\) 更高的位上。应当注意不能把 \(a\) 往这几位上放。

• 具有一定的计数式问题色彩，但显然不是。