跟 Nachia DP 博客学DP-16 数位 DP
需要对于给定的 $N$ 位以下的全体非负整数 $x$ 进行计算、计数等问题时候，使用这样的状态转移和设计会比较好，所以被称作 数位DP。
常见的有两种：
- $dp[n][c]:=$ （将 $x$ 的高位第 $n$ 位确定下来，针对这部分与特定值关系或其他由状态 $c$ 能表示的子问题的解）
- $dp[n][c]:=$ （将 $x$ 的低位第 $n$ 位确定下来，针对这部分与特定值关系或其他由状态 $c$ 能表示的子问题的解）
后者在某些领域也被称为 竹DP，前者是通常的数位 DP，下文我称其为 逆向数位 DP。
例题
例 1: No.741 AscNumber 不下降数字 2.0$
https://yukicoder.me/problems/no/741
EASY：逆向数位 DP 模板。
讲解见： https://sistinefibel-2006.github.io/post/20260831%20-mei-ri-%202.0%202.5%204.0.html
例 2：https://atcoder.jp/contests/dp/tasks/dp_s
https://atcoder.jp/contests/dp/tasks/dp_s
Note
给定大正整数 $K \le 10^{10000}$，找到所有比他小的正整数的数量，取模 $10^9+7$，满足：
- 十进制表示下各个数位之和是 $D \in [1,100]$ 的倍数
如果朴素的思考，肯定会想要套用上面的模板，于是设：
$dp[n][c]:=$ 从左到右枚举到第 $n$ 位，前 $n$ 位总和是 $c$ 的数的数量
但是仔细想一想就会发现，这个设计有一些问题。少考虑了两件事情：
- 第二维度过大且冗余，完全可以设计成 $c \mod{D}$ 的结果，这样第二维最大是 $D$
- 没有存储当前数是否合法，换句话说，我们要多设计一个维度表示，如果到下一位枚举的时候，是否还有没有可能性超过 $K$ 的限制？
于是有最终的 DP 设计：$dp[n][c][0/1]:=$ 从左到右枚举到第 $n$ 位，前 $n$ 位之和取模 $D$ 为 $c$，之后还有没有可能超过 $K$ 的数字总数。
现在考虑转移设计：
考虑什么情况下有可能超过 $K$？
- 如果我们设当前是第 $x$ 位，那么其要满足，从 $dp[x - 1][...][0]$ 转移过来，也就是前一位得有可能超过，且前一位得满足 $K_{x-1} =$ 枚举的下一位。
反之则不可能大于。
于是我们有转移方程
$$
j \in [0, 9] : dp[x][c + j \mod{D}][1] = dp[x - 1][c + j \mod{D}][1] + dp[x - 1][c + j \mod{D}][0] \cdot [j < K_{x - 1}]
$$
$$ j \in[0, 9] : dp[x][c + j \mod{D}][0] = dp[x - 1][c + j \mod{D}][0] \cdot [j = K_{x - 1}] $$
这样就行了么？
还得把 0 减去，所以 $ans - 1$ 就可以了