数位 DP 好题

## 数位 DP 简介 在我眼里，数位 DP 也就是一个有技巧的一个 DP，本质上其实也是 DP，或者说是计数？但是两者都需要考察选手对于数位的理解能力，尤其是“标记”的处理。 对此写了一个与数位 DP 相关的[专栏](https://www.luogu.com.cn/article/vyvrgzea)，欢迎拜访。 ## 与数位相关的计数 不需要什么标记，只需要计数能力，而且几乎没有技巧，可以加深对于 $[0,m]$ 之间计数的理解。 - [P2602](/problem/P2602)，应该是最经典的一道，有两种写法，其中一种就是 “计数” DP。 - [B3883](/problem/B3883)，也许是第二典的一道，稍微推导还可以使用计数方式解决。 - [P2235](/problem/P2235)，本质与上一道一样，但是需要转成二进制，说明了数位 DP 的多进制性。 - [P2518](/problem/P2518)，一种更高阶的计数，需要分类讨论“位数小于”和“位数等于”的情况，理解了“位数等于”的情况应该就可以跳转下一章节了。 - [P3281](/problem/P3281)，如果是式子做法需要推大量式子，一方面确实能提升计数能力，感兴趣可以做一做。 ## 与数位相关的 DP 这就需要考察选手对于标记的理解能力，具体来说就是从高位向低位 DP 的过程中维护一个标记表示“前面有没有卡满原数字”。这种 DP 一般使用记忆化搜索实现。 同样的，一些复杂的题目可能还需要对前导零处理。 但是这个标记在简单问题上是可以直接优化掉的，因为在标记存在的时候后面都是可以随便填写的了。 - [P2602](/problem/P2602)，有记忆化搜索带标记写法，但是可能比计数方法要复杂，需要前导零标记，而且不仅要记录出现次数，还要记录符合条件的数字总数。 - [P8764](/problem/P8764)，特别入门的题，不需要前导零标记，该维护的该维护即可。 - [P4999](/problem/P4999)，与第一题类似。 - [P2657](/problem/P2657)，记忆化搜索带标记典题，可以尝试独立思考，需要前导零标记。 - [P3413](/problem/P3413)，方法和上一题是一样的，不过由“任意”转“存在”，可以再新增一个标记来处理。 - [P4124](/problem/P4124)，本质也是多处理几个标记。 - [P6218](/problem/P6218)，练手题。 - [AT_tdpc_number](/problem/AT_tdpc_number)，练手题。 - [P9821](/problem/P9821)，需要同时维护两个数字，本质不难。 - [P4317](/problem/P4317)，一些东西无法同时求解出可以考虑拆分，和下面的 P4127 思想差不多。。 到这里基本就可以处理一些简单的数位 DP 了。 ## 提高与其他技巧应用 - [P7976](/problem/P7976)，数位 DP 可以应用于 Lucas 定理。 - [P8688](/problem/P8688)，上一题的加强，运用了一个优化，即直接计算出从其他状态转移的方案数。 - [P4127](/problem/P4127)，需要枚举一开始不好维护的东西，这应该也是 DP 的一些基本技巧。 - [P3107](/problem/P3107)，与上一题思想同。 - [P10959](/problem/P10959)，上一题的加强版，不能用传统的记忆化实现了。 - [P1831](/problem/P1831)，与上一题思想同。 - [P2106](/problem/P2106)，和矩阵融合在了一起。 - [P5674](/problem/P5674)，彻底的将数位 DP 与计数和数论融合了。 - [P6371](/problem/P6371)，也是一个简单的 trick，经过根号处理后，其中一半就是数位 DP。 - [P9640](/problem/P9640)，与背包结合。 - [CF1073E](/problem/CF1073E)，和状态压缩结合，不需要技巧。 - [UVA12046](/problem/UVA12046)，是下一题的简单版本。 - [CF55D](/problem/CF55D)，需要大概使用哈希的技巧，大概就是把稀疏的状态“离散化”。 - [CF628D](/problem/CF628D)，按照题意模拟即可，但是需要格外注意前导零的实现。 - [AT_abc317_f](/problem/AT_abc317_f)，数位 DP 也可以应用与 Nim 游戏等 SG 函数与数位相关的博弈。 - [AT_abc138_f](/problem/AT_abc138_f)，需要简单的推导转换。 - [P4067](/problem/P4067)，很厉害的题，也是需要两个东西来维护答案和”数字总数“。 - [AT_arc133_d](/problem/AT_arc133_d)，也是很厉害的题，需要分讨一堆。 - [P7717](/problem/P7717)，与字典树的简单结合，思维难度较大。 - [P9129](/problem/P9129)，与正常数位 DP 的标记不同，结合部分区间 DP，思维难度较大。 - [P9387](/problem/P9387)，与上一题目类似，这道题目可以选择倒着 DP，这样就可以方便处理进位，是一个不错的拓展。 ## 总结 总结就是简单题都会做，复杂题就是一堆东西套一堆东西，所以就可以多刷几道练手。 这里的题目没有难的，因为难的题就要涉及到其他更复杂的东西（比如平面几何），也就只是纯数位 DP。 如果本人做到了或是随到了一些好的题目，也会加入其中，也欢迎各路数位 DP 大神推荐好题。