1. 从一道题看数位DP的真正门槛B-number这道题在数位DP的练习体系里属于那种看起来平平无奇上手才发现处处是坑的典型。题目本身的要求并不复杂找出区间内满足特定整除性质且十进制表示中包含特定子串的数字个数。但真正做过的人都知道这道题的核心难点根本不在数位DP这四个字上而在于你怎么处理包含某子串这个状态以及怎么把整除判定和数位枚举揉在一起还不让状态爆炸。我见过太多人第一次写这道题的时候直接套了一个最朴素的记忆化搜索模板结果要么是状态设计漏了维度导致答案偏大要么是记忆化数组开得不对导致重复计算。更常见的情况是样例过了提交上去WA一片然后对着代码盯了半天也看不出哪里有问题。这不是因为数位DP本身有多难而是因为B-number这道题恰好踩在了几个容易出错的交叉点上。这篇文章面向的是已经了解数位DP基本框架、但在处理带子串约束的整除计数时容易翻车的读者。我会从状态设计的底层逻辑讲起把记忆化搜索的每一个参数为什么存在、为什么不能省、为什么这样设计能保证正确性全部拆开揉碎讲清楚。同时也会给出完整的代码实现和几个关键测试用例方便你直接对照验证。2. 为什么朴素枚举一定会超时问题规模与暴力边界2.1 数据范围决定了你必须用数位DPB-number的典型数据范围是区间端点最大到10的9次方甚至10的10次方级别。如果你对区间内每个数逐一检查单次查询的复杂度就是O(n × 位数)当n达到10的9次方时就算每次检查只需要几纳秒总时间也会轻松突破几秒甚至几十秒。更不用说题目通常会给出多组测试数据暴力做法完全没有生存空间。数位DP的核心思路是把逐个数枚举变成逐位枚举。假设上界是10位数那么每一位有0到9共10种选择总状态空间大约是10的10次方——看起来也没好到哪里去。但关键在于大量数字在前缀相同的情况下后续的计数结果是可以复用的。这就是记忆化搜索的切入点当你确定了当前处理到第几位、前面的前缀对后续产生了什么影响后面所有可能的填法数量就是固定的不需要重复计算。2.2 暴力做法能帮你验证什么虽然暴力枚举不能作为最终解法但它在调试阶段非常有用。我个人的习惯是先用暴力写一个check函数对小范围比如1到10000内的所有数字逐一判断得到一个暴力答案表。然后用数位DP跑同样的范围对比两者是否一致。如果在小范围上就对不上那说明状态设计或者转移逻辑有问题不需要等到大范围才发现。具体来说暴力版本大概长这样def brute_force(n): count 0 for i in range(1, n 1): s str(i) if 13 in s and i % 13 0: count 1 return count这段代码虽然简单但它给出了一个绝对正确的参照系。数位DP的调试过程中最怕的就是看起来对但实际错的情况有一个暴力版本做对照能帮你快速定位问题。2.3 数位DP的状态空间到底有多大以B-number为例假设上界是10的10次方也就是最多10位数。每一位的处理需要记录以下信息当前处理到第几位10种可能、当前前缀对13取模的余数13种可能、当前前缀是否已经包含了13这个子串2种可能、当前前缀是否还在紧贴上界2种可能。乘起来大约是10 × 13 × 2 × 2 520种状态。每种状态最多被访问一次记忆化之后每次转移枚举10个数字总计算量大约是520 × 10 5200次操作。这个量级对于任何编程语言来说都是瞬间完成的。这就是数位DP的威力所在它把O(n)的枚举压缩成了O(状态数 × 转移数)的常数级计算。而状态数的多少直接取决于你设计了多少个维度来刻画前缀对后续的影响。3. 状态设计的核心三个维度缺一不可3.1 维度一位置pos与上界限制limit位置pos是最直观的维度表示当前正在填第几位从高位到低位。但仅仅有pos是不够的因为你还得知道当前前缀是否已经小于上界的前缀。如果前缀已经小于上界那么当前位可以自由选择0到9如果前缀仍然等于上界的前缀那么当前位只能选到上界对应位的数字。这个是否紧贴上界的标志就是limit。很多初学者会忽略limit维度觉得我只要在枚举的时候判断一下就行了。但问题在于如果你不把limit作为状态的一部分记忆化就会出错。因为limit为true和limit为false时后续的可选数字范围是不同的对应的计数结果也不同。如果你把这两种情况混在一起记忆化就会导致答案错误。正确的做法是当limit为true时不进行记忆化因为这种情况只会在一条路径上出现不会被重复访问当limit为false时才把结果存入记忆化数组。这样既保证了正确性又不影响效率。3.2 维度二模数余数remB-number要求数字能被13整除所以你需要记录当前前缀对13取模的余数。这个维度看起来简单但有一个容易踩的坑前导零的处理。举个例子上界是100你要统计1到100中满足条件的数字。当你处理第一位时可以选择填0表示这个数实际上只有后面几位也可以选择填1。如果你把前导零也当作正常数字参与模运算那么0013和13会被当成不同的前缀来处理但实际上它们代表的是同一个数字。这就会导致重复计数或者状态混乱。解决方法是引入一个started标志表示当前是否已经开始填非零数字。如果还没有开始started为false那么当前位填0时余数保持为0且不更新任何状态。只有当started变为true之后才开始正常计算余数和子串匹配。3.3 维度三子串匹配状态matched这是B-number区别于普通数位DP的关键维度。你需要记录当前前缀是否已经包含了13这个子串。但这里有一个细节仅仅记录是否包含是不够的因为你在拼接数字的时候需要知道前缀的最后一位是什么才能判断新加入的数字是否会形成13。比如说当前前缀是...1下一位填3那么就形成了13如果当前前缀是...2下一位填3就不会形成13。所以你需要记录的状态其实有三种还没有出现13且最后一位不是1、还没有出现13且最后一位是1、已经出现了13。这三种状态可以用一个整数来表示0表示未出现且末尾非11表示未出现且末尾为12表示已出现。状态转移也很直观当前状态为0填入数字d如果d等于1转移到状态1否则保持在状态0。当前状态为1填入数字d如果d等于3转移到状态2如果d等于1保持在状态1否则回到状态0。当前状态为2填入任何数字保持在状态2。这个三状态的设计是B-number状态压缩的精髓。如果你只用一个布尔值来表示是否包含13就无法处理末尾是1这种中间状态导致漏算或者多算。3.4 三个维度如何协同工作把这三个维度组合起来记忆化数组就是dp[pos][rem][state]其中pos是位置rem是余数state是子串匹配状态。数组大小大约是10 × 13 × 3 390非常小。在递归函数中参数除了这三个维度之外还需要limit和started。但limit和started不需要作为记忆化数组的维度因为它们只影响当前路径的选择范围不影响后续有多少种合法填法这个计数结果。具体来说limit为true时当前位的枚举上界是上界数字limit为false时枚举上界是9。started为false时当前位可以填0且不更新rem和statestarted为true时正常更新。当递归到达最后一位之后pos等于总位数判断条件就是started为true排除数字0本身、rem等于0、state等于2。三个条件同时满足返回1否则返回0。4. 记忆化搜索的实现细节与常见翻车点4.1 递归函数的参数顺序与含义先给出一个标准的递归函数签名def dfs(pos, rem, state, limit, started): if pos len(digits): return 1 if started and rem 0 and state 2 else 0 if not limit and dp[pos][rem][state] ! -1: return dp[pos][rem][state] upper digits[pos] if limit else 9 res 0 for d in range(0, upper 1): if not started and d 0: res dfs(pos 1, 0, 0, limit and d upper, False) else: new_rem (rem * 10 d) % 13 if state 2: new_state 2 elif state 1 and d 3: new_state 2 elif d 1: new_state 1 else: new_state 0 res dfs(pos 1, new_rem, new_state, limit and d upper, True) if not limit: dp[pos][rem][state] res return res这段代码看起来不长但每一行都有讲究。我逐段解释一下。4.2 为什么limit为true时不记忆化这是记忆化搜索中最容易被忽略的细节。当limit为true时当前位的枚举上界是digits[pos]而不是9。这意味着从这个状态出发的后续计数结果只对紧贴上界的这一条路径有效。如果你把它存入dp数组下次遇到同样的pos、rem、state但limit为false的情况就会错误地复用这个结果导致答案偏小。所以正确的做法是只有当limit为false时才把结果写入dp数组。limit为true时直接返回计算结果不存储。这样虽然会多算几次但由于limit为true的路径只有一条就是完全紧贴上界的那条额外开销可以忽略不计。4.3 started标志与前导零的纠缠前导零是数位DP里另一个高频翻车点。很多人在处理数字是否包含某个子串时忘记排除前导零的干扰。比如说上界是100数字13会被表示为013。如果你不处理前导零那么在处理第一位0的时候state会保持为0因为0不等于1然后第二位填1state变为1第三位填3state变为2。看起来好像没问题但问题在于数字1会被表示为001数字0会被表示为000。如果你不排除前导零那么000也会被当作一个合法的数字参与计数而实际上0不在考虑范围内题目通常要求正整数。更隐蔽的问题是前导零会影响rem的计算。如果你把前导零也参与模运算那么013的rem计算过程是0 → 0×1000 → 0×1011 → 1×10313 → 13%130。而13的rem计算过程是1 → 1×10313 → 13%130。两者结果相同看起来没问题。但如果数字是103前导零版本是0103计算过程是0 → 0 → 1 → 10 → 103 → 103%1312而非前导零版本是103计算过程是1 → 10 → 103 → 103%1312。结果也相同。实际上由于0×10d d前导零在模运算中不会改变最终结果。但为了逻辑清晰和避免其他潜在问题还是建议用started标志显式处理。4.4 状态转移中的顺序陷阱在更新state的时候有一个容易写错的顺序问题。看这段代码if state 2: new_state 2 elif state 1 and d 3: new_state 2 elif d 1: new_state 1 else: new_state 0这个顺序不能乱。如果state已经是2已经出现过13那么无论d是什么new_state都保持为2。这个判断必须放在最前面。如果state是1末尾是1且d等于3那么形成13new_state变为2。这个判断放在第二位。如果d等于1那么new_state变为1无论之前state是0还是1。最后其他情况new_state变为0。如果你把d 1的判断放在前面那么当state为1且d为1时会先被d 1捕获new_state变为1这其实是对的。但当state为1且d为3时如果先判断d 1不满足然后判断d 3但你没有单独处理d 3的情况就会走到else分支new_state变为0这就错了。所以顺序很重要先处理已完成的state再处理形成13的情况再处理末尾为1的情况最后是默认情况。4.5 记忆化数组的初始化与清空dp数组通常初始化为-1表示尚未计算。但要注意如果你的程序需要处理多组测试数据且每组数据的上界不同那么dp数组是否需要清空取决于你的状态设计是否与上界有关。在B-number的标准做法中dp[pos][rem][state]的值只依赖于pos、rem、state这三个维度与上界的具体数字无关。因为limit为false时当前位可以自由选择0到9后续的计数结果只取决于还需要填几位、当前余数是多少、当前子串匹配状态是什么。所以dp数组可以在多组数据之间复用不需要清空。但如果你在状态中加入了其他与上界相关的信息比如某些题目要求统计的数字必须小于某个特定值那就需要根据情况清空。对于B-number来说不需要清空这是一个可以优化的点。5. 完整代码实现与逐行注释5.1 Python版本import sys sys.setrecursionlimit(10000) def solve(n): if n 0: return 0 digits [] while n 0: digits.append(n % 10) n // 10 digits.reverse() length len(digits) dp [[[-1] * 3 for _ in range(13)] for _ in range(length)] def dfs(pos, rem, state, limit, started): if pos length: return 1 if started and rem 0 and state 2 else 0 if not limit and dp[pos][rem][state] ! -1: return dp[pos][rem][state] upper digits[pos] if limit else 9 res 0 for d in range(0, upper 1): if not started and d 0: res dfs(pos 1, 0, 0, limit and d upper, False) else: new_rem (rem * 10 d) % 13 if state 2: new_state 2 elif state 1 and d 3: new_state 2 elif d 1: new_state 1 else: new_state 0 res dfs(pos 1, new_rem, new_state, limit and d upper, True) if not limit: dp[pos][rem][state] res return res return dfs(0, 0, 0, True, False) def main(): for line in sys.stdin: line line.strip() if not line: continue n int(line) print(solve(n)) if __name__ __main__: main()5.2 C版本#include bits/stdc.h using namespace std; int digits[15]; int dp[15][13][3]; int len; int dfs(int pos, int rem, int state, bool limit, bool started) { if (pos len) { return (started rem 0 state 2) ? 1 : 0; } if (!limit dp[pos][rem][state] ! -1) { return dp[pos][rem][state]; } int upper limit ? digits[pos] : 9; int res 0; for (int d 0; d upper; d) { if (!started d 0) { res dfs(pos 1, 0, 0, limit d upper, false); } else { int new_rem (rem * 10 d) % 13; int new_state; if (state 2) { new_state 2; } else if (state 1 d 3) { new_state 2; } else if (d 1) { new_state 1; } else { new_state 0; } res dfs(pos 1, new_rem, new_state, limit d upper, true); } } if (!limit) { dp[pos][rem][state] res; } return res; } int solve(int n) { if (n 0) return 0; len 0; while (n 0) { digits[len] n % 10; n / 10; } reverse(digits, digits len); memset(dp, -1, sizeof(dp)); return dfs(0, 0, 0, true, false); } int main() { int n; while (cin n) { cout solve(n) endl; } return 0; }5.3 两个版本的差异与选择建议Python版本的优势是代码短、逻辑清晰适合快速验证思路。缺点是递归深度受限于Python的解释器限制虽然可以用sys.setrecursionlimit调高但在极端情况下比如上界有18位可能会有性能问题。不过对于B-number的典型数据范围10位左右Python完全够用。C版本的优势是速度快、内存可控适合在竞赛环境中使用。memset初始化dp数组的效率很高递归调用也没有额外的解释器开销。如果你是在准备算法竞赛建议以C版本为主。两个版本的核心逻辑完全一致你可以用Python版本快速验证思路然后用C版本提交。6. 调试与验证怎么确认你的代码是对的6.1 小范围暴力对拍最可靠的验证方法就是暴力对拍。写一个暴力函数对1到10000内的每个数字逐一检查然后和数位DP的结果对比。如果两者完全一致说明你的状态设计和转移逻辑在小范围内是正确的。然后可以逐步扩大范围比如到100000、1000000观察是否仍然一致。对拍脚本大概长这样def brute(n): cnt 0 for i in range(1, n 1): s str(i) if 13 in s and i % 13 0: cnt 1 return cnt for n in range(1, 10001): if solve(n) ! brute(n): print(fMismatch at n{n}: dp{solve(n)}, brute{brute(n)}) break else: print(All matched!)如果对拍过程中发现不一致不要急着改代码先定位是哪个n出现了问题然后手动分析那个n的每一位看看数位DP在哪个状态上算错了。这种定位方式比盲目调试高效得多。6.2 边界情况的手动验证除了对拍之外还需要手动验证一些边界情况n1答案应该是0因为1不包含13且不能被13整除。n13答案应该是1因为13包含13且能被13整除。n12答案应该是0因为12不包含13。n26答案应该是0因为26能被13整除但不包含13。n130答案应该是1只有130本身不对130包含13且130%130所以是1。但还要检查113、213等是否在范围内。实际上113%139不满足。所以n130时答案应该是1。这些边界情况可以帮助你快速发现一些低级错误比如忘记判断started、忘记判断rem、state转移顺序错误等。6.3 多组数据的处理B-number通常会有多组测试数据每组给出一个n要求输出1到n中满足条件的数字个数。如果你的代码在处理多组数据时出现答案累加或者状态污染那很可能是dp数组没有正确初始化或者递归函数中使用了全局变量导致状态混乱。在C版本中每次调用solve函数时都会memset(dp, -1, sizeof(dp))确保每组数据都是独立计算的。在Python版本中每次调用solve函数时都会重新创建dp数组也不会有状态污染。如果你发现多组数据的答案不对先检查dp数组是否在每组数据前被正确重置。7. 从B-number延伸出去的数位DP通用套路7.1 状态设计的通用公式B-number的状态设计可以总结为一个通用公式dp[位置][约束1][约束2]...[约束k]。其中每个约束都是前缀对后续产生影响的某种信息。常见的约束包括模数余数用于处理整除性问题。子串匹配状态用于处理包含/不包含某个子串的问题。数位和用于处理数位和相关的计数问题。前一位数字用于处理相邻位之间关系的问题比如不能有连续相同的数字。计数器用于处理某个数字出现次数的问题。状态设计的核心原则是只记录必要且充分的信息。信息太少会导致无法正确转移信息太多会导致状态空间爆炸。B-number的三个维度pos、rem、state就是必要且充分的典型例子。7.2 记忆化搜索的通用模板把B-number的框架抽象出来可以得到一个通用的记忆化搜索模板def dfs(pos, state1, state2, ..., limit, started): if pos len(digits): return 1 if 满足最终条件 else 0 if not limit and dp[pos][state1][state2][...] ! -1: return dp[pos][state1][state2][...] upper digits[pos] if limit else 9 res 0 for d in range(0, upper 1): if not started and d 0: res dfs(pos 1, 初始状态..., limit and d upper, False) else: new_state1, new_state2, ... 转移(state1, state2, ..., d) res dfs(pos 1, new_state1, new_state2, ..., limit and d upper, True) if not limit: dp[pos][state1][state2][...] res return res这个模板几乎可以套用到所有数位DP问题上。你只需要根据具体题目确定状态有哪些、转移怎么写、最终条件是什么。7.3 常见变体与应对策略B-number的变体包括统计包含13且能被13整除的数字之和、统计包含13且数位和为13的倍数的数字个数、统计包含13且是回文数的数字个数等。这些变体的核心框架不变只需要调整状态维度和最终判断条件。比如说如果要求统计数字之和那么需要在状态中增加一个当前数字之和的维度或者在递归返回值中同时返回个数和总和。如果要求统计数位和为13的倍数那么需要把rem的模数从13改为13数位和的模数状态转移变为new_sum sum d。这些变体的共同点是它们都在B-number的基础上增加了一个或多个约束维度。只要你理解了B-number的状态设计逻辑这些变体都可以举一反三。8. 我在实际调试中踩过的几个坑第一个坑是忘记处理前导零。我第一次写的时候没有加started标志结果数字0被当成了合法数字参与计数导致答案偏大。更隐蔽的是前导零还会影响state的判断比如数字1被表示为001在处理第一位0的时候state保持为0第二位0的时候state还是0第三位1的时候state变为1。这看起来没问题但如果数字是013前导零会导致state在第一位0的时候保持为0第二位1的时候变为1第三位3的时候变为2最终被正确计数。所以前导零对state的影响其实不大但对rem和最终判断的影响是致命的。第二个坑是limit为true时进行了记忆化。这个问题非常隐蔽因为在小范围测试时可能不会暴露。比如上界是100你在处理第一位时limit为true枚举了0和1。如果你把limit为true的结果存入了dp数组那么下次遇到同样的pos、rem、state但limit为false的情况就会错误地复用这个结果。在小范围测试时由于上界较小可能不会触发这个bug但一旦上界变大答案就会明显偏小。第三个坑是state转移顺序写错。我一开始把d 1的判断放在了最前面结果当state为1且d为3时先判断d 1不满足然后判断d 3但没有单独处理走到了else分支new_state变为0导致13被漏算。正确的顺序应该是先判断state 2再判断state 1 d 3再判断d 1最后是else。第四个坑是dp数组没有正确初始化。在C中如果忘记memsetdp数组的初始值是随机的可能导致某些状态被错误地当作已计算而直接返回。在Python中如果dp数组的维度不对比如dp[pos][rem][state]写成了dp[pos][state][rem]也会导致答案错误。这些坑的共同特点是它们都不会导致编译错误也不会在小范围测试中轻易暴露但一旦触发就会导致答案错误。所以我的建议是写完代码后先用暴力对拍验证小范围再手动构造几个边界用例最后再提交。