算法简介：出发！火之国

数位DP，字面意思上来讲，就是按位做 DP，他的原理是基于类似于前缀和的思想，统计 0 ~ n 这部分的某种数字然后利用前缀和思想求出一段区间内某种数字的算法。

算法演示：以燔燎铸名

说实话，这是一个随机应变的算法，要更据题目给的数字用合适的方法计算数字，这里只能给出一点基础的建议。

我们思考，对于一个 $n$ 我们要制造出小于等于它的数字，怎么办？由于高位对于地位有绝对压制， 所以说如果当前位是 $P$ ，那么如果我选了数字 $i(i < P)$ ，那么往后的我们就可以随便选，如果 $i = P$ 我们还得继续考虑。

其次就是前导零。对于前导零我们还得开一个标记记录，如果前导零的标记还在，但是我们选了0，那这个是不算数的。

模板大概就是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int dp[50]; // DP数组
// 当前到了哪一位（从高到低），是否还有限制，是否有前导零，等等要维护的变量
ll Dfs(int len, int lim, int top, ...) {
    if(len == 0) { // 没了
        return ...;
    }
    if(!lim && !top && dp[len] != -1) { // 已经算过了
        return dp[len];
    }
    int mx = lim ? a[len] : 9; // 有没有限制
    ll ans = 0;
    for(int i = 0; i <= mx; i++) {
        ans += Dfs(len - 1, limit && i == mx, top & i == 0, ...); // 统计答案
    }
    if(!limit) dp[len][mask] = ans; // 记录答案
    return ans;
}

详细的用法还得自己体会，建议看下面的题目。

算法实战：荣花与炎日之途