数位 dp

数位 dp（digit DP）是一类专门处理「在某个数区间 $[L, R]$ 内统计满足特定数位性质的数」的动态规划技术。所谓"数位性质"，指的是只取决于数的十进制（或任意进制）表示中各位数字的性质，例如"不含数字 4"、“相邻两位之差至少为 2”、“数字之和等于 K”。这类问题看似简单，但区间上界可能高达 $10^{18}$ 甚至更大，朴素枚举必然超时；而数位 dp 利用"逐位确定 + 记忆化"的思想，把一个 $O(n)$ 的枚举压缩到 $O(\log n \cdot |\text{state}|)$ 的状态空间，是计数类问题的通用利器。

本文从动机出发，建立数位 dp 的通用框架与模板，再通过四道经典例题（不要 62、数字计数、Windy 数、数位和问题）逐步展开状态设计的演化，最后讨论二进制进阶、与字符串算法的结合、与普通 DP/容斥的横向对比，以及实战中常见的陷阱。

引言：为什么需要数位 dp

一类"看似可枚举"的计数问题

先看几个典型问题：

1. 不要 62（HDU 2089）：统计 $[n, m]$ 中不含数字 4 且不含子串 62 的数的个数，$1 \le n \le m \le 10^9$。
2. 数字计数（洛谷 P2602）：统计 $[1, n]$ 中数字 $0 \sim 9$ 各自出现的总次数，$n \le 10^{12}$。
3. Windy 数（洛谷 P2657）：统计 $[a, b]$ 中相邻两位数字之差至少为 2 的数的个数，$a, b \le 2 \times 10^9$。
4. 数位和：统计 $[1, n]$ 中数位之和恰好为 $K$ 的数的个数，$n \le 10^{18}$，$K \le 9 \times 18$。

这些问题的共同点：

• 输入规模由"数的大小"而非"元素个数"决定，上界动辄 $10^{9}$ 甚至 $10^{18}$；
• 所求性质只依赖数的各位数字，与数作为整体的大小无关；
• 求的是"满足条件的个数"，即计数而非最值。

对 $[1, 10^{18}]$ 做朴素枚举显然不可行；即使是 $O(\sqrt n)$ 也无法承受。但仔细观察：一个 $18$ 位的十进制数，本质上只有 $18$ 个"位置"，每个位置取 $0 \sim 9$。如果能把"是否满足性质"分解到逐位决策上，状态空间就骤降到 $18 \times 10 \times \cdots$ 的量级，这正是数位 dp 的核心切入点。

前缀和转化：把区间问题变成单端问题

几乎所有数位 dp 题目都先做一步转化：

$$\text{ans}(L, R) = \text{solve}(R) - \text{solve}(L - 1)$$

其中 $\text{solve}(n)$ 表示 $[1, n]$（或 $[0, n]$）内满足条件的数的个数。这样只需解决"给定上界 $n$，统计 $[0, n]$ 内满足条件的数"这一单端问题，思路统一、实现一致。后文所有例题都遵循这一范式。

💡 提示：注意 $\text{solve}(n)$ 的下界是 $0$ 还是 $1$。统计"含某子串"等问题中 $0$ 通常不满足条件，影响不大；但统计"数字 0 出现次数"时，$0$ 是否纳入计数会显著影响结果，需要单独约定。

核心思想与正确性直觉

逐位填数：把一棵巨大的搜索树压扁

把 $n$ 写成十进制字符串 $d_{L-1} d_{L-2} \cdots d_1 d_0$（$L$ 为位数）。我们要数出 $[0, n]$ 内满足条件的数。从最高位开始逐位"填数字"：

• 如果前若干位都已经填得严格小于 $n$ 的对应位，那么剩余位可以任取 $0 \sim 9$，不受 $n$ 约束；
• 如果前若干位填得恰好等于 $n$ 的对应位，那么当前位最大只能填到 $n$ 的当前位，否则会越过上界。

这个"是否仍贴着上界"的信息用一个布尔变量 limit（或 tight）携带。limit = true 表示"前缀恰好等于 $n$ 的前缀，当前位有上界限制"；limit = false 表示"前缀已严格小于 $n$，剩余位自由"。

这样，从最高位到最低位的填数过程就构成了一棵深度为 $L$、分叉最多 $10$ 的搜索树。朴素 DFS 的节点数最坏仍是 $10^L$，但绝大多数子树是同构的：只要 (剩余位数, 已携带的状态, limit=false) 相同，子树的答案就完全相同，可以记忆化复用。

记忆化生效的条件：状态等价类

记忆化能起作用，关键在于"非受限子树完全同构"。具体地说：

• 当 limit = false 时，剩余位可以任取 $0 \sim 9$，与 $n$ 的具体值无关，只与"剩余位数"和"已确定前缀携带的、影响后继决策的状态"有关；
• 当 limit = true 时，剩余位仍受 $n$ 约束，子树结构依赖于 $n$ 的剩余位，几乎不会重复，因此不记忆化（或记忆化命中率极低，通常直接跳过）。

所以模板里常见的写法是：只有 limit = false 时才查表/写表。这正是数位 dp 把指数级搜索压成多项式状态的根本原因。

