数位 DP 做题记录

数位 DP

数位 DP 的常见套路就是记录当前到哪一位，是否抵着上界，转移时枚举当前可以填哪些数，做一遍记忆化搜索。

P3413 SAC#1 - 萌数

题意：求 \([l,r]\) 中有多少个数中含有回文子串。

思路：如果存在回文子串，那么必然有相邻两位相同或者间隔一位相同，在数位 DP 时额外记录前 2 位就可以了。

CF1487F Ones

题意：给定一个正整数 \(n\)，要求用只由 \(1\) 组成的数字的和或差表示 \(n\)，且使用 \(1\) 个数最少。

思路：一看就像数位 DP，但是又跟普通数位 DP 不太像。

其实直接从高位到低位考虑，那么对当前位进行的操作有影响的只有之前位还剩下的需要抵消的和当前位已经要减多少，即设 \(f[pos][c][x][0/1]\) 表示当前考虑到了第 \(pos\) 位，前面的还有 \(c\) 需要抵消，这一位及一下需要减 \(x\)，当前位是 - 还是 + 的答案，于是有转移

现在的问题是确定 \(c,x\) 的范围，因为在当前位加的 1 个数不会超过 5 次，因此 \(c\leqslant\frac{x}{10}+1\)。

P9129 [USACO23FEB] Piling Papers G

题意：给定长度为 \(n(1\leq n\leq 300)\) 的整数序列 \(a(1\leq a_i\leq 9)\)，和整数区间 \([A,B](1\leq A\leq B\leq 10^{18})\)，有 \(q\) 次询问，每次询问给出 \(l,r\)。每次询问开始，你有一个空串 \(x\)，你可以正序对 \(a_{l\sim r}\) 进行操作，操作有三种：\(x\rightarrow\overline{x+a_i}\)，\(x\rightarrow\overline{a_i+x}\)，或者什么也不做，求 \(\overline{x}\) 的取值在 \([A,B]\) 的不同的操作方案数，对 \(10^9+7\) 取模。

思路：很新奇的数位 DP。

因为可以从前、后都加数字，这样传统的数位 DP 显然行不通了。我们发现 \(A,B\) 很小，于是我们可以把当前已经填了的数所在的区间 \([l,r]\) 计入状态。于是设 \(f[i][l][r][0/1/2]\) 表示前 \(i\) 个数形成了区间 \([l,r]\)，当前数和 \(t\) 的关系（\(>,<,=\)）。最终答案是 \(f[n][1][len][0/1]+\sum\limits_{l>1}f[n][l][len][0/1/2]\)。

这样求出来的是每个前缀的答案，于是预处理出所有后缀的答案就可以 \(O(1)\) 回答了。

P2518 [HAOI2010] 计数

题意：现在给定一个数，你可以删掉这个数中的任意多个数位 0
（或不删）并将其他的数位任意重新排序。请求出能产生出多少个不同的这个数小的数（注意这个数不会有前导 0）。

思路：看起来是数位 DP，不过可以有更优的做法，数据范围可以加 1000000 个 0！

那就是可重复元素的康托展开。

从末尾往前，维护当前答案和当前排列个数，排列个数就是 \(\dfrac{n!}{\prod a_i}\)，记当前是 \(a\)，已经出现了 \(b\) 次，比 \(a\) 小的有 \(c\) 个，于是当前位的贡献就是 \(\dfrac{tc}{b}\)。

于是用树状数组维护即可。

CF585F Digits of Number Pi

题意：给定数字串 \(s,x,y(len(x)=len(y),x\leqslant y)\)，求存在长度不小于 \(\left\lfloor\dfrac{len(x)}{2}\right\rfloor\) 的子串是 \(s\) 的子串的数字串 \(t\in[x,y]\) 的数量。

思路：首先看到 \([x,y]\) 第一反应肯定是数位 DP，但又因为与字符串匹配有关，自然就考虑上 AC 自动机或 SAM，而我写的是 SAM 的做法。设 \(f[cur][pos][len][lim][flag]\) 表示当前在第 \(cur\) 位，在 SAM 上为第 \(pos\) 个节点，当前已匹配的字符串长度为 \(len\)，\(lim=0/1\) 表示有没有顶到上界，\(flag=0/1\) 表示目前长度合不合法。转移时枚举下一个选的哪一个数字，若长度已合法或 SAM 上当前节点有这个儿子则可直接转移，否则不断跳 \(link\) 直到有这个儿子或跳到了 1 号节点为止，然后再转移。复杂度 \(O(10nd^2)\)。

CF55D Beautiful numbers

题意：Volodya 认为一个数字 \(x\) 是美丽的，当且仅当 \(x\in\mathbb{Z^+}\) 并且对于 \(x\) 的每一个非零位上的数 \(y\)，都有 \(y|x\)。

你需要帮助他算出在区间 \([l,r]\) 中有多少个数是美丽的。

思路：首先想到，\(1\sim 9\) 的 \(lcm\) 是 2520，于是我们可以在数位 DP 时记录当前模 2520 的于是和当前的 lcm，而有用的 lcm 只有 48 个，可以只记录这些，于是就做完了。

P3303 [SDOI2013] 淘金

题意：记 \(f(i)\) 表示 \(i\) 的数码的乘积，一开始所有 \((i,j)(i,j\in[1,n])\) 上有一个金子，然后所有位置上的金子会移动到 \((f(i),f(j))\)，你可以选择 \(k\) 个位置，求最多可以有多少金子。

思路：首先考虑枚举 \(f(i)\) 计算有多少 \(i\)。因为 \(f(i)\) 的指质因子只有 2,3,5,7，可以把每个质因子的指数存进状态进行数位 DP 计算答案。

然后就是贪心了。将 \(f(i)\) 按照对应多少个 \(i\) 从大到小排序然后贪心选择即可。