企业官网建设流程全解析

1. 从一道题看数位DP的核心思想

B-number这类题目，在算法竞赛圈子里算是数位DP的经典入门题之一。题目的核心要求通常是：统计某个区间内满足特定数字结构条件的数的个数，比如“包含子串13且能被13整除”这样的双重约束。第一次接触这类题的人往往会想用暴力枚举，但一看数据范围就傻眼了——区间上界可能到10的9次方甚至更大，逐个判断根本不现实。这时候数位DP就派上用场了。

所谓数位DP，本质上是按位处理的动态规划。它的核心思路是把一个十进制数拆成一位一位的数字，然后从高位到低位逐位决策，同时用状态记录当前已经满足或未满足的条件。这样做的好处是，大量具有相同前缀特征的数字可以共享同一套状态，从而把指数级的枚举压缩成多项式级别的状态转移。以B-number为例，我们需要同时跟踪两个维度的信息：当前数字对13取模的余数，以及当前数字中是否已经出现了“13”这个子串。这两个维度组合起来，再加上位置信息，就构成了DP的状态空间。

为什么用记忆化搜索来实现数位DP？这是有讲究的。递推式的数位DP写起来比较绕，尤其是处理上界限制的时候，需要额外判断当前位是否贴着上界走。而记忆化搜索的写法更符合人的直觉：我写一个dfs函数，参数包括当前处理到第几位、当前余数是多少、当前是否已经出现了13、以及一个布尔标记表示当前位是否受到上界约束。如果不受上界约束，说明后面的位可以自由选择0到9，这时候就可以把计算结果缓存起来，下次遇到相同状态直接返回。这种“贴着上界”和“自由发挥”的区分，是数位DP记忆化搜索写法的精髓所在。

对于B-number这道题，状态设计大致是这样的：dfs(pos, mod, has13, limit)，其中pos表示当前处理到第几位（从高位往低位数），mod表示当前前缀对13取模的余数，has13表示当前前缀中是否已经包含了子串“13”，limit表示当前位是否受到上界约束。转移的时候，枚举当前位可以填的数字d，如果limit为真，那么d的上限是当前位的数字；否则d可以从0枚举到9。新的余数是(mod * 10 + d) % 13，新的has13状态取决于之前是否已经有13，或者当前位和前一位是否构成了13。这里有一个容易忽略的细节：判断是否形成“13”需要知道前一位填的是什么，所以状态里其实还需要记录前一位的数字，或者换一种方式，在转移的时候直接判断。

很多初学者在这里会卡住：为什么状态里不需要记录前一位的数字？其实可以换一种状态定义方式，把“是否已经出现13”和“前一位是否为1”合并成一个三值状态：0表示还没出现13且前一位不是1，1表示还没出现13但前一位是1，2表示已经出现了13。这样状态数更少，转移也更清晰。这种状态压缩的技巧在数位DP中非常常见，值得仔细体会。

2. 状态设计与转移方程的细节拆解

2.1 为什么选择三值状态而不是布尔标记

前面提到，判断是否出现“13”需要知道前一位的信息。如果只用布尔值has13，那么在转移时就需要额外知道前一位是不是1。有两种处理方式：一种是在dfs参数里多加一个pre变量记录前一位数字，另一种是把has13扩展成三值状态。两种方式都能work，但三值状态在记忆化时更高效，因为状态空间更小，缓存命中率更高。

具体来说，三值状态的定义如下：state=0表示当前前缀中还没有出现“13”，且前一位不是1；state=1表示当前前缀中还没有出现“13”，但前一位是1；state=2表示当前前缀中已经出现了“13”。转移规则也很直观：如果当前state=2，那么无论填什么数字，新的state仍然是2；如果当前state=1且填入的数字是3，那么新的state变成2；如果当前state=1且填入的数字是1，那么新的state保持1；如果当前state=1且填入其他数字，那么新的state变成0；如果当前state=0且填入1，那么新的state变成1；如果当前state=0且填入其他数字，新的state保持0。

这种状态设计的精妙之处在于，它把“前一位是否为1”这个信息编码进了状态本身，避免了在dfs参数中额外传递pre变量。状态数从原来的2种（has13的真假）变成了3种，但省去了一个参数维度，总体状态空间反而更小。在实际写代码的时候，这种设计能让记忆化数组的维度更少，缓存效率更高。

2.2 余数状态的处理与边界条件

余数状态的处理相对直接：每次填入数字d之后，新的余数等于(mod * 10 + d) % 13。初始时mod=0，因为空前缀对应的数值是0，0对13取模还是0。最终判断一个数是否合法，需要满足两个条件：state=2（出现了13）且mod=0（能被13整除）。