三类常见状态位

一个数位 dp 的状态通常由下列位组合而成：

状态位	含义	何时需要
pos	当前填到第几位（剩余位数）	永远需要，递归层数指示器
limit	是否仍贴着上界 $n$	永远需要，处理上界约束
lead	前缀是否全为前导零	当性质与"实际位数"或"数字 0 计数"相关时需要
pre	上一位填的数字	当性质涉及相邻位关系时需要
sum	已填数位之和	当性质涉及数位和时需要
cnt	已填某数字的次数	当需要统计某数字频次时需要
mask	已用数字集合（位掩码）	当性质涉及"数字是否重复出现"时需要
mod	已填数对某模数的余数	当性质涉及整除性时需要

limit 和 lead 一般不进入记忆化键（或只在它们为 false 时记忆化），因为它们为 true 的分支是"边界路径"，几乎不可复用。

前导零的微妙之处

lead 是数位 dp 最容易出错的地方。考虑十进制数 00123，它的实际值是 123，前两个 0 是前导零，并非真正的数位。如果题目性质是"相邻两位之差至少为 2"，那么：

• 前导零的 0 不应与第一个真实数字比较（否则第一个真实数字 $d$ 必须满足 $|d - 0| \ge 2$，即 $d \ge 2$，错误地排除了 1xx 这样的合法数）；
• 因此需要用 lead 标记"当前还在前导零阶段"，此时填 0 仍是前导零，pre 不更新，直到填入第一个非零数字。

类似地，统计"数字 0 出现次数"时，前导零的 0 不应计入。lead 正是为这类区分而存在。

⚠️ 注意：lead 与 limit 同时为 true 的初始状态（即"全前导零 + 贴上界"）通常对应空数 0，需要根据题意决定是否计入。多数题目中 $0$ 要么不满足条件（如"不含 62"中 $0$ 是合法的但题目求 $[n,m]$ 通常 $n \ge 1$），要么单独处理。

通用框架与模板

下面给出一个可以套用到绝大多数数位 dp 题目的递归记忆化模板。它把上界处理、前导零处理、记忆化时机都规范化，后续每道例题只需修改"状态维度"和"转移条件"。

#include <bits/stdc++.h>
using namespace std;

// ===== 通用数位 dp 模板 =====

int a[24];              // 拆位后的数字，a[0] 为最高位
int len;                // 位数
long long dp[24][/*状态维度*/];
bool vis[24][/*状态维度*/];

// pos:   当前位下标（从 0 开始，0 = 最高位）
// limit: 是否贴上界
// lead:  是否仍在前导零阶段
// st:    其它携带的状态（依题而异）
long long dfs(int pos, bool limit, bool lead, /*状态参数*/) {
    if (pos == len) return /*终止条件：一个合法数已构造完毕，返回 1 或累加量*/;

    // 仅在"非受限 + 非前导零"时查表
    if (!limit && !lead && vis[pos][/*状态键*/]) return dp[pos][/*状态键*/];

    long long res = 0;
    int up = limit ? a[pos] : 9;       // 当前位的上界
    for (int d = 0; d <= up; d++) {
        // 跳过/特殊处理某些数字（依题而异）
        // 递归：limit 仅在贴上界且当前位也取到上界时保持 true
        //       lead 仅在前导零且当前位仍取 0 时保持 true
        res += dfs(pos + 1,
                   limit && (d == up),
                   lead && (d == 0),
                   /*更新后的状态*/);
    }

    if (!limit && !lead) {
        vis[pos][/*状态键*/] = true;
        dp[pos][/*状态键*/] = res;
    }
    return res;
}

long long solve(long long n) {
    if (n < 0) return 0;
    len = 0;
    for (long long t = n; t; t /= 10) a[len++] = t % 10;
    reverse(a, a + len);   // a[0] 为最高位
    memset(vis, 0, sizeof vis);
    return dfs(0, true, true, /*初始状态*/);
}

模板的关键约定：

1. 数位从高位到低位处理（a[0] 为最高位），符合直觉；
2. limit、lead 不进记忆化键，只在 !limit && !lead 时记忆化；
3. up 由 limit 决定：贴上界时只能取到 $n$ 的当前位，否则自由取 $0 \sim 9$；
4. 转移时同步更新 limit 与 lead：limit && d == up 表示"之前贴上界且当前也贴上界，则继续贴"；lead && d == 0 表示"之前全前导零且当前仍填 0，则继续前导零"。

理解了模板，后续每道题本质上是"选择状态维度 + 定义转移条件"的填空题。

经典例题一：不要 62（HDU 2089）

问题描述

统计 $[n, m]$ 中"吉利数"的个数。吉利数定义为：不含数字 4，且不含子串 62。多组数据，$1 \le n \le m \le 10^9$，输入以 0 0 结束。

思路

这是数位 dp 的入门模板题，性质只涉及"单个数字"和"相邻两位"，状态需要：

• pre：上一位数字，用于判断子串 62；
• lead：处理前导零（虽然本题前导零不实质影响"不含 4/62"，但保留 lead 让模板统一，且能正确处理前导零阶段的 pre）。

转移条件：

