数位 \(\text{dp}\) 简记

给出一些条件，求某一区间内，满足条件的数的个数；或者是定义一个函数，求某一区间内，函数值的和或积。
数位 \(\text{dp}\) 大多数的限制条件与各位数之和、整除、是否出现、相邻相等有关。
简单记一下有价值的东西。

常规记忆化搜索调用参数

• int len 当前位数
• int pre 上一位数字
• bool lead 有无前导 \(0\)
• bool limit 是否卡上界
• int cnt 统计出现次数
• bool chk 标记是否已经满足条件
• int mod 计算带余除以某个数的值

复杂度大致是所有参数取值范围大小乘在一起，只有卡上界的会一直搜，而卡上界的一定是一条链。

二进制

例题：花神的数论题
二进制记忆化搜索有些大材小用，并且这道题是计算函数的积，可以当做一个计数题来做，容易得到实际是求出每个值作为 \(sum\) 的出现次数。
实际上是运用了数位 \(\text{dp}\) 的思想，考虑当前这一位卡不卡上界，不卡上界一定可以直接算出来，卡上界就递归下去，处理边界情况可能边界麻烦。

整除减少状态数

例题：haha数
可以 \(2^{8}\) 状态压一下出现的数，对于整除情况单个讨论一下，\(2,4,8\) 只需要记录下 \(\bmod 8\) 的余数，\(3,9\) 同理，而 \(7\) 需要单独记录，\(6\) 只要满足 \(2,3\) 的条件即可，最后 \(5\) 在最后一位判断。这样状态数就减少很多。
（一般在只需要知道是否属于一个集合时，将状态选取为 \(0/1\)）

非常规 \(\text{bfs}\)

例题：苍与红的试炼
要求最小所以不能无脑搜，需要 \(\text{bfs}\)。
传参一定是关于整体 \(\bmod d\) 的值以及各位数的和，而参数相同的两个数，在最后加同样的东西都可以达成的情况下，先出现的一定更优，也算是一种优化方式。

不求满足条件数的个数，而是满足条件的位置或者连续段个数

例题：数字计数
已经算是一道计数题了。
记忆化搜索两个答案，方案数以及答案，这样可以统计当前枚举位的贡献以及剩下位置的总答案，不需要计算组合数。