最近带学生刷《信息学奥赛一本通》的时候1313这道“位数问题”几乎隔一阵子就有人卡住。题面很短在所有的N位数中有多少个数中含有偶数个数字3答案对12345取模N给到1000。第一眼看过去像小学奥数脑筋急转弯但放到“递推算法”这个章节里它其实是一道非常典型的状态设计题核心考两个点递推状态怎么定义以及前导零怎么处理。对准备CSP-J/S、或者刚学完递推想刷题巩固的选手来说这一题值得彻底吃透。这篇我就用最容易理解的方式把从题意拆解到AC代码再到延伸扩展的完整过程讲清楚。1. 题目到底在问什么别被“位数”两个字带偏1.1 题面还原与三个容易漏掉的细节标准题面是这样的在所有的N位数中有多少个数中有偶数个数字3由于结果可能很大你只需要输出这个答案对12345取余数的值。输入一个整数N输出一个整数答案。这句话里藏着三个细节初次做的人很容易忽略第一“N位数”严格来说就是N位的正整数最高位不能是0。三位数指的是100到999而不是000到999。这一点直接关系到最后的答案也是网上很多题解吵来吵去的地方。第二“含有偶数个数字3”里的偶数包括0。也就是说一个数里一个3都没有也算“偶数个3”。这个细节不理解的话n1的答案你就没法算对。第三为什么要对12345取模因为这题的答案会非常大。N1000的时候真值是一个几千位的天文数字不取模连long long都装不下。取模既是题目约束也是在暗示你N很大别想暴力。1.2 先手推两个小数据做题之前先手动算两个小规模的情况能帮你验证后面所有推导。N1时一位正整数是1到9。这9个数里只有数字3含有一个3是奇数个其余8个数1、2、4、5、6、7、8、9都不含30个3算偶数个。所以答案是8。N2时两位数从10到99。先看完全不含3的数十位可以是1、2、4、5、6、7、8、9共8种个位可以是0、1、2、4、5、6、7、8、9共9种。两者相乘得到72个。再看含有偶数个3且不是0个的这里只能是“含有两个3”的情况也就是一个数是33只有1个。所以答案等于72加1是73。这两个结果记下来后面代码跑出来的答案必须和它们一致。1.3 为什么暴力枚举必挂有些新手看到这题的第一反应是写个循环从10^(N-1)枚举到10^N-1数一下含3个数然后统计。这个思路在小数据下完全正确但N1000时你要访问10的999次方量级的数这个规模比宇宙中的粒子数还多好几个数量级程序跑完地球毁灭都不可能出结果。所以题目放在“递推算法”这一章就是在告诉你别枚举去找规律让第i步的结果能从第i-1步的结果直接推出来。计数类问题一旦规模变大第一反应永远是“能不能递推”而不是“能不能枚举”。2. 核心思路用“允许前导零的字符串”做递推2.1 状态设计dp[i][0]和dp[i][1]真正动手递推之前先做一个看起来很“绕”的变换暂时把“N位数”放宽成“长度为i的十进制数字串允许第一位是0”。定义两个状态dp[i][0]长度为i的串中数字3出现偶数次的串的数量dp[i][1]长度为i的串中数字3出现奇数次的串的数量。这里的“串”是允许前导零的。比如i2时“03”和“33”都算长度为2的串。为什么要这样放宽这是我个人认为这道题最值得学的地方。你想啊如果严格按“首位不能为0”来递推每次往最高位放数字的时候都要额外判断“当前是不是第一位”。这一判断不仅写起来麻烦还容易漏。而如果先假设每一位都能放0到9任意一个数字整个递推过程就非常干净因为每一位的可选数字数都一样。算完之后我们只需要把所有“最高位是0”的串统一减掉就行。这个“先算全集再扣掉不合法的子集”的思路在计数题里非常通用。2.2 递推式的完整推导现在考虑从长度为i-1的串扩展成长为i的串。所谓扩展就是在原串末尾追加一位数字。检查一下追加什么数字会影响偶奇性。如果追加的数字是3只有1种放法。原来偶数个3的串追加后变成奇数个3原来奇数个3的串追加后变成偶数个3。用式子表达就是从dp[i-1][1]转移到dp[i][0]从dp[i-1][0]转移到dp[i][1]。如果追加的是0、1、2、4、5、6、7、8、9一共9种放法。这些数字不会改变3的个数。所以dp[i][0]需要加上dp[i-1][0]乘以9dp[i][1]需要加上dp[i-1][1]乘以9。把两种情况合并就得到核心递推式dp[i][0] dp[i-1][1] dp[i-1][0] * 9 dp[i][1] dp[i-1][0] dp[i-1][1] * 9所有中间结果对12345取模。我给初学者讲这个式子的时候喜欢把它比喻成开关问题数字3就是墙上的一个开关遇到一次3就按一下奇偶性翻转遇到其他数字等于什么都没发生。你只关心最后灯是开还是关不关心之前按了多少次。这就是为什么状态只有0和1两维而不是记录“具体出现了几个3”——具体数字对答案没影响奇偶性就足够。2.3 边界为什么要从空串开始边界条件我喜欢写成dp[0][0] 1dp[0][1] 0。含义是长度为0的串只有空串一种里面0个3而0是偶数所以它属于“偶数个3”这一类。这个边界看起来抽象但非常优雅。它让循环可以从i1直接跑到iN不需要对N1做特殊判断。有些资料把边界写成dp[1][0]9、dp[1][1]1那样循环要从i2开始并且算N1时要单开逻辑。这两种写法在绝大多数数据下结果一样但“空串起步”在逻辑上最完整后面讲答案计算时你会看到它的好处。3. 从“所有串”到“真N位数”减去首位为0的计数3.1 答案为什么是dp[n][0]减dp[n-1][0]dp[n][0]统计的是所有长度为n、允许前导零的串中数字3出现偶数次的串的数量。但我真正想要的是N位数——首位不能为0。所以必须从dp[n][0]里剔除所有“最高位是0”的串。最高位如果是0把这个0去掉之后剩下的部分就是一个长度为n-1的串。注意去掉最高位的0并不会改变数字3出现的次数。因此“最高位是0且数字3出现偶数次”的串的数量恰好等于dp[n-1][0]。所以答案就是ans dp[n][0] - dp[n-1][0]由于做了取模减法结果可能是负数所以要补一个MOD再取模ans (dp[n][0] - dp[n-1][0] 12345) % 12345;这个“减前一位”的操作其实就是把前导零统一扣掉。理解它比记住公式重要因为很多同类递推题最后都要做这一步。3.2 完整AC代码C#include bits/stdc.h using namespace std; const int MOD 12345; int dp[1005][2]; int main() { int n; cin n; // 空串长度为00个3属于偶数个3 dp[0][0] 1; dp[0][1] 0; for (int i 1; i n; i) { dp[i][0] (dp[i - 1][1] dp[i - 1][0] * 9) % MOD; dp[i][1] (dp[i - 1][0] dp[i - 1][1] * 9) % MOD; } int ans (dp[n][0] - dp[n - 1][0] MOD) % MOD; cout ans endl; return 0; }如果你用的评测环境不支持#include bits/stdc.h改成#include iostream也一样。数组开1005是因为N最大到1000dp[0]也要用多开几个防止下标越界。整个运算过程中dp[i-1]最大不超过12344乘9之后也不到12万int完全装得下不需要long long。3.3 用n2、n3验证代码把dp表的前几行展开idp[i][0]dp[i][1]两数之和0101191102821810037562441000先验证n2dp[2][0]减dp[1][0]82减9等于73和前面手推完全一致。再验证n3答案等于756减82674。你也可以自己口算验证三位数不含3的有8×9×9648个含两个3的情况分三种讨论33X有9个、3Y3有9个、Z33有8个合计648加26等于674。对上号了。这个表里最左边那列“两数之和”每一行都是10^i正好是全部长度为i的串的总数。这其实是个非常好的自检指标如果你代码算出来的dp[i][0]和dp[i][1]之和不等于10的i次方取模后的值那说明递推式一定写错了。4. 进阶矩阵快速幂与数位DP把这道题的价值榨干4.1 N如果变成1e9递推变矩阵如果题目改一下N给到10的9次方O(N)的递推也扛不住了。但幸运的是我们的递推式是线性齐次的可以写成矩阵形式[ dp[i][0] ] [9 1] [ dp[i-1][0] ] [ dp[i][1] ] [1 9] [ dp[i-1][1] ]初始向量是[1, 0]的转置对应dp[0][0]1dp[0][1]0。用矩阵快速幂可以在O(log N)时间内算出第N层。核心代码片段是这样的struct Mat { int a[2][2]; Mat(bool E false) { memset(a, 0, sizeof(a)); if (E) a[0][0] a[1][1] 1; } Mat operator*(const Mat other) const { Mat c; for (int i 0; i 2; i) for (int j 0; j 2; j) for (int k 0; k 2; k) c.a[i][j] (c.a[i][j] a[i][k] * other.a[k][j]) % MOD; return c; } }; Mat power(Mat base, int exp) { Mat res(true); while (exp 0) { if (exp 1) res res * base; base base * base; exp 1; } return res; }使用时构造转移矩阵M分别算出M的n次方和n-1次方Mat M; M.a[0][0] 9; M.a[0][1] 1; M.a[1][0] 1; M.a[1][1] 9; Mat A power(M, n); Mat B power(M, n - 1); // 初始向量是 [1,0]^T所以取第0行第0列即可 int ans (A.a[0][0] - B.a[0][0] MOD) % MOD;这个版本对原题来说属于超纲但如果你学到矩阵快速幂再回头看这道题会发现它就是最标准的“线性递推转矩阵”入门题。4.2 数位DP视角奇偶状态的记忆化搜索再换一个角度。如果题目变成“给定L求1到L之间有多少个数含有偶数个3”前面的整体递推法就用不了了因为这要求统计范围不是完整的“所有N位数”而是某个任意上界。这时候要用数位DP。数位DP的状态里除了常规的pos当前处理到第几位、limit是否贴着上界、lead是否还在前导零阶段真正描述“3出现次数”的只需要一个0/1变量parity就可以。每遇到一个数字3就把parity异或1其他数字不影响它。int dfs(int pos, int parity, bool limit, bool lead) { if (pos n) return parity 0; if (!limit !lead memo[pos][parity] ! -1) return memo[pos][parity]; int up limit ? s[pos] - 0 : 9; int res 0; for (int d 0; d up; d) { if (lead d 0) res dfs(pos 1, parity, limit d up, true); else res dfs(pos 1, parity ^ (d 3), limit d up, false); } if (!limit !lead) memo[pos][parity] res; return res; }你会看到1313这道题其实是这个模板在L10^N-1时的一个特例因为上界是完整的limit一直为false最后再统一处理前导零扣减。把这道递推题吃透再去看数位DP会轻松很多。4.3 常见变体清单这类“数字出现次数奇偶性”的题有一大堆变体而且套路高度统一把3换成其他数字k只需要把递推式里追加数字时的判断从d3改成dk要求奇数个3最后返回parity1要求至少出现两次3状态要扩展成0没出现过3、1出现过一次、2出现过两次及以上不能只用一维奇偶要求统计3出现的总次数而不是个数的奇偶那就不是纯计数题递推式要改成包含“位置权重”的形式思路完全不同。每一道变体本质上都在做同一件事把“3出现的次数”压缩成尽可能小的状态再用转移来更新它。这个建模思想才是这道题真正值钱的地方。5. 刷题实测中的几个坑取模、边界、对拍5.1 取模减法的坑这是最容易踩的坑。公式是dp[n][0]减dp[n-1][0]但两个数都是取模之后的结果谁大谁小完全不确定。如果dp[n][0]比dp[n-1][0]小直接相减会得到负数而C里负数取模的结果还是负数输出就WA了。正确做法是加上MOD再取模int ans (dp[n][0] - dp[n - 1][0] MOD) % MOD;因为dp数组的两个值都在0到12344之间差的最小值是负12344加一次MOD就足够保证非负。如果以后遇到差可能超过MOD的情况再写成(x % MOD MOD) % MOD也不迟。5.2 网上两种边界的争议刷题时会发现网上题解分成两派写法初始边界n1时输出缺点A写法dp[1][0]9, dp[1][1]1循环从2开始需要特判可能输出9把0也算进一位数概念上不严谨B写法dp[0][0]1, dp[0][1]0循环从1开始自动得到8需要理解“空串”这个抽象边界我强烈建议采用B写法。它不依赖特判而且“先算允许前导零的串再减掉首位0”的思路在全过程中保持一致。如果你在某个OJ上看到答案要求输出9那多半是题目对“N位数”的定义有额外说明或者评测数据把0算进了一位正整数。但按通常的信息学奥赛题面一位正整数不含0答案就应该是8。5.3 用暴力对拍验证自己的代码每次做这种组合计数题我都建议在本地写一个暴力程序对小数据对拍。Python写起来最快def dp_ans(n): MOD 12345 even, odd 1, 0 pre_even 0 for i in range(1, n 1): pre_even even ne (odd even * 9) % MOD no (even odd * 9) % MOD even, odd ne, no return (even - pre_even) % MOD def brute(n): cnt 0 for x in range(10 ** (n - 1), 10 ** n): if str(x).count(3) % 2 0: cnt 1 return cnt % 12345 for n in range(1, 7): print(n, dp_ans(n), brute(n), dp_ans(n) brute(n))n1到6足够覆盖两位数、三位数、四位数几个关键边界。如果全部输出True你的递推式基本可以放心交上去。这段脚本我至今还在用碰到类似的递推题直接改改范围就能复用。5.4 空间滚动优化递推式里dp[i]只依赖dp[i-1]所以根本不需要开1005×2的二维数组。用两个变量滚动就行int even 1, odd 0, preEven 0; for (int i 1; i n; i) { preEven even; int ne (odd even * 9) % MOD; int no (even odd * 9) % MOD; even ne; odd no; } cout (even - preEven MOD) % MOD endl;这里的preEven要在更新even之前保存循环结束后它正好是dp[n-1][0]。滚动数组对这题不是必须的但它体现了递推题里常见的空间压缩思维改其他题时经常用到。说实话1313在《信息学奥赛一本通》里算不上难题但它把计数题最重要的两个概念浓缩在了一起一个是“只关心奇偶性”的状态建模另一个是前导零的扣除。我早期做这道题时也在n1输出8还是9上纠结过后来一直沿用“空串起步、最后减前一位”的写法整个思路顺了很多。如果你正在刷一本通建议做完这题顺手把验证脚本留着后面遇到类似的递推题直接拿它协助对拍。这道题刷透之后很多“数字出现次数”类的题目你都会觉得格外亲切。