1. 当前位 d == 4 直接跳过；
2. pre == 6 && d == 2 跳过（构成 62）；
3. 否则递归。

完整代码

#include <bits/stdc++.h>
using namespace std;

int a[12], len;
long long dp[12][10];
bool vis[12][10];

// pos: 当前位; pre: 上一位数字(lead 时记为 0, 不影响判断);
// limit: 贴上界; lead: 前导零
long long dfs(int pos, int pre, bool limit, bool lead) {
    if (pos == len) return 1;  // 走完所有位，得到一个合法数
    if (!limit && !lead && vis[pos][pre]) return dp[pos][pre];
    long long res = 0;
    int up = limit ? a[pos] : 9;
    for (int d = 0; d <= up; d++) {
        if (d == 4) continue;                 // 不含 4
        if (pre == 6 && d == 2) continue;     // 不含 62
        res += dfs(pos + 1, d, limit && d == up, lead && d == 0);
    }
    if (!limit && !lead) { vis[pos][pre] = true; dp[pos][pre] = res; }
    return res;
}

long long solve(long long n) {
    if (n < 0) return 0;
    if (n == 0) return 1;       // 0 视为合法（不含 4 也不含 62）
    len = 0;
    for (long long t = n; t; t /= 10) a[len++] = t % 10;
    reverse(a, a + len);
    memset(vis, 0, sizeof vis);
    return dfs(0, 0, true, true);
}

int main() {
    long long l, r;
    while (cin >> l >> r && (l || r))
        cout << solve(r) - solve(l - 1) << "\n";
    return 0;
}

复杂度分析

• 状态数：$O(L \cdot 10)$，$L$ 为位数，本题 $L \le 10$；
• 转移：每位枚举 $10$ 个数字；
• 总复杂度：$O(L \cdot 100)$ 每次查询，加上拆位 $O(L)$。多组数据下完全无压力。

变种与扩展

• 不含某子串 49（HDU 3555 Bomb）：把 pre==6 改成 pre==4、d==2 改成 d==9 即可；
• 不含任意给定模式串：当模式串长度 $\ge 3$ 时，pre 不够用，需要用 KMP 自动机状态 替代–把"已匹配模式串的前缀长度"作为状态位，这是数位 dp 与字符串算法结合的常见升级（参见后文进阶一节）；
• 求最大吉利数 / 第 k 小吉利数：在 dp 值（子树大小）已知后，按位贪心"试填"即可二分定位。

经典例题二：数字计数（洛谷 P2602）

问题描述

给定 $n$，统计 $[1, n]$ 中数字 $0, 1, \dots, 9$ 各自出现的总次数。$n \le 10^{12}$。

例如 $n = 13$ 时，$1 \sim 13$ 中数字 $1$ 出现 $6$ 次（$1, 10, 11, 12, 13$ 中的所有 $1$），数字 $0$ 出现 $0$ 次。

思路

这是"统计某数字频次"的代表性题目。对每个目标数字 $x \in \{0, \dots, 9\}$ 单独跑一次数位 dp，累加 $x$ 出现的次数。

状态需要：

• cnt：到目前为止 $x$ 出现的次数。cnt 的范围可达 $L$，直接作为维度会让状态数膨胀到 $O(L^2)$–仍然可接受（$L \le 13$），但更优雅的做法是累加贡献而非把 cnt 入状态（见下方"贡献法"）。

这里先给出"入状态"的朴素写法，再给出更高效的"贡献法"。

前导零的处理：统计 $x = 0$ 时，前导零的 0 不应计入。所以只在 !lead（已经脱离前导零）且 d == 0 时才把计数 $+1$。对 $x \ne 0$ 则无此顾虑，只要 d == x 就计数。

完整代码（朴素：cnt 入状态）

#include <bits/stdc++.h>
using namespace std;

int a[16], len;
long long dp[16][16];   // dp[pos][cnt]
bool vis[16][16];

// 统计 [0, n] 中数字 x 出现的总次数
long long dfs(int pos, int cnt, bool limit, bool lead, int x) {
    if (pos == len) return cnt;
    if (!limit && !lead && vis[pos][cnt]) return dp[pos][cnt];
    long long res = 0;
    int up = limit ? a[pos] : 9;
    for (int d = 0; d <= up; d++) {
        int ncnt = cnt;
        if (d == x && !(x == 0 && lead)) ncnt++;  // 前导零的 0 不计
        res += dfs(pos + 1, ncnt, limit && d == up, lead && d == 0, x);
    }
    if (!limit && !lead) { vis[pos][cnt] = true; dp[pos][cnt] = res; }
    return res;
}

long long count_digit(long long n, int x) {
    if (n <= 0) return 0;
    len = 0;
    for (long long t = n; t; t /= 10) a[len++] = t % 10;
    reverse(a, a + len);
    memset(vis, 0, sizeof vis);
    return dfs(0, 0, true, true, x);
}

int main() {
    long long n;
    cin >> n;
    for (int x = 0; x <= 9; x++)
        cout << count_digit(n, x) << " \n"[x == 9];
    return 0;
}

