Digit DP
1. 形式
通常需要我们去计算在 $A$ 和 $B$ 之内满足某条件的数的个数,数据规模通常都很大,如 $10^{18}$。
而处理的思想一般遵循以下步骤:
- 定义 $dp[i][j]$ 为长度为 $i$ 以 $j$ 开头的满足某条件的数的个数
- 通过性质,将转移方程写出来,然后预处理出 $dp$ 数组。(注意此处只是预处理,并不是数位 DP 的主要部分)
- 逐位计算,
Digit DP
https://cwhirly.github.io/2025/11/04/OI/Dynamic Programming/Digit DP/