数位动态规划：高效计算区间内特定数字特征的整数个数

核心逻辑与数学原理

数位动态规划（Digit DP）的核心本质是对大整数集合在逐位展开的形式下进行前缀树（Trie）式的拓扑计数优化。它主要用于解决形如“计算区间 $[L, R]$ 中满足某种特定数字特征（如不含特定数字、数位数字之和是质数等）的整数个数”的问题。

1. 区间差分降维映射： 直接在闭区间 $[L, R]$ 上维护复杂的数位限制极度困难。由于计数函数 $f(X)$（表示 $[0, X]$ 内满足条件的个数）具有显式的可加性与独立性，可通过前缀差分将问题无损降维映射为两次独立的单边界计数：

$$\text{Ans} = f(R) - f(L - 1)$$

2. 状态空间的 Trie 树结构与记忆化裁剪： 对于给定的上界 $X$，我们可以将从高位到低位的选数过程看作在一棵高维数字字典树（Trie 树）上的拓扑遍历。

• 贴边限制 (Limit)：如果前面的数位都紧贴着 $X$ 的对应数位，那么当前位能够选择的数字上限就受到了约束。例如 $X = 324$，若前两位选了 3 和 2，当前位至多只能选 4；若前两位选了 3 1，当前位就可以在 0~9 中任意选择。
• 状态重叠的几何本质：一旦某一位的决策“脱离了贴边限制”（即当前选择的数字严格小于 $X$ 的对应数位），那么该数位之后的所有低位数位在选择 0~9 时将不再受到上界 $X$ 的任何约束。此时，后续的搜索子树拓扑结构是完全等价且重叠的。通过引入记忆化数组记录脱离限制后的通用状态，可将指数级暴搜剪枝为 $O(\text{len} \times \text{states})$ 的高规整复杂度。

状态设计与算法推导

数位 DP 最优雅、最不容易在考场写崩溃的实现方式是高度内聚的记忆化搜索模板。

1. 核心搜索函数参数设计

定义 int dfs(int pos, int state, bool limit, bool lead)：

• pos：当前处理的数位指针（从高位向低位推进）。
• state：题目要求的特征状态（如前一位数字、已有的数字之和等）。
• limit：布尔标记，表示当前位是否受到上界 $X$ 的贴边限制。
• lead：布尔标记，表示当前位之前是否全部为前导零。

2. 状态转移与记忆化控制

设当前位在 $X$ 中对应的数字上限为 $up$（若 limit 为真，则 $up = \text{digits}[pos]$，否则 $up = 9$）。 通过循环枚举当前位可以填入的数字 $i \in [0, up]$：

• 下一个状态的限制度 next_limit = limit && (i == up)。
• 下一个状态的前导零标记 next_lead = lead && (i == 0)。
• 累加子状态的返回值：res += dfs(pos - 1, update(state, i), next_limit, next_lead)。

3. 记忆化回溯的数学准则

只有当 limit == false 且 lead == false 时，当前 dfs(pos, state) 的返回值才能写入记忆化数组 dp[pos][state]。因为一旦有贴边限制或前导零污染，当前算出的值只是一个不完整的残缺子树，绝不能作为通用状态进行复用。

C++ 标准源码（NOIP风格）

以下源码解决经典数位 DP 模型：“求区间 $[L, R]$ 中不含连续相同数字（即相邻数位数字不同）的整数个数”，严格兼容 Linux g++ -O2 编译标准。

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

long long dp[20][11]; // dp[pos][pre_digit] 记忆化数组
int digits[20];       // 存储上界 X 拆分后的每一位数字

// 核心记忆化搜索函数
long long dfs(int pos, int pre, bool limit, bool lead) {
    // 基准条件：所有数位处理完毕，说明成功构建了一个合法的数
    if (pos == 0) {
        return 1; 
    }

    // 致命踩坑点：只有在无限制、无前导零污染时，才能直接读取记忆化缓存
    if (!limit && !lead && dp[pos][pre] != -1) {
        return dp[pos][pre];
    }

    // 根据当前的贴边状态，动态锁定当前位的选择上界
    int up = limit ? digits[pos] : 9;
    long long res = 0;

    for (int i = 0; i <= up; ++i) {
        // 条件过滤：若非前导零状态下，当前位与上一位数字相同，则该分支非法
        if (!lead && i == pre) {
            continue;
        }

        // 递归进入下一数位
        // 1. 新的 limit 状态由当前 limit 和是否填到上限数字共同决定
        // 2. 新的 lead 状态由当前 lead 和当前位是否继续填 0 共同决定
        res += dfs(pos - 1, i, limit && (i == up), lead && (i == 0));
    }

    // 致命踩坑点：只有在无限制、无前导零污染时，才能将当前值固化进全局缓存
    if (!limit && !lead) {
        dp[pos][pre] = res;
    }

    return res;
}