⚠️ 注意：这里对 $x = 0$ 的处理：当 lead 为真时，d == 0 仍是前导零，不计入 cnt；当 lead 为假时，d == 0 才算真正的 0 数位。条件 !(x == 0 && lead) 精确表达了这个区分。如果题目要求 $0$ 也按"实际出现"统计（包括前导零），则去掉该条件–但那样会大量重复计数，几乎不是任何题目的本意。

优化：贡献法（不把 cnt 入状态）

把 cnt 入状态会让状态空间变成 $O(L^2)$。更高效的做法是逐位计算贡献：固定某一位填 $x$，其余位任取，数出该位填 $x$ 能形成多少个合法数。这就是经典的"按位计数"思路，时间复杂度 $O(L)$，无需记忆化。

但其实现涉及"高位贴上界时的低位取值范围"等细节，容易写错。本节给出基于数位 dp 框架的等价写法–返回的不是 cnt，而是"当前子树内 $x$ 出现次数的总和"：

// 贡献法：dfs 返回该子树内数字 x 出现的总次数
long long dp2[16];
bool vis2[16];

long long dfs2(int pos, bool limit, bool lead, int x) {
    if (pos == len) return 0;
    if (!limit && !lead && vis2[pos]) return dp2[pos];
    long long res = 0;
    int up = limit ? a[pos] : 9;
    for (int d = 0; d <= up; d++) {
        bool nlimit = limit && d == up;
        bool nlead  = lead && d == 0;
        // 子树叶子数：不受限时为 10^(len-pos-1)，受限时需递归计数
        long long leaves = subtree_size(pos + 1, nlimit, nlead);
        res += dfs2(pos + 1, nlimit, nlead, x);
        if (d == x && !(x == 0 && lead))
            res += leaves;     // 当前位在每个叶子各出现 1 次
    }
    if (!limit && !lead) { vis2[pos] = true; dp2[pos] = res; }
    return res;
}

其中 subtree_size 是"剩余位任取时形成的数的个数"，不受限时为 $10^{\text{剩余位数}}$，受限时需递归计算。这种写法把状态压回 $O(L)$，但对初学者不够直观。实践中朴素写法 $O(L^2)$ 已经足够快（$L \le 18$ 时仅约 $324$ 个状态），建议优先保证正确性，再考虑优化。

复杂度分析

• 朴素写法：对每个 $x$ 跑一次，每次 $O(L^2)$ 状态，总复杂度 $O(10 \cdot L^2)$；
• 贡献法：$O(10 \cdot L)$；
• 本题 $L \le 13$，两种写法都能轻松通过。

变种

• 统计二进制下 $1$ 的个数之和（如 POJ 3252 Round Numbers 的近亲）：把进制改为 2，思路一致；
• 区间内所有数的数位和之和：把 cnt 换成 sum，转移时 sum += d；
• 多数字同时统计：用 dp[pos] 返回一个长度为 $10$ 的数组，一次递归同时累加所有数字的贡献，避免跑 $10$ 遍。

经典例题三：Windy 数（洛谷 P2657）

问题描述

Windy 数定义：不含前导零，且相邻两位数字之差的绝对值至少为 $2$ 的正整数。给定 $[a, b]$，统计其中 Windy 数的个数。$1 \le a \le b \le 2 \times 10^9$。

例如 $135$ 是 Windy 数（$|1-3|=2, |3-5|=2$）；$121$ 不是，因为 $|2-1|=1 < 2$。

思路

本题是"相邻位约束"的典型，pre（上一位数字）是核心状态。前导零处理尤为关键：

• 前导零阶段，pre 不应取 0 参与差值比较，否则第一个真实数字 $d$ 必须满足 $|d - 0| \ge 2$，即 $d \ge 2$，错误排除了 $1$ 开头的数（如 $135$）；
• 因此约定：lead 为真时跳过差值检查；或者用一个"哨兵值"（如 $-10$）作为 pre，使任何真实数字 $d$ 都能通过 $|d - (-10)| \ge 2$。

转移条件：lead || abs(d - pre) >= 2 时才递归。

完整代码

#include <bits/stdc++.h>
using namespace std;

int a[12], len;
long long dp[12][10];
bool vis[12][10];

// pre: 上一位数字; limit/lead 同前
long long dfs(int pos, int pre, bool limit, bool lead) {
    if (pos == len) return 1;   // 走完所有位即一个合法 Windy 数
    if (!limit && !lead && vis[pos][pre]) return dp[pos][pre];
    long long res = 0;
    int up = limit ? a[pos] : 9;
    for (int d = 0; d <= up; d++) {
        if (!lead && abs(d - pre) < 2) continue;  // 非前导零时检查差值
        res += dfs(pos + 1, d, limit && d == up, lead && d == 0);
    }
    if (!limit && !lead) { vis[pos][pre] = true; dp[pos][pre] = res; }
    return res;
}

long long solve(long long n) {
    if (n <= 0) return 0;
    len = 0;
    for (long long t = n; t; t /= 10) a[len++] = t % 10;
    reverse(a, a + len);
    memset(vis, 0, sizeof vis);
    return dfs(0, 0, true, true);
}

int main() {
    long long l, r;
    cin >> l >> r;
    cout << solve(r) - solve(l - 1) << "\n";
    return 0;
}

前导零为何不能省

