1. 从一道题看数位DP的核心思想B-number 这个题名看着朴素实际上是一道非常经典的数位DP入门到进阶的过渡题。它的核心要求通常是统计某个区间内满足特定数字结构条件的数的个数而 B-number 的经典定义是——数字的十进制表示中包含连续子串 13并且整个数能被 13 整除。这两个条件叠加在一起就把单纯的数位DP和状态压缩、取模运算结合起来了。我第一次接触这个题的时候第一反应是暴力枚举但一看数据范围就放弃了——区间上界通常能到 10^9 甚至更大暴力枚举每个数再判断时间复杂度直接爆炸。这时候数位DP就派上用场了。数位DP的本质是把“逐个数判断”转化为“逐位构造数字”在构造的过程中记录必要的信息从而避免重复计算。为什么叫“数位”DP因为我们是在数字的每一位上做决策。比如一个数有 n 位我们从最高位开始一位一位地决定这一位填什么数字同时维护一些状态信息。这些状态信息就是DP的“状态”它们必须能够完整描述当前构造进度下对后续决策有影响的所有信息。对于 B-number 来说我们需要维护哪些状态至少有三个维度当前处理到第几位、当前数字对13取模的余数、以及当前是否已经出现了 13 这个子串。但这里有个细节——判断是否出现 13 不能只看“有没有出现过”还要看“上一位是不是1”因为如果上一位是1当前位填3那就形成了新的 13。所以状态设计上通常用两个标记来区分一个是“是否已经出现过13”另一个是“上一位是否为1”。这两个标记可以合并成一个三值状态0表示还没出现13且上一位不是11表示还没出现13但上一位是12表示已经出现过13。这个状态设计是数位DP里非常典型的技巧。很多新手会想我直接记录“是否出现过13”不就行了吗为什么还要记录“上一位是不是1”原因很简单——如果你只记录“是否出现过13”那么当你在某一位填3的时候你无法判断上一位是不是1也就无法确定这个3是否和前面的1构成了 13。所以必须把“上一位是否为1”这个信息也纳入状态。再来说取模。判断一个数能否被13整除不需要知道这个数的完整值只需要知道它对13的余数。在逐位构造数字的过程中余数可以递推更新如果当前已经构造的部分对13的余数是 r那么在这个数后面再添一位数字 d新的余数就是 (r * 10 d) % 13。这个递推关系是数位DP能够处理整除问题的关键。把这三个维度组合起来状态就是 dp[pos][rem][state]其中 pos 表示当前处理到第几位从高位到低位rem 表示当前构造出的前缀对13的余数state 表示与 13 相关的状态。这个状态空间的大小大约是 位数 × 13 × 3对于常见的10位数字来说也就是 10 × 13 × 3 390 个状态非常小。每个状态的计算只需要枚举当前位填0到9所以总计算量也很小。但数位DP还有一个关键点上界限制。我们不能简单地枚举所有数字因为题目通常要求统计某个区间 [L, R] 内满足条件的数。直接统计区间不好做通常转化为前缀统计count(R) - count(L-1)。而 count(N) 表示统计 0 到 N 之间满足条件的数的个数。在统计 count(N) 的时候我们需要处理“当前位是否受到N的对应位的限制”。如果前面所有位都和N的对应位相等那么当前位只能填 0 到 N 的当前位否则当前位可以填 0 到 9。这个“是否受限”的标记通常用 limit 表示它不需要作为DP状态的一部分来记忆化因为它只在当前搜索路径上有效不同路径的 limit 状态不会共享。所以完整的DFS函数签名通常是dfs(pos, rem, state, limit)其中 pos、rem、state 用于记忆化limit 用于控制当前位的枚举范围。记忆化的条件是 !limit因为当 limit 为真时当前状态依赖于具体的N不能直接复用。2. 状态设计与转移方程的细节拆解2.1 三个核心状态维度的含义与取值先明确 pos 的含义。通常我们把数字的各位拆开从最高位开始编号。比如数字 12345最高位是1对应 pos0或者 pos5取决于实现习惯。我个人的习惯是让 pos 表示“当前还需要处理几位”或者“当前正在处理从高位数起的第几位”。两种方式都可以关键是递归的终止条件和状态转移要一致。rem 的取值范围是 0 到 12因为是对13取模。初始时在最高位之前我们可以认为已经构造的前缀是空空串对应的数值是0所以初始 rem 0。每填一位数字 d新的 rem (rem * 10 d) % 13。这个递推的正确性可以用数学归纳法证明假设当前前缀表示的数值是 X那么 X % 13 rem。在 X 后面添一位 d新的数值是 X * 10 d它对13的余数就是 (X * 10 d) % 13 ((X % 13) * 10 d) % 13 (rem * 10 d) % 13。所以递推是严格的。state 的取值我前面说了是0、1、2。具体定义如下state 0当前前缀中还没有出现过 13且当前前缀的最后一位不是1或者前缀为空。state 1当前前缀中还没有出现过 13但当前前缀的最后一位是1。state 2当前前缀中已经出现过 13。状态转移规则如果当前 state 0填 d 1则新 state 1最后一位变成1。填 d 3则新 state 0因为上一位不是1所以不构成13且当前位是3不是1。填其他数字新 state 0。如果当前 state 1填 d 3则新 state 2形成了13。填 d 1则新 state 1最后一位仍然是1。填其他数字新 state 0最后一位不是1了。如果当前 state 2无论填什么新 state 都保持 2已经出现过13不会再消失。这个转移规则可以用一个简单的函数来实现也可以用打表的方式预先算好。我通常写一个 nxt(state, d) 函数返回新的 state。2.2 记忆化搜索的边界条件与返回值递归的终止条件是 pos 处理完了所有位。此时我们需要判断当前构造出的完整数字是否满足条件state 2 且 rem 0。如果满足返回1否则返回0。注意这里还要考虑前导零的问题。如果题目统计的是正整数那么全零的情况即数字0是否算通常 B-number 要求是正整数所以数字0不算。但我们的DFS如果从最高位开始枚举且允许前导零那么全零的路径会构造出数字0。数字0的 state 是0没有出现过13rem 是0但 state ! 2所以不会被计数。所以前导零在这里不会造成误计数。但如果题目对前导零有特殊要求比如不允许前导零影响状态判断那就需要额外处理。对于 B-number 来说前导零不影响因为0不满足 state2。记忆化的实现用一个三维数组 dp[pos][rem][state] 来记录结果。初始化为 -1。在 dfs 函数中如果 !limit 且 dp[pos][rem][state] ! -1直接返回。否则进行计算计算完后如果 !limit则存入 dp 数组。这里有一个常见的坑dp 数组的初始化。如果多组测试数据且每组数据的上界不同那么 dp 数组是否可以复用答案是如果 dp 数组只依赖于 pos、rem、state而不依赖于具体的上界N那么它可以复用。因为记忆化的是“在没有上界限制的情况下从当前状态出发能构造出多少个满足条件的后缀”。这个值与N无关。所以对于多组数据只需要在程序开始时初始化一次 dp 数组为 -1之后每组数据都可以直接使用。但要注意如果题目中数字的位数不同pos 的含义可能会变。比如第一组数据上界是 9993位第二组是 99994位那么 pos 的取值范围不同dp 数组的维度可能需要调整。通常我们可以固定最大位数比如最多10位那么 dp 数组大小就是 [11][13][3]足够覆盖所有情况。2.3 上界限制 limit 的处理技巧limit 的处理是数位DP的另一个关键。在 dfs 中我们传入一个 bool 类型的 limit表示当前位是否受到上界N的对应位的限制。如果 limit 为真那么当前位能填的最大数字是 N 的当前位记为 digit[pos]否则可以填到9。枚举当前位数字 d 时新的 limit 是 limit (d digit[pos])。也就是说只有当之前一直受限且当前位也填了上界的对应位新的 limit 才为真。这里有一个细节如果 limit 为真我们能不能记忆化不能。因为当 limit 为真时后续可填的数字范围依赖于具体的N不同的N会导致不同的结果。所以记忆化只在 !limit 时进行。这也是为什么 dp 数组记录的是“无限制”情况下的结果。有些实现会把 limit 也作为状态的一部分但那样会导致 dp 数组多一维而且实际上 limit 为真的状态很少被重复访问记忆化收益不大。所以标准做法是不把 limit 纳入记忆化。2.4 前导零的处理与数字0的特殊性前导零在数位DP中是一个容易出错的地方。如果题目统计的是“数字的十进制表示”那么前导零不应该影响数字的结构。比如数字 013 实际上就是 13它包含 13 子串吗如果按字符串看013 包含 13但按数字看13 也包含 13。所以前导零不影响 13 的判断。但对于取模前导零也不影响因为 013 13对13取模的结果是一样的。但有一种情况需要注意如果题目要求数字中不能有前导零或者前导零会影响状态比如统计某种特定模式的数字那就需要额外处理。对于 B-number前导零不影响所以我们可以放心地允许前导零。不过有一个小问题如果从最高位开始枚举且允许前导零那么数字0会被构造出来。数字0的 state 是0rem 是0不满足 state2所以不会被计数。但如果题目统计的是“非负整数”且0满足条件比如0能被13整除那就需要单独处理。B-number 通常要求正整数所以0不算。3. 完整代码实现与逐行解析3.1 代码框架与全局变量定义#include bits/stdc.h using namespace std; int digit[15]; // 存储上界N的各位数字从高位到低位 int dp[15][13][3]; // 记忆化数组 // 状态转移函数当前状态为state填数字d返回新状态 int nxt(int state, int d) { if (state 2) return 2; if (state 1) { if (d 3) return 2; if (d 1) return 1; return 0; } // state 0 if (d 1) return 1; return 0; } // DFS函数 int dfs(int pos, int rem, int state, bool limit) { if (pos -1) { return (state 2 rem 0) ? 1 : 0; } if (!limit dp[pos][rem][state] ! -1) { return dp[pos][rem][state]; } int up limit ? digit[pos] : 9; int ans 0; for (int d 0; d up; d) { int nstate nxt(state, d); int nrem (rem * 10 d) % 13; ans dfs(pos - 1, nrem, nstate, limit (d up)); } if (!limit) dp[pos][rem][state] ans; return ans; } // 统计0到n之间满足条件的数的个数 int solve(int n) { if (n 0) return 0; int len 0; while (n) { digit[len] n % 10; n / 10; } // 注意digit数组是从低位到高位存储的所以pos从len-1开始 return dfs(len - 1, 0, 0, true); } int main() { memset(dp, -1, sizeof(dp)); int L, R; while (cin L R) { cout solve(R) - solve(L - 1) endl; } return 0; }这段代码是 B-number 的标准解法。我来逐行解释关键部分。首先digit 数组存储上界N的各位数字。注意在 solve 函数中我是用 n % 10 取最低位然后 n / 10所以 digit[0] 是最低位digit[len-1] 是最高位。在 dfs 中pos 从 len-1 开始每次减1直到 -1。这样 pos 就对应从高位到低位的处理顺序。dp 数组初始化为 -1。在 dfs 中如果 !limit 且 dp[pos][rem][state] 已经有值直接返回。否则计算。nxt 函数实现了状态转移。注意 state2 时直接返回2因为已经出现过13不会再消失。在 dfs 的循环中up 是当前位能填的最大数字。如果 limit 为真up digit[pos]否则 up 9。然后枚举 d 从0到up。计算 nstate 和 nrem递归调用 dfs(pos-1, nrem, nstate, limit (d up))。注意新的 limit 是 limit (d up)而不是 limit (d digit[pos])因为 up 可能等于 digit[pos]当 limit 为真时所以 d up 等价于 d digit[pos]。但当 limit 为假时up9d up 可能为真d9但此时 limit 已经是假所以新的 limit 仍然是假。所以用 limit (d up) 是正确的。最后如果 !limit将结果存入 dp 数组。solve 函数将 n 拆位然后调用 dfs。注意如果 n 0直接返回0。在主函数中统计区间 [L, R] 的结果就是 solve(R) - solve(L-1)。3.2 记忆化数组的初始化与多组数据复用前面提到dp 数组只需要在程序开始时初始化一次。但这里有一个潜在问题如果多组数据的上界位数不同dp 数组的 pos 维度可能需要调整。比如第一组数据上界是 9993位pos 从2开始第二组数据上界是 99994位pos 从3开始。dp[2][...] 在第一组数据中被计算过在第二组数据中 pos2 时它表示的是“从第2位开始从高位数的后缀”但两组数据的 pos 含义可能不同。实际上pos 表示的是“剩余还需要处理的位数”它与具体的上界无关。比如 pos2 表示还需要处理3位数字pos从2到0。这个含义在两组数据中是一致的。所以 dp 数组可以复用。但要注意如果第一组数据中 pos2 的状态被计算过它记录的是“在无限制情况下从 pos2 开始能构造出多少个满足条件的后缀”。这个值与上界无关所以第二组数据中 pos2 时可以直接使用。因此dp 数组的复用是安全的。不过有一种情况需要小心如果题目中数字的进制不是10或者取模的模数不同那 dp 数组就不能复用。但 B-number 是固定的10进制和模13所以没问题。3.3 边界条件与特殊输入的处理边界条件主要有两个n 0 时返回0n 0 时digit 数组为空len0dfs(-1, 0, 0, true) 会直接返回 (state2 rem0) ? 1 : 0。state0所以返回0。这符合预期因为0不满足条件。如果输入 L1, R13那么 solve(13) 会统计 0 到 13 之间满足条件的数。13 本身包含 13 且能被13整除所以应该被计数。solve(0) 返回0。所以结果是1。我们可以手动验证0到13中只有13满足条件。正确。如果输入 L1, R130那么除了13还有哪些130 包含 13 且 130 % 13 0所以130也满足。还有 113113 包含 13 吗113 的十进制是 113包含子串 13 吗113 的子串有 1, 1, 3, 11, 13, 113其中 13 出现在第2到第3位所以113包含 13。113 % 13 113 - 104 9不能被13整除。所以113不满足。我们需要系统统计但这里不展开。4. 常见错误与调试技巧4.1 状态转移写错导致漏解或重复计数最常见的错误是 nxt 函数写错。比如在 state1 时填 d3 应该转移到 state2但有人可能写成 state1 或 state0。这会导致漏解。另一种错误是在 state0 时填 d1 应该转移到 state1但有人可能忘记处理导致 state 一直为0从而漏掉所有包含 13 的数。调试方法可以写一个暴力程序枚举小区间内的所有数判断是否满足条件然后与数位DP的结果对比。比如枚举 0 到 1000比较两者结果。如果一致说明状态转移基本正确。4.2 取模递推的初始值与更新错误取模递推的初始值是 rem0。在 dfs 中每次填 d新的 rem (rem * 10 d) % 13。这个公式必须写对。有人可能写成 (rem d) % 13 或 (rem * 10 d) % 13 但忘记取模。这些都会导致错误。另外注意 rem 的范围是 0 到 12所以 dp 数组的第二维大小是13。如果写成 dp[15][10][3]就会越界。4.3 limit 标记传递错误导致答案偏大limit 的传递是 limit (d up)。有人可能写成 limit (d digit[pos])这在 limit 为真时是等价的但当 limit 为假时up9d digit[pos] 可能为真如果 digit[pos]9 且 d9但此时 limit 已经是假所以新的 limit 应该是假。用 limit (d up) 可以避免这个问题。因为当 limit 为假时limit ... 一定是假。另一个错误是忘记在 !limit 时才记忆化。如果 limit 为真时也记忆化会导致不同上界的结果被混用答案偏大或偏小。4.4 多组数据下 dp 数组未重置或错误重置前面说了 dp 数组可以复用但前提是每组数据的模数和进制相同。如果题目中有多组数据且每组数据的模数不同比如有的模13有的模7那就不能复用。但 B-number 固定模13所以可以复用。如果错误地在每组数据前都 memset(dp, -1, sizeof(dp))会导致重复计算效率降低但不会出错。如果忘记初始化dp 数组是全局变量默认是0那就会导致错误因为0会被误认为是有效结果。所以必须在程序开始时 memset 一次。4.5 前导零影响状态判断的隐蔽问题对于 B-number前导零不影响。但如果题目要求统计的数字不能有前导零或者前导零会影响状态比如统计某种特定模式的数字那就需要额外处理。处理方法通常是在 dfs 中增加一个 bool 类型的 lead 标记表示当前是否还在处理前导零。如果 lead 为真且当前位填0则新状态仍然是 leadtrue且 state 和 rem 不更新或者保持初始值。如果 lead 为真且当前位填非0则 lead 变为 false并正常更新 state 和 rem。对于 B-number我们可以不加 lead 标记因为前导零不影响结果。但如果你发现答案偏大可以检查一下是否因为前导零导致某些数字被重复计数。比如数字 013 和 13 被当成两个不同的数实际上在数位DP中我们是从高位到低位构造数字前导零会被自然地处理为数字的一部分。比如上界是 100那么数字 013 实际上就是 13它在构造时最高位填0然后填1然后填3。这个路径构造出的数字是 13不是 013。所以不会重复计数。5. 数位DP的通用模板与扩展思路5.1 从 B-number 抽象出的数位DP通用框架B-number 的解法可以抽象成一个通用的数位DP框架。这个框架包含以下几个部分将上界N拆分为数字数组 digit[]。定义状态通常包括 pos当前处理到第几位、以及若干与题目相关的状态变量如 rem、state 等。定义状态转移根据当前位的数字更新状态变量。定义终止条件pos 处理完时判断是否满足题目条件。记忆化用 dp 数组记录无限制情况下的结果。上界限制用 limit 标记控制当前位的枚举范围。这个框架可以解决大部分数位DP问题。不同的题目只是状态变量和转移规则不同。5.2 状态压缩技巧如何合并等价状态在 B-number 中我们把“是否出现过13”和“上一位是否为1”合并成了一个三值状态。这种合并等价状态的技巧在数位DP中很常见。比如有些题目要求统计数字中某个数字出现的次数那状态可能是一个计数变量。如果计数变量很大可以考虑是否只需要知道“是否达到某个阈值”从而压缩状态。另一个技巧是如果某些状态在后续转移中行为相同可以合并。比如在 B-number 中state2 之后无论填什么都是 state2所以 state2 是一个吸收态。我们可以把它单独处理。5.3 记忆化搜索与递推写法的取舍数位DP有两种常见写法记忆化搜索DFS记忆化和递推从低位到高位或从高位到低位。记忆化搜索的优点是思路直观容易处理上界限制缺点是递归深度可能较大但通常位数不超过20所以没问题。递推的优点是速度快但处理上界限制比较麻烦通常需要预处理无限制情况下的结果然后再逐位统计。对于 B-number我推荐记忆化搜索因为状态转移简单代码可读性好。递推写法也可以但需要额外处理上界限制容易出错。5.4 扩展到其他类似题目不要62、windy数等B-number 的解法可以扩展到其他数位DP题目。比如“不要62”是统计区间内不包含 62 且不包含 4 的数的个数。状态设计类似state 表示是否已经包含 62以及上一位是否为6。取模条件没有所以少一个维度。“windy数”是统计相邻两位数字之差至少为2的数的个数。状态需要记录上一位数字因为转移时依赖上一位。这些题目的共同点是状态设计要能够完整描述对后续决策有影响的信息。只要抓住这个核心数位DP就不难。6. 实战调试记录与性能优化建议6.1 用暴力对拍验证正确性我在第一次写 B-number 的时候提交后 WA 了。于是写了一个暴力程序bool check(int x) { string s to_string(x); if (s.find(13) string::npos) return false; return x % 13 0; } int brute(int L, int R) { int cnt 0; for (int i L; i R; i) { if (check(i)) cnt; } return cnt; }然后枚举小区间比如 L1, R10000比较暴力结果和数位DP结果。发现数位DP结果偏小。检查后发现是 nxt 函数在 state1 时填 d3 写成了返回1应该是返回2。改正后对拍通过。对拍是调试数位DP最有效的方法。因为数位DP的状态转移容易写错而暴力程序简单直接可以作为基准。6.2 记忆化数组维度与初始化顺序的坑dp 数组的维度顺序是 dp[pos][rem][state]。在 dfs 中访问时必须保持一致。有人可能写成 dp[rem][pos][state]导致访问错位。另外初始化时 memset(dp, -1, sizeof(dp)) 必须放在所有测试数据之前。如果放在循环内会重复初始化效率降低。还有一个坑如果 dp 数组是全局变量且程序中有多组测试数据那么第一组数据计算出的 dp 值会被第二组数据复用。这通常是正确的但前提是状态定义与上界无关。如果状态定义中包含了与上界相关的信息比如 limit那就不能复用。所以标准做法是不把 limit 纳入状态。6.3 时间复杂度分析与优化空间B-number 的时间复杂度是 O(位数 × 13 × 3 × 10)。位数最多10对于10^9所以总计算量大约是 10 × 13 × 3 × 10 3900 次操作。非常小。即使多组数据每组数据也只是重新计算一遍总时间可以忽略。如果位数更大比如到10^1819位计算量也只是 19 × 13 × 3 × 10 7410 次。仍然很小。所以数位DP的效率非常高。优化空间不大但可以注意如果多组数据的上界相同可以缓存结果。但通常没必要。6.4 多组输入下的清空与复用策略前面说了 dp 数组可以复用。但有一个细节如果多组数据的上界位数不同dp 数组的 pos 维度可能需要调整。比如第一组数据上界是 9993位pos 从2开始第二组数据上界是 99994位pos 从3开始。dp[2][...] 在第一组数据中被计算过在第二组数据中 pos2 时它表示的是“从第2位开始从高位数的后缀”但两组数据的 pos 含义可能不同。实际上pos 表示的是“剩余还需要处理的位数”它与具体的上界无关。比如 pos2 表示还需要处理3位数字pos从2到0。这个含义在两组数据中是一致的。所以 dp 数组可以复用。但要注意如果第一组数据中 pos2 的状态被计算过它记录的是“在无限制情况下从 pos2 开始能构造出多少个满足条件的后缀”。这个值与上界无关所以第二组数据中 pos2 时可以直接使用。因此dp 数组的复用是安全的。不过有一种情况需要小心如果题目中数字的进制不是10或者取模的模数不同那 dp 数组就不能复用。但 B-number 是固定的10进制和模13所以没问题。6.5 常见WA点速查表错误类型表现修正方法nxt函数写错答案偏小或偏大对拍验证rem递推公式错答案偏小检查 (rem*10d)%13limit传递错答案偏大用 limit (d up)记忆化条件错答案偏大只在 !limit 时记忆化dp数组未初始化答案随机程序开始 memset前导零处理错答案偏大检查是否重复计数边界n0未处理数组越界solve中判断 n0这个表是我在实际调试中总结的基本上覆盖了数位DP常见的错误。7. 个人实操心得与进阶建议数位DP这个知识点我踩过的坑主要集中在状态设计和边界处理上。最开始学的时候我总是想不清楚到底要记录哪些状态经常多记或者少记。后来总结出一个方法先写暴力然后观察暴力程序在判断一个数是否满足条件时需要哪些信息。这些信息就是状态。比如 B-number 的暴力判断需要知道“是否包含13”和“对13的余数”那么在数位DP中就需要记录这两个信息。但“是否包含13”在逐位构造时还需要知道“上一位是不是1”所以状态要细化。另一个心得是记忆化搜索的代码结构非常固定可以背下来。遇到新的数位DP题目只需要修改状态定义和转移规则框架不变。这样能大大加快解题速度。对于想进阶的朋友建议做完 B-number 后再去做“不要62”、“windy数”、“恨7不成妻”等题目。这些题目的状态设计各有特点能帮助你更深入地理解数位DP。最后分享一个小技巧在写 dfs 的时候可以在函数开头加一句调试输出打印 pos、rem、state、limit 和当前返回值。这样在结果不对时可以追踪递归过程快速定位问题。当然提交时要注释掉。这个题后续还可以扩展到统计满足多个条件的数比如同时包含 13 和 31或者对多个模数取模。状态设计会变得更复杂但核心思想不变。