Digit DP

1. 形式

通常需要我们去计算在 $A$ 和 $B$ 之内满足某条件的数的个数,数据规模通常都很大,如 $10^{18}$。
而处理的思想一般遵循以下步骤:

  1. 定义 $dp[i][j]$ 为长度为 $i$ 以 $j$ 开头的满足某条件的数的个数
  2. 通过性质,将转移方程写出来,然后预处理出 $dp$ 数组。(注意此处只是预处理,并不是数位 DP 的主要部分)
  3. 逐位计算,

Digit DP
https://cwhirly.github.io/2025/11/04/OI/Dynamic Programming/Digit DP/
作者
Weihao Cheng
发布于
2025年11月4日
许可协议