如果把 lead 去掉、直接用 pre=0 作为初值，会发生什么？以 $n = 135$ 为例，最高位填 1 时，abs(1 - 0) = 1 < 2，被错误剪枝，导致所有 $1$ 开头的 Windy 数（包括 $135$ 本身）全部丢失。lead 的作用正是告诉递归：“当前还没有真正的数字，pre 是无效的，不要参与差值检查”。

这与例题一的 lead 角色不同：例题一中前导零不影响"不含 4/62"的判断（前导零的 0 既不是 4 也不构成 62），lead 仅用于规范记忆化；本题则直接决定转移合法性，缺之即错。

复杂度分析

• 状态数 $O(L \cdot 10)$，转移 $O(10)$，总 $O(L \cdot 100)$；
• $L \le 10$，毫秒级。

变种

• 相邻两位之差恰好为某值 / 至多为某值：调整 abs(d - pre) 的比较条件；
• 不含相邻相同数字：d != pre；
• 回文数计数：需要双向填数（从两端向中间），状态需携带"另一端已填的数字"，是数位 dp 的进阶扩展。

经典例题四：数位和问题与最大数字和

问题描述（数位和等于 K）

给定 $n$ 和 $K$，统计 $[1, n]$ 中数位之和恰好为 $K$ 的数的个数。$n \le 10^{18}$，$K \le 9 \times 18 = 162$。

最大数字和变体：给定 $[L, R]$，求其中所有数数位和的最大值，以及达到该最大值的数的个数。

思路

sum（已填数位之和）作为状态维度。转移：sum += d。终止：pos == len 时返回 sum == K。

sum 的范围是 $[0, 9L]$，本题 $L \le 18$，所以 sum 维度最大 $162$，状态数 $O(L \cdot 162)$，完全可接受。

前导零：前导零的 0 会使 sum 保持不变，自然不贡献–这正是我们想要的（前导零不是真实数位），因此本题 lead 不影响 sum 的正确性，但仍建议保留 lead 以规范记忆化（避免把"前导零路径"与"真实路径"混入同一状态键）。

完整代码（数位和等于 K）

#include <bits/stdc++.h>
using namespace std;

int a[20], len;
long long dp[20][170];   // dp[pos][sum]
bool vis[20][170];
int K;

long long dfs(int pos, int sum, bool limit, bool lead) {
    if (sum > K) return 0;            // 剪枝：和已超 K
    if (pos == len) return sum == K ? 1 : 0;
    if (!limit && !lead && vis[pos][sum]) return dp[pos][sum];
    long long res = 0;
    int up = limit ? a[pos] : 9;
    for (int d = 0; d <= up; d++) {
        res += dfs(pos + 1, sum + d, limit && d == up, lead && d == 0);
    }
    if (!limit && !lead) { vis[pos][sum] = true; dp[pos][sum] = res; }
    return res;
}

long long solve(long long n, int k) {
    if (n <= 0) return 0;
    len = 0;
    for (long long t = n; t; t /= 10) a[len++] = t % 10;
    reverse(a, a + len);
    memset(vis, 0, sizeof vis);
    K = k;
    return dfs(0, 0, true, true);
}

int main() {
    long long n; int k;
    cin >> n >> k;
    cout << solve(n, k) << "\n";
    return 0;
}

最大数字和

“最大数字和"本身是简单的贪心：对上界 $n$，从高到低尝试"当前位减 1，其后全 9”，得到的数位和取最大值即为答案。例如 $n = 348$：候选有 $348 \to 3+4+8=15$、$299 \to 2+9+9=20$、$99 \to 18$，最大为 $20$（对应数 $299$）。

但"达到最大数位和的数的个数"则需要数位 dp：令 $K$ 为最大数位和，则答案即 $\text{solve}(R, K) - \text{solve}(L - 1, K)$。这就把"最大数字和"问题自然纳入数位和统计的框架。

// 计算不超过 n 的数中，数位和的最大值
int max_digit_sum(long long n) {
    if (n <= 0) return 0;
    // 贪心：逐位尝试借位后全 9
    vector<int> d;
    for (long long t = n; t; t /= 10) d.push_back(t % 10);
    reverse(d.begin(), d.end());
    int best = 0;
    for (int x : d) best += x;        // 原数本身的数位和
    for (int i = 0; i < (int)d.size(); i++) {
        if (d[i] == 0) continue;      // 该位无法借位
        int s = 0;
        for (int j = 0; j < i; j++) s += d[j];
        s += d[i] - 1;                // 当前位减 1
        s += 9 * ((int)d.size() - i - 1);  // 其后全 9
        best = max(best, s);
    }
    return best;
}

// 配合上文的 solve(n, K) 即可求"达到最大数位和的数的个数"
//   count_max(L, R) = solve(R, max_digit_sum(R)) - solve(L-1, max_digit_sum(R))

复杂度分析

• 数位和等于 $K$：状态 $O(L \cdot 9L) = O(L^2)$，转移 $O(10)$，总 $O(L^2)$；
• 最大数字和贪心：$O(L)$；
• $L \le 18$，极快。

变种