这里有一个容易踩的坑：前导零的处理。在数位DP中，如果从高位开始枚举，可能会出现前导零的情况。比如统计1到1000中满足条件的数，数字5实际上只有一位，但在按位处理时会被当成0005来处理。前导零会影响state的转移吗？答案是会。如果当前还是前导零阶段，那么填入0不应该被当作“前一位是0”来处理，而应该保持在前导零状态。不过对于B-number这道题来说，前导零并不会影响最终结果，因为前导零不会形成“13”，也不会影响余数（0乘以10加0还是0）。但为了代码的严谨性，最好还是加一个标记来区分前导零和非前导零。

另一个边界条件是pos的终止位置。当pos超出数字的最高位时，说明所有位都已经处理完毕，此时返回(state==2 && mod==0) ? 1 : 0。这个返回值表示当前这个完整的数是否满足条件。在记忆化搜索中，只有limit为false的状态才会被缓存，因为limit为true的状态依赖于具体的上界数字，不具备通用性。

2.3 记忆化数组的维度与初始化

记忆化数组的维度取决于dfs的参数。对于B-number，dfs的参数是pos、mod、state、limit，其中limit不需要被缓存（因为limit为true的状态不会被重复访问），所以记忆化数组可以是三维的：dp[pos][mod][state]。pos的范围是数字的位数，最多十位左右；mod的范围是0到12；state的范围是0到2。总状态数大约是10 * 13 * 3 = 390，非常小，完全可以在常数时间内完成所有状态的填充。

初始化的时候，通常把dp数组全部置为-1，表示该状态还没有被计算过。在dfs函数中，如果limit为false且dp[pos][mod][state]不等于-1，直接返回缓存值。计算完当前状态后，如果limit为false，把结果存入dp数组。这种“先查缓存、再计算、后存缓存”的模式是记忆化搜索的标准写法。

需要注意的是，如果题目有多组测试数据，而每次查询的区间不同，那么记忆化数组在每组数据之间是否需要清空？答案是：如果dp数组的状态定义不依赖于具体的上界数字，那么不需要清空。因为dp[pos][mod][state]表示的是“从第pos位开始，当前余数为mod、状态为state，且后续位可以自由选择”的方案数，这个值与上界无关。所以多组数据可以共享同一个dp数组，只需要在每组数据开始时把limit相关的部分重新计算即可。这一点在写题解的时候经常被忽略，但实际比赛中能省下不少时间。

3. 完整代码实现与逐行解析

3.1 核心DFS函数的实现

下面给出B-number的完整C++实现代码，并逐段解析关键逻辑。

#include <bits/stdc++.h> using namespace std; int dp[15][13][3]; int digit[15]; // pos: 当前处理到第几位 // mod: 当前前缀对13取模的余数 // state: 0-无13且前一位非1, 1-无13且前一位是1, 2-已有13 // limit: 当前位是否受上界约束 int dfs(int pos, int mod, int state, bool limit) { if (pos == 0) { return (state == 2 && mod == 0) ? 1 : 0; } if (!limit && dp[pos][mod][state] != -1) { return dp[pos][mod][state]; } int up = limit ? digit[pos] : 9; int res = 0; for (int d = 0; d <= up; d++) { int newMod = (mod * 10 + d) % 13; int newState = state; if (state == 0 && d == 1) { newState = 1; } else if (state == 1) { if (d == 3) newState = 2; else if (d == 1) newState = 1; else newState = 0; } // state == 2 时 newState 保持 2 res += dfs(pos - 1, newMod, newState, limit && d == up); } if (!limit) { dp[pos][mod][state] = res; } return res; } int solve(int n) { if (n <= 0) return 0; int len = 0; while (n > 0) { digit[++len] = n % 10; n /= 10; } memset(dp, -1, sizeof(dp)); return dfs(len, 0, 0, true); } int main() { int n; while (cin >> n) { cout << solve(n) << endl; } return 0; }

这段代码的核心在于dfs函数的转移逻辑。注意digit数组是从下标1开始存储最低位的，所以dfs从len开始往下递归，pos=0时表示所有位都处理完了。这种从高位到低位的处理顺序是数位DP的标准写法。

3.2 状态转移的逐行拆解

在for循环中，枚举当前位可以填入的数字d。如果limit为true，那么d的上限是digit[pos]；否则d可以从0到9。这个上限控制是数位DP的关键，它保证了我们不会枚举出超过上界的数字。

