定义 Link to heading
数位 dp 主要是为了解决以下问题：
求出在给定区间 $[A, B]$ 内，符合条件 $f(i)$ 的 i 的个数。
注意这里的 $f(i)$ 通常情况下和大小无关，而是一些奇怪的性质。例如“水仙花数”等。
这里我们用一个非常简单的问题来引出数位 dp：
对于范围 $[A, B]$ 来说，有多少个数字 $x$，使得 $x$ 满足其十进制数位含有 $d$ 的个数恰好为 $k$ 次？
输入：$A, B, d, k$ 输出：满足条件的数的个数
原理 Link to heading
数位 dp 范围 Link to heading
数位 dp 解决 $[0, N]$ 范围的问题，对于刚刚提到的 $[A, B]$ 可以采用 $[0, B] - [0, A]$ 来解决。
构建数位序列 Link to heading
将一个数看作是数字的序列 $sq$，我们想要从左向右构建序列 $sq$，当某一位构建完成后，递归调用构建下一位。对于其中的某一位，不一定可以选择 0～9 中的全部，而是需要确保选择之后的数不会比 $N$ 更大。
如何推断一个数位 Link to heading
假设当前位于位置 $pos$，那么从第 1 位到第 $pos-1$ 位则都已经确定了。如果在这确定的数位中存在一位 $t, (1 <= t < pos)$ 使得 $sq[i] < b[t]$，那么数位 $pos$ 就可以选择 0～9的任意一位，因为此时生成的数已经绝对小于上限。
但如果没有这样的 $t$ 使得 $pos$ 数位可以在 0～9 之间任选，那我们就只能在 0～$b[pos]$ 之间考虑了。
省去数位序列 Link to heading
在递归 dp 的过程中，我们可以通过设定一个 f1 来判断之前是否已经满足了 $t$ 的条件。当某次 $t$ 选择了小于 $b[t]$ 的数位时，只要将 f1 设置为 true 并传递给下一递归函数即可。
额外情况 Link to heading
刚刚给出了构建数位序列 sq 的过程。但是并没有给出计算满足条件的数的过程。我们可以定义一个参数 $cnt$，用来表示已经出现数字 $d$ 的次数。当整个序列 sq 构建完毕时，只需要考虑 $cnt$ 即可知道序列是否满足条件。
最终的 dp 状态 Link to heading
我们需要为 dp 保存三个状态。
- 当前构建的位置 $pos$。
- 当前数位之前是否已经满足小于 $b[t]$ 的情况：f1。
- 目前数字 $d$ 出现的次数：cnt。
尝试用单个递归解决双范围 $[A, B]$ 的问题 Link to heading
我们刚刚给出了一个参数 f1 用来标记是否满足小于的情况，那么也完全可以设置一个参数 f2 用来标记是否有一个数位 $t$ 满足 $sq[t] > a[t]$。根据 f2 的值，我们可以判断是否可以在当前位选择一个比 $a[t]$ 更小的值。
模板代码 Link to heading
这里对代码进行了适当的改编。initial_condition 表示 dp 需要保存的状态，根据不同问题而异。当递归完成最后一位的时候返回 1 表示当前数字满足情况。如果某次还不是数字，那么可以跳过一次不填写数字。
1a = str(n)
2# 返回从 i 开始向后填数字，可以构造的符合条件的整数的数量。
3# mask 表示 i 之前的数位填写的数字
4# is_limit 表示前面填写的数字是否都是 n 对应位上的，或者说现在是否可以往超过 a[t] 以上的数字填写
5# is_num 表示前面是否填写了数字，用于解决前导 0 的问题。
6# 如果为 true，那么当前位从 0 开始
7# 如果为 false，那么既可以跳过也可以从 1 开始
8# 比如有些题目需要计算 0 出现的次数，那么当 is_num 为 false 的时候
9# 0 就不能参与后面的枚举计算
10@cache
11def f(i: int, some_condition: int, is_limit: bool, is_num: bool) -> int:
12 if i == len(s): # 已经到达终点了，而且已经构造出来了一个整数
13 return int(is_num)
14 res = 0
15 if not is_num: # 现在还不是数字，那么可以继续跳过，不填数字
16 res = f(i+1, some_condition, False, False)
17 # is_limit 是 False，因为跳过了说明肯定不超过上界
18 up = int(s[i]) if is_limit else 9 # 上界根据之前是否小于上界来判断
19 # 枚举要填写的数字
20 for d in range(1-int(is_num), up+1) # 如果没有构成数字的话只能从 1 开始循环
21 if some_condition
22 res += f(i+1, update_conditoin, is_limit and d == up, True)
23 return res
24
25f(0, initial_condition, True, False)