• 数位和是 $K$ 的倍数：用 sum 对 $K$ 取模作为状态（mod）；
• 数位和为质数：先筛出 $\le 9L$ 的质数，对每个质数 $p$ 跑一次 $\text{solve}(n, p)$ 求和；或直接在终止处判断 sum 是否为质数；
• 数位和等于 $K$ 且不含某子串：组合 sum 与 pre 两个状态维度；
• 整除性（如 $[1, n]$ 中能被 $K$ 整除的数）：状态用 mod（已填数对 $K$ 取模），终止 mod == 0。注意当 $K$ 较大时（如 $K \le 10^4$），状态数 $O(L \cdot K)$ 仍可接受；但 $K$ 极大时需换思路（如利用数论性质）。

进阶：二进制数位 dp 与 Round Numbers

数位 dp 不限于十进制。把"进制"换成 $2$，所有框架照搬适用。Round Numbers（POJ 3252）是经典二进制数位 dp：

统计 $[L, R]$ 中二进制表示下 0 的个数不少于 1 的个数的正整数个数（无前导零）。$L, R \le 2 \times 10^9$。

状态需要携带"0 个数与 1 个数的差"或两者计数。由于差的范围是 $[-L, L]$，可平移到 $[0, 2L]$ 作为数组下标。

#include <bits/stdc++.h>
using namespace std;

int a[34], len;
long long dp[34][70];   // dp[pos][dif+34]，dif = cnt1 - cnt0，平移避免负下标
bool vis[34][70];

// dif: cnt1 - cnt0 (已填部分). lead 时填 0 不计入，填 1 脱离前导零
long long dfs(int pos, int dif, bool limit, bool lead) {
    if (pos == len) return dif <= 0 ? 1 : 0;   // 1 的个数 <= 0 的个数
    if (!limit && !lead && vis[pos][dif + 34]) return dp[pos][dif + 34];
    long long res = 0;
    int up = limit ? a[pos] : 1;   // 二进制：上界 1
    for (int d = 0; d <= up; d++) {
        int ndif = dif;
        if (!lead || d == 1) {     // 前导零阶段填 0 不计数；填 1 脱离前导零
            if (d == 1) ndif++;
            else ndif--;
        }
        res += dfs(pos + 1, ndif, limit && d == up, lead && d == 0);
    }
    if (!limit && !lead) { vis[pos][dif + 34] = true; dp[pos][dif + 34] = res; }
    return res;
}

long long solve(long long n) {
    if (n <= 0) return 0;
    len = 0;
    for (long long t = n; t; t >>= 1) a[len++] = t & 1;
    reverse(a, a + len);
    memset(vis, 0, sizeof vis);
    return dfs(0, 0, true, true);
}

int main() {
    long long l, r;
    cin >> l >> r;
    cout << solve(r) - solve(l - 1) << "\n";
    return 0;
}

二进制数位 dp 在以下场景常见：

• 统计二进制下 1 的个数（popcount）满足某条件的数；
• 异或/位运算相关计数（如"与 $X$ 异或后 $\le K$ 的数"）；
• 数位压成布尔状态，结合 mask 表示已用位集合。

进制 $B$ 越大，状态空间越大（每位 $B$ 种取值），但位数 $\log_B n$ 越小，权衡视题目而定。

进阶：与字符串算法结合（模式串匹配）

当约束变为"不含某个长度 $\ge 3$ 的模式串 $P$"时，单靠 pre（上一位）不足以描述匹配进度。此时需要把 KMP 自动机的状态嵌入数位 dp：

• 预处理 $P$ 的 next 数组，构造一个状态机：状态 $s$ 表示"当前已匹配 $P$ 的前缀长度为 $s$"；
• 数位 dp 状态增加 s：填入数字 $d$ 后，根据 KMP 自动机转移 s = trans[s][d]；
• 若 s == |P| 则表示匹配到模式串，按题意计数或排除。

// 概念示意：不含模式串 P（全部由数字组成）的数的个数
int nxt[24];                 // KMP next 数组
int trans[24][10];           // trans[s][d] = 状态 s 读入 d 后的新状态

void build(const string& P) {
    int m = P.size();
    nxt[0] = 0;
    for (int i = 1, j = 0; i < m; i++) {
        while (j && P[i] != P[j]) j = nxt[j - 1];
        if (P[i] == P[j]) j++;
        nxt[i] = j;
    }
    for (int s = 0; s <= m; s++)
        for (int d = 0; d < 10; d++) {
            int j = s;
            while (j && (j == m || P[j] - '0' != d)) j = nxt[j - 1];
            if (j < m && P[j] - '0' == d) j++;
            trans[s][d] = j;
        }
}

// dfs 中增加状态 s；s == m 表示已匹配模式串，需排除
long long dfs(int pos, int s, bool limit, bool lead, int m) {
    if (s == m) return 0;          // 已匹配模式串，排除
    if (pos == len) return 1;
    if (!limit && !lead && vis[pos][s]) return dp[pos][s];
    long long res = 0;
    int up = limit ? a[pos] : 9;
    for (int d = 0; d <= up; d++) {
        int ns = (lead && d == 0) ? 0 : trans[s][d];  // 前导零不推进匹配
        res += dfs(pos + 1, ns, limit && d == up, lead && d == 0, m);
    }
    if (!limit && !lead) { vis[pos][s] = true; dp[pos][s] = res; }
    return res;
}