newMod的计算很直接：(mod * 10 + d) % 13。这里mod是当前前缀对13的余数，乘以10再加上当前位数字，就得到了新的前缀数值对13的余数。这个递推关系利用了模运算的性质，避免了直接计算大整数。

newState的更新逻辑稍微复杂一些。如果当前state=0且d=1，说明前一位不是1但当前位是1，新的state变成1。如果当前state=1，说明前一位是1，此时如果d=3，就形成了“13”，新的state变成2；如果d=1，前一位仍然是1，新的state保持1；如果d是其他数字，前一位不再是1，新的state变成0。如果当前state=2，说明之前已经出现过13，无论填什么数字，新的state都保持2。

递归调用时，limit参数更新为limit && d == up。这意味着只有当之前一直贴着上界且当前位也贴着上界时，下一位才继续受上界约束。一旦某一位填入了小于上界的数字，后面的位就可以自由选择了。

3.3 多组数据的处理与性能分析

代码中使用了while(cin >> n)来处理多组输入。每次调用solve函数时，都会重新memset dp数组。虽然dp数组的状态定义与上界无关，理论上可以复用，但为了代码简洁，每次清空也不会有性能问题，因为状态数只有几百个。

性能方面，dfs的时间复杂度大约是O(位数 * 13 * 3 * 10)，对于10位以内的数字，计算量在几千次操作左右，完全可以在1毫秒内完成。即使有多组测试数据，只要组数不是特别大，总运行时间也能轻松控制在时限内。

这里有一个优化技巧：如果题目要求统计区间[a, b]内满足条件的数的个数，可以用solve(b) - solve(a-1)来计算。这种前缀和的思想在数位DP中非常常见，因为solve函数统计的是1到n中满足条件的数的个数，区间查询可以通过两次前缀查询相减得到。

4. 常见错误与调试技巧实录

4.1 状态转移中的典型错误

初学者在写B-number的时候，最容易犯的错误是状态转移写错。比如在state=1且d=3的时候，忘记把newState更新为2；或者在state=0且d=1的时候，忘记把newState更新为1。这些错误会导致最终统计结果偏少或偏多。

另一个常见错误是余数的初始值设置错误。有些人在dfs的初始调用中把mod设为0，这是正确的；但有些人在递归过程中把newMod算成了(mod + d) % 13，这就完全错了。正确的公式是(mod * 10 + d) % 13，因为每填入一位数字，原来的前缀数值要乘以10再加上当前位。

还有一个隐蔽的错误是digit数组的下标处理。如果digit数组从下标0开始存储最低位，那么dfs的终止条件应该是pos < 0而不是pos == 0。这种下标偏移错误在调试时很难发现，因为代码可能在小数据上跑出正确结果，但在大数据上就出问题了。

4.2 记忆化搜索的缓存失效问题

记忆化搜索的核心是缓存，但如果缓存条件写错了，就会导致结果错误。最常见的错误是在limit为true的时候也去查缓存。因为limit为true的状态依赖于具体的上界数字，不同的上界数字对应的结果不同，如果缓存了limit为true的状态，下次遇到相同的pos、mod、state但不同的上界时，就会返回错误的结果。

正确的做法是：只有在limit为false的时候才查缓存和存缓存。limit为true的状态直接计算，不缓存。这个规则在所有的数位DP题目中都适用，务必牢记。

另一个缓存相关的坑是dp数组的初始化。如果多组数据之间没有清空dp数组，而dp数组的状态定义又依赖于某些全局变量，就会导致错误。对于B-number来说，dp数组的状态定义不依赖于任何全局变量，所以理论上可以不清空。但为了代码的健壮性，建议每组数据都清空一次。

4.3 调试技巧与验证方法

调试数位DP代码的时候，最有效的方法是写一个暴力枚举程序来对拍。暴力程序可以简单地遍历1到n的所有数字，逐个判断是否包含“13”且能被13整除。然后用随机生成的n来测试两个程序的输出是否一致。如果发现不一致，可以缩小n的范围，找到第一个出错的n，然后手动分析这个n的每一位是如何被处理的。

另一个调试技巧是在dfs函数中打印中间状态。比如在每次递归调用时打印pos、mod、state、limit和当前枚举的d，观察状态转移是否符合预期。这种方法虽然输出量大，但对于定位状态转移错误非常有效。

对于B-number这道题，还可以用一些特殊值来验证。比如n=13时，答案应该是1（只有13本身满足条件）；n=26时，答案应该是1（13满足，26不满足）；n=130时，答案应该是2（13和130都满足）。用这些特殊值来测试代码，能快速发现明显的逻辑错误。

5. 数位DP的通用模板与扩展应用

5.1 从B-number抽象出的通用模板