// 求解 [0, n] 范围内的合法数量
long long solve(long long n) {
    if (n < 0) return 0;
    if (n == 0) return 1;

    int len = 0;
    while (n > 0) {
        digits[++len] = n % 10; // 将数字剥离，digits[1] 是最低位，digits[len] 是最高位
        n /= 10;
    }

    // 每次求解前，记忆化数组必须全部重置为 -1
    memset(dp, -1, sizeof(dp));

    // 从最高位开始往下刷，初始状态：处于贴边限制(true)，处于前导零(true)，前一位数字传入一个无关值 10
    return dfs(len, 10, true, true);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long l, r;
    if (cin >> l >> r) {
        // 利用前缀差分实现闭区间 [L, R] 的无损映射
        cout << solve(r) - solve(l - 1) << "\n";
    }

    return 0;
}

NOIP 实战避坑指南

1. 错误地对有贴边限制（limit == true）的状态进行记忆化读写

• 现象：在 dfs 函数开头，无条件写了 if (dp[pos][state] != -1) return dp[pos][state];。在搜索结束时也无条件写入。这会导致严重的计数缺失。因为贴边时搜索到的方案数是受到上界强行截断的缩减值。一旦这个残缺的值被作为通用模板缓存起来，后面在无限制状态下走到相同的 pos 和 state 时，就会直接返回这个偏小的值，导致最终答案严重缩水。
• 规避手段：牢记数位 DP 的铁律：只有在 !limit 且 !lead 成立时，才能进行 dp 数组的读取与写入。

2. 忽视差分边界 $L-1$ 导致整型下溢出

• 现象：当输入数据中 $L = 0$ 时，调用 solve(l - 1) 会传入 -1。如果没有在 solve 函数入口进行 if (n < 0) return 0; 的特判，代码会试图去拆分一个负数，导致整个数位分离逻辑陷入死循环或产生越界脏数据。
• 规避手段：对前缀差分的左边界进行严格的安全安检。要么特判 $L=0$ 时直接返回 $f(R)$，要么在 solve 函数内部对负数输入进行安全切断。

经典 NOIP/洛谷 真题

1. 洛谷 P2602 [ZJOI2010] 数字计数

• 题意描述：给定两个正整数 $a$ 和 $b$，求在 $[a, b]$ 中的所有整数中，每个数码（$0 \sim 9$）各出现了多少次。$a, b \le 10^{12}$。
• 问题本质与解题思路：多状态并发维护的数位计数问题。由于需要统计具体数码出现的频次，状态维数需要扩充。
• 核心思路：外层从 $0$ 到 $9$ 枚举当前正在统计的数码 $X$。对于数码 $X$，设计 dfs(pos, count, limit, lead)，其中 count 记录从高位到当前位已经填了多少个 $X$。在搜索到 pos == 0 时，直接返回 count 作为该分支对总频次的贡献。其中对于数码 $0$，必须严格配合 lead 标记，只有当 lead == false 时填写的 $0$ 才是有效数字，前导零状态下的 $0$ 坚决不能计入 count。

2. 洛谷 P4999 烦人的数学作业

• 题意描述：给出区间 $[L, R]$，求区间内所有整数的各个数位上的数字之和的总和。由于答案很大，结果需要对 $10^9+7$ 取模。多组数据，$L, R \le 10^{18}$。
• 问题本质与解题思路：标准数位累计和映射。
• 核心思路：数位和的累加符合数位 DP 的拓扑结构。状态设计为 dfs(pos, sum, limit, lead)，其中 sum 表示高位已经填好的数字之和。当枚举当前位填入数字 $i$ 时，下一层的状态值直接更新为 sum + i。到达叶子节点 pos == 0 时，直接返回 sum。由于多组数据且 $R$ 达到 $10^{18}$，记忆化数组大小设为 dp[20][200]（最大数位和为 $18 \times 9 = 162$），每组数据共用同一张无污染的 dp 数组即可秒杀。