这一思路可推广到 AC 自动机（多模式串）、后缀自动机等，是数位 dp 与字符串结合的通用范式。注意前导零阶段通常不应推进模式串匹配（前导零不是真实数位），因此 lead && d == 0 时把 s 重置为 $0$。

横向对比：数位 dp vs 普通 dp vs 容斥

数位 dp 与普通 dp

维度	普通 dp	数位 dp
状态来源	问题结构的子问题分解	数的"位"与"上界贴边信息"
转移方向	通常从前往后 / 从小到大	固定从高位到低位
上界处理	一般无显式上界，或上界即规模	limit 位是核心，处理 $[0, n]$
记忆化时机	所有状态都可记忆化	仅 !limit（且常 !lead）时记忆化
典型规模	由元素个数 / 容量决定	由位数 $\log n$ 决定
适用问题	最值、方案数、可行性	计数（满足数位性质的个数）

普通 dp 解决"规模为 $n$ 的问题"，状态空间常与 $n$ 同阶；数位 dp 解决"上界为 $n$ 的计数"，状态空间与 $\log n$ 同阶。两者本质都是"状态 + 转移 + 记忆化"，但数位 dp 的"上界贴边"机制是它独有的。

数位 dp 与容斥原理

很多数位 dp 题目也能用容斥解决，反之亦然。例如"不含数字 4 的数"等价于"总数 $-$ 至少含一个 4 的数"，后者可用容斥展开。但：

• 容斥适用于"约束可分解为若干独立事件的交并"，当约束涉及相邻位（如 Windy 数）时容斥展开极复杂，数位 dp 更直接；
• 数位 dp 适用于"约束可逐位判定"，当约束是"恰好出现 $k$ 次某数字"这类全局约束时，仍可做但状态需携带计数；
• 两者常结合：用容斥把"至少含某模式"转化为"总数 $-$ 不含某模式"，后者用数位 dp 求解（这正是例题一的范式）。

数位 dp 的两种实现风格

数位 dp 有两种实现风格：

1. 递归记忆化（本文模板）：自顶向下，limit/lead 作为参数，逻辑直观，是竞赛主流写法；
2. 递推填表：自底向上，先预处理"不受限"的 f[pos][...]，再单独处理"贴上界"路径。代码更冗长但常数更小，适合卡常的题目。

两者等价。本文统一用递归记忆化，因其更易写对、更易扩展。

实战场景

竞赛中的应用

数位 dp 是 ICPC / CCPC / 省选 / AtCoder / Codeforces 中的常见考点，典型题型包括：

• 区间计数：洛谷 P2602、P2657、HDU 2089 等模板题；
• 第 k 小 / 大满足条件的数：先 dp 求出子树大小，再按位贪心试填（如"第 k 个不含 4 的数"）；
• 数位和与整除性结合：SPOJ、Codeforces 上"数位和为质数"等；
• 位运算计数：Codeforces 经典"区间内 popcount(x) <= k 的数的个数"、"x XOR v <= K"的数；
• 多模式串约束：结合 KMP/AC 自动机的状态数位 dp（如"不含给定多个子串的数的个数"）；
• 高维数位 dp：同时对两个数 $a, b$ 做数位 dp（如统计满足 $a + b \le n$ 且 $a, b$ 满足某性质的数对个数），状态维度翻倍。

第 k 小试填：子树大小驱动贪心

数位 dp 除了"计数"，还能解决"第 k 小满足条件的数"。思路：先用 dp 预处理"不受限状态下，从某状态出发还能构造多少个合法数"（即子树大小），然后从最高位开始逐位贪心：

• 对当前位，从小到大枚举 $d$，查"若填 $d$，剩余位能构造多少个合法数"；
• 若该数 $\ge k$，则当前位确定填 $d$，进入下一层；
• 否则 $k$ 减去该数，继续尝试更大的 $d$。

// 概念示意：求第 k 个不含数字 4 的正整数
long long kth_no4(long long k) {
    long long ans = 0;
    int pos = 0, pre = 0;
    bool lead = true;
    while (k > 0) {
        for (int d = (lead ? 1 : 0); d <= 9; d++) {  // 首位不可为 0
            if (d == 4) continue;
            long long cnt = subtree(pos + 1, d, false, lead && d == 0);
            if (cnt >= k) { ans = ans * 10 + d; pre = d; pos++; lead = false; break; }
            else k -= cnt;
        }
    }
    return ans;
}

其中 subtree 复用前文 dfs 的 dp 表（不受限分支）。这种"dp 预处理 + 按位贪心"是数位 dp 解"第 k 小"的通用模式，也常用于"在合法数中二分查找"。

工程中的应用

虽然工程中极少直接遇到"统计 $[1, 10^{18}]$ 内满足条件的数"这样的需求，但数位 dp 的思想–用"是否贴边"压缩状态空间、把全局约束分解为逐位决策–在以下场景有迁移价值：

