企业官网建设流程全解析

1. 从一道题看数位DP的真正门槛

B-number这道题在数位DP的练习体系里属于那种"看起来平平无奇，上手才发现处处是坑"的典型。题目本身的要求并不复杂：找出区间内满足特定整除性质且十进制表示中包含特定子串的数字个数。但真正做过的人都知道，这道题的核心难点根本不在"数位DP"这四个字上，而在于你怎么处理"包含某子串"这个状态，以及怎么把整除判定和数位枚举揉在一起还不让状态爆炸。

我见过太多人第一次写这道题的时候，直接套了一个最朴素的记忆化搜索模板，结果要么是状态设计漏了维度导致答案偏大，要么是记忆化数组开得不对导致重复计算。更常见的情况是：样例过了，提交上去WA一片，然后对着代码盯了半天也看不出哪里有问题。这不是因为数位DP本身有多难，而是因为B-number这道题恰好踩在了几个容易出错的交叉点上。

这篇文章面向的是已经了解数位DP基本框架、但在处理"带子串约束的整除计数"时容易翻车的读者。我会从状态设计的底层逻辑讲起，把记忆化搜索的每一个参数为什么存在、为什么不能省、为什么这样设计能保证正确性，全部拆开揉碎讲清楚。同时也会给出完整的代码实现和几个关键测试用例，方便你直接对照验证。

2. 为什么朴素枚举一定会超时：问题规模与暴力边界

2.1 数据范围决定了你必须用数位DP

B-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 维度二：模数余数rem

B-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表示未出现且末尾非1，1表示未出现且末尾为1，2表示已出现。状态转移也很直观：

• 当前状态为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和state；started为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），然后第二位填1，state变为1，第三位填3，state变为2。看起来好像没问题？但问题在于，数字1会被表示为"001"，数字0会被表示为"000"。如果你不排除前导零，那么"000"也会被当作一个合法的数字参与计数，而实际上0不在考虑范围内（题目通常要求正整数）。

更隐蔽的问题是：前导零会影响rem的计算。如果你把前导零也参与模运算，那么"013"的rem计算过程是：0 → 0×10+0=0 → 0×10+1=1 → 1×10+3=13 → 13%13=0。而"13"的rem计算过程是：1 → 1×10+3=13 → 13%13=0。两者结果相同，看起来没问题。但如果数字是"103"，前导零版本是"0103"，计算过程是：0 → 0 → 1 → 10 → 103 → 103%13=12；而非前导零版本是"103"，计算过程是：1 → 10 → 103 → 103%13=12。结果也相同。实际上，由于0×10+d = 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，那么形成"13"，new_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(f"Mismatch at n={n}: dp={solve(n)}, brute={brute(n)}") break else: print("All matched!")

如果对拍过程中发现不一致，不要急着改代码，先定位是哪个n出现了问题，然后手动分析那个n的每一位，看看数位DP在哪个状态上算错了。这种定位方式比盲目调试高效得多。

6.2 边界情况的手动验证

除了对拍之外，还需要手动验证一些边界情况：

• n=1：答案应该是0，因为1不包含"13"且不能被13整除。
• n=13：答案应该是1，因为13包含"13"且能被13整除。
• n=12：答案应该是0，因为12不包含"13"。
• n=26：答案应该是0，因为26能被13整除但不包含"13"。
• n=130：答案应该是1（只有130本身？不对，130包含"13"且130%13=0，所以是1。但还要检查113、213等是否在范围内。实际上113%13=9，不满足。所以n=130时答案应该是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++中，如果忘记memset，dp数组的初始值是随机的，可能导致某些状态被错误地当作"已计算"而直接返回。在Python中，如果dp数组的维度不对，比如dp[pos][rem][state]写成了dp[pos][state][rem]，也会导致答案错误。

这些坑的共同特点是：它们都不会导致编译错误，也不会在小范围测试中轻易暴露，但一旦触发就会导致答案错误。所以我的建议是：写完代码后，先用暴力对拍验证小范围，再手动构造几个边界用例，最后再提交。