B-number虽然是一道具体的题目，但它的解法可以抽象成一个通用的数位DP模板。这个模板的核心结构是：一个dfs函数，参数包括位置、若干状态变量、以及上界标记；一个记忆化数组，用于缓存不受上界约束的状态；一个solve函数，负责把数字拆位并调用dfs。

通用模板的伪代码大致如下：

int dfs(int pos, StateType state, bool limit) { if (pos == 0) return check(state) ? 1 : 0; if (!limit && dp[pos][state] != -1) return dp[pos][state]; int up = limit ? digit[pos] : 9; int res = 0; for (int d = 0; d <= up; d++) { StateType newState = transition(state, d); res += dfs(pos - 1, newState, limit && d == up); } if (!limit) dp[pos][state] = res; return res; }

这个模板可以套用到大多数数位DP题目上，只需要根据具体题目定义StateType和transition函数即可。StateType可以是一个整数、一个结构体、或者多个整数的组合。transition函数负责根据当前状态和填入的数字计算新状态。

5.2 数位DP的常见变体与扩展

数位DP的变体非常多，常见的扩展方向包括：统计满足多个条件的数的个数、统计满足条件的数的和、统计满足条件的数的平方和等。对于求和的问题，状态中需要额外记录当前已经形成的数的和以及数的个数，转移的时候需要用到一些数学公式。

另一个常见的扩展是处理二进制或其他进制。数位DP不仅适用于十进制，也适用于二进制、八进制等任意进制。只需要把拆位和枚举数字的部分改成对应的进制即可。比如二进制数位DP中，每位只能填0或1，状态转移会更简单。

还有一种扩展是处理区间查询。前面提到过，区间[a, b]的查询可以通过solve(b) - solve(a-1)来实现。但如果题目要求的是区间内满足条件的数的某种统计量（比如和），那么直接相减可能不行，需要更复杂的处理。这时候可以考虑在状态中记录更多信息，或者使用差分的思想。

5.3 数位DP与其他算法的结合

数位DP经常和其他算法结合出现。比如与矩阵快速幂结合，处理位数非常大的情况；与AC自动机结合，处理多模式串匹配的问题；与状压DP结合，处理状态空间较大的问题。这些结合方式在高级题目中很常见，但核心思想仍然是数位DP的那一套：按位处理、状态压缩、记忆化搜索。

对于B-number这道题来说，它本身已经涵盖了数位DP的核心要素：多维度状态、上界约束、记忆化缓存。把这题吃透，再去看其他数位DP题目，会发现很多都是类似的套路。我个人建议是先把B-number这类经典题反复写几遍，直到能闭着眼睛写出正确的状态转移，然后再去挑战更复杂的变体。

6. 实操中的性能优化与代码风格建议

6.1 记忆化数组的维度压缩

在实际写题的时候，记忆化数组的维度直接影响缓存效率。对于B-number，dp数组是三维的：dp[15][13][3]。如果能把某些维度合并，就能减少缓存miss。比如state只有3种取值，可以把它编码进mod维度中，变成dp[15][39]，其中mod*3+state作为新的索引。这样做的好处是数组更紧凑，缓存局部性更好。

不过对于B-number这种状态数本来就不大的题目，维度压缩带来的性能提升微乎其微。但在状态数较大的题目中，维度压缩能显著减少内存占用和缓存miss。这是一个值得养成的编码习惯。

6.2 递归深度与栈溢出风险

数位DP的递归深度等于数字的位数。对于10位以内的数字，递归深度最多10层，完全不会有栈溢出风险。但如果题目中的数字位数达到100位甚至1000位（比如处理大整数），那么递归深度就会很大，可能导致栈溢出。这时候需要把递归改成迭代，或者手动增大栈空间。

对于B-number来说，数字位数最多10位，递归深度很小，不需要担心栈溢出。但在写通用模板的时候，最好考虑到这个风险，必要时使用迭代版本的数位DP。

6.3 代码风格与可读性建议

数位DP的代码虽然不长，但状态转移的逻辑比较绕，容易写错。建议在写代码的时候，把状态的定义和转移规则用注释写清楚，方便自己和他人阅读。变量命名也要有意义，比如用has13而不是h，用remainder而不是r。

另外，建议把dfs函数和solve函数分开写，solve函数负责拆位和初始化，dfs函数负责状态转移。这样代码结构更清晰，也方便调试。如果题目有多组数据，可以在main函数中循环调用solve函数。

最后，建议在写完之后用暴力程序对拍，确保正确性。数位DP的边界条件比较多，手动测试很难覆盖所有情况，对拍是最可靠的验证方法。