• ID 生成与校验：校验"给定区间内满足校验位规则的 ID 个数"（如 ISBN、信用卡 Luhn 校验的组合分析）；
• 数字水印与编码：统计满足特定数位规则的编码空间大小；
• 数据分析：估算满足某数位特征的数值分布（如"以特定前缀开头的号码在区间内的占比"）；
• 形式化验证：模型检查中"满足某约束的位串计数"本质即二进制数位 dp。

掌握数位 dp 的核心收益不在"工程中复用代码"，而在训练"把指数级枚举压缩为对数级状态"的思维–这种"识别同构子问题 + 用边界位携带上界信息"的技巧，是算法设计的通用素养。

常见陷阱与边界条件

1. solve(0) 与下界

solve(n) 通常统计 $[0, n]$。当题目求 $[1, n]$ 时，需检查 $0$ 是否满足条件：

• "不含 62"中 $0$ 满足，但 $[1, n]$ 应减去 $0$，即 $\text{solve}(n) - \text{solve}(0)$，其中 $\text{solve}(0) = 1$（$0$ 本身）。多数实现里 solve(0) 返回 $1$（因为 $0$ 不含 4 也不含 62），所以 $\text{solve}(n) - 1$ 才是 $[1, n]$ 的答案。但模板题求 $[n, m]$，做 $\text{solve}(m) - \text{solve}(n-1)$ 时 $0$ 自动被对消，无需特殊处理；
• "正整数"语义的题（如 Windy 数要求正整数）应让 solve(0) = 0，本文代码用 if (n <= 0) return 0 处理。

务必先明确 solve(0) 的语义，再决定前缀相减时是否需要 $\pm 1$。

2. 前导零与 pre 初值

lead 为真时 pre 的取值必须"不干扰后继判断"：

• Windy 数中，lead 时跳过差值检查，pre 取何值都行（代码中 pre 实际不参与），但若用"哨兵值"法（如 pre = -10），需保证哨兵不与任何真实数字触发非法转移；
• 不要用 pre = 0 作为前导零阶段的初值并参与比较–这正是 Windy 数最易踩的坑。

3. 记忆化时机

只在 !limit && !lead 时记忆化。常见错误：

• 把 limit 也写入键并记忆化：看似正确，但 limit = true 的状态几乎不重复，白白占用空间且无加速，更危险的是若上界 $n$ 在多组数据间变化，残留的 vis 会导致答案串台；
• 多组数据务必 memset(vis)：上一组的记忆化结果会被本组复用，且 limit 路径的"伪记忆"可能错误，导致答案错乱。

4. long long 与溢出

$n \le 10^{18}$ 时，$[0, n]$ 内数的个数可达 $10^{18}$，远超 int。dp 值与返回值一律用 long long。sum、cnt 等小范围状态用 int 即可，但累加结果必须 long long。

5. 上界拆位方向

本文模板把 $n$ 拆位后 reverse，使 a[0] 为最高位、从高位向低位递归。若采用"从低位向高位"的写法，limit 的语义会变（贴上界信息无法逐位传递），通常不推荐。统一从高位到低位是数位 dp 的标准约定。

6. lead 与 limit 同时为真的初始状态

初始调用 dfs(0, true, true, ...) 表示"从最高位开始，贴上界，全前导零"。这一状态对应"数 0"的构造路径，终止时 pos == len 返回的值即"$0$ 是否满足条件"。若题目排除 $0$，需在最终答案中减去这一项，或调整终止条件（如 Windy 数 solve(0) = 0）。

7. 状态维度爆炸

当约束复杂时（如同时携带 sum、pre、mask、mod），状态数可能爆炸。应对策略：

• 剪枝不可达状态：如 sum > K 时直接返回 0；
• 降维：如"数位和为 $K$ 的倍数"用 mod 替代 sum；
• 分治/折半：位数极多时（如 $10^{100}$），可用 meet-in-the-middle；
• 换模型：某些约束用容斥、生成函数或矩阵快速幂更高效。

8. 多组数据的状态重置

多组数据下，全局的 dp/vis 数组、以及作为全局变量的状态参数（如 K、模式串 m）都必须在每组开始前重置。若状态维度本身不变（如 dp[pos][sum]）但语义依赖全局参数（如 K），仅 memset(vis) 还不够，必须同时更新全局参数，否则查表命中后返回的是基于旧参数的答案。

小结

数位 dp 的本质是：把"上界为 $n$ 的计数"转化为"在 $n$ 的数位表示上逐位决策的搜索"，再用记忆化把指数级搜索树压成多项式状态空间。其通用性来自三个机制：

1. 逐位填数：从高位到低位，每位枚举 $0 \sim \text{up}$；
2. limit 携带上界：区分"贴上界"与"自由填"，仅自由分支记忆化；
3. lead 处理前导零：区分"前导零"与"真实数位"，保证涉及位数/相邻位/数字 0 计数的性质正确判定。

掌握本文的通用模板与四道经典例题（不要 62、数字计数、Windy 数、数位和），即可覆盖绝大多数数位 dp 题目。进阶方向包括：二进制/任意进制数位 dp、与 KMP/AC 自动机结合的模式串约束、第 k 小试填、多变量联合数位 dp 等。核心思维–“识别同构子问题 + 用边界位携带上界信息”–远比具体模板重要，是计数问题中最具迁移价值的算法工具之一。