第一次在信息学奥赛一本通递推章节刷到1313题“位数问题”时我盯着题干里“偶数个数字3”这句话半天没缓过神。老实说我一开始是打算硬枚举的for循环从10^(n-1)扫到10^n-1逐个统计3出现的次数再判断奇偶。这个思路对n1、n2当然没问题可等我把n10的数据敲进去程序跑得比乌龟还慢n20直接卡死。那一刻我意识到这题不是考你会不会写循环是考你愿不愿意把“一个一个数”换成“用已知推未知”的递推。今天这篇就想把这题从读题到AC的全过程掰开揉碎讲清楚包括状态为什么设计成二维、第一位为什么要单独处理、踩过的坑长什么样文末再聊聊怎么用一套思路把递推章节的其他题也吃透。无论你是刚接触信息学奥赛一本通的新手还是准备普及组复赛想巩固递推的选手这篇都应该对你有用。1. 位数问题到底在问什么把题面翻译成人话1.1 原题重述与数据范围信息学奥赛一本通1313题原名“位数问题”题面很短在所有的N位数中有多少个数中有偶数个数字3由于结果可能很大你只需要输出这个答案对12345取余的值。输入一个整数n输出一个整数n的范围是1到1000。这里有个容易忽略的细节——题目说的是“N位数”不是“长度为N的字符串”。这意味着最高位不能是0。10到99是两位数而00到99里的“05”这种不能算两位数。这个“首位不能为0”的约束就是后面初始化时的关键也是很多人第一次提交WA的原因。n最大到1000这不是个随便给的范围。如果n1000时让我枚举我连方案总数都数不清所有N位数的个数是9×10^(n-1)n1000时这个数字有1000位别说什么“逐个统计”了哪怕只是把这个数完整打印出来都要占1KB的输出空间。所以这道题从一开始就把枚举这条路彻底堵死了。1.2 先算一笔账硬枚举为什么必死无疑我们可以做一个简单的复杂度分析。枚举的思路是从10^(n-1)开始到10^n-1结束逐个检查。假设n20要检查的数字有9×10^19个就算你的机器一秒能检查一亿个数字也需要9×10^11秒也就是差不多三万年。就算退一步不要求1秒内跑完光是把n1000对应的答案数量级写出来就已经是一个1000位的整数。这个数量级远超过unsigned long long能表示的范围unsigned long long最大约1.8×10^19也就是20位。所以即使枚举速度允许还需要自己写大数加法和大数取模复杂度直接起飞。这说明什么说明出题人把n开到1000就是在逼你换思路不要构造出每一个N位数而是从“小规模结果”出发推导“大规模结果”。这个思路就是递推也叫动态规划的最基础形态。任何一个合格的竞赛选手看到“某个计数问题结果取模n特别大”第一反应都应该是递推而不是枚举。1.3 剥掉外壳看本质其实只需要知道奇偶性在动手设计递推之前先把“偶数个数字3”这个条件拆一拆。一个N位数里数字3可能出现0次、1次、2次……直到N次。我们并不关心它具体出现了多少次只关心它是奇数还是偶数。这个“只关心奇偶”的观察是整个题目的题眼。为什么这么说因为当我们要从N-1位数扩展到N位数时新加的那一位数字只有两种可能它要么是3要么不是3。如果是3那么3的个数奇偶性会翻转如果不是3奇偶性保持不变。也就是说不管前面那N-1位数字具体长成什么样对后一位来说它们只分为两类——3出现偶数次的和3出现奇数次的。把数以万计的具体数字压缩成两个状态这就是递推能成立的根本原因。如果题目改成“求所有N位数中有多少个数字3出现次数恰好等于5”那递推状态就要复杂得多因为你需要记录“已经出现了0个、1个、2个……5个”这些详细情况。但只问奇偶两个状态就够了。这一步压缩就是状态设计的雏形。2. 状态设计是怎么想出来的f[i][0]和f[i][1]的含义2.1 一维数组为什么不够用有了“只关心奇偶”这个观察一个很自然的尝试是设f[i]表示“i位数中数字3出现偶数次的个数”。然后你就会发现递推写不下去f[i]和f[i-1]之间没有固定的关系。原因是这样的当我给一个i-1位数后面再添一位时最终的i位数要满足“3出现偶数次”需要分两种情况第一种是原来的i-1位数里3出现偶数次新添的那一位不是3第二种是原来的i-1位数里3出现奇数次新添的那一位是3。问题是f[i-1]只告诉了我“偶数次”的个数没告诉“奇数次”的个数。第二种情况根本没法算。这就是一维状态的信息缺失。你不是不知道怎么做这个加法而是没有把做加法需要的原料准备齐全。所以必须再加一个数把“3出现奇数次”的个数也记录下来。于是就有了二维数组f[i][0]和f[i][1]的雏形。2.2 一个生活化类比收发室按奇偶分账我给学生讲这道题时喜欢打个比方。假设你是一个收发室管理员要统计校园里每个人收过几次快递但不需要知道具体次数只需要知道每个人收没收过偶数次快递。那你手里得掌握两个分类账本一本记的是“已经收了偶数次的人”另一本记的是“已经收了奇数次的人”。现在有新人加入了或者又到了一个快递你该怎么更新账本如果这个人是“偶数次”的人他这次没收到快递那他还留在偶数本里如果他收到一个快递他就翻到了奇数本。如果这个人是“奇数次”的人他这次没收到快递还在奇数本收到一个快递就翻到偶数本。你看每次更新都同时需要两本账少了任何一本另一本都没法算。这里的“快递”就是数字3“收到/没收到”就是新增的这一位填3还是不填3。f[i][0]是偶数账f[i][1]是奇数账两条账一起记才能往下推。2.3 状态转移的动作拆解9种保持和1种翻转现在正式定义f[i][0]表示i位数中数字3出现偶数次的个数f[i][1]表示i位数中数字3出现奇数次的个数。假设我们已经知道了所有i-1位数的分类情况现在在末尾添上第i位。第i位可以填0到9这10个数字但填法要分两类看第一类填非3的数字0、1、2、4、5、6、7、8、9一共9种。不管原来那个i-1位数里3出现了奇数次还是偶数次新添一位非3数字都不会改变3的总次数所以奇偶性保持不变。这一位填的时候要注意第i位不是最高位所以可以填0这里一定是9种不是8种。第二类填数字3只有1种。这个行为会让3的总次数加1奇偶性翻转。原来偶数次的变成奇数次原来奇数次的变成偶数次。所以两只脚都能走路了新的偶数状态来源于“原来的偶数状态×9”加上“原来的奇数状态×1”新的奇数状态来源于“原来的奇数状态×9”加上“原来的偶数状态×1”。这个“×9”和“×1”不是拍的是把10个数字按“是否影响3的奇偶性”分成9和1两组一一对应过来的。3. 转移方程、初始化与取模把递推式写得滴水不漏3.1 两条方程的正式推导把上面的分析写成式子就是f[i][0] f[i-1][0] × 9 f[i-1][1] × 1f[i][1] f[i-1][1] × 9 f[i-1][0] × 1我怎么验证这个式子对不对有一个非常关键的校验方法无论何时f[i][0]加上f[i][1]必须等于所有i位数的总数也就是9×10^(i-1)。因为每个i位数3出现的次数不是偶数就是奇数没有第三种情况。这个总数校验可以让你的错误无处遁形后面踩坑部分我会展开说。代入检验一下i2时f[2][0] 8×9 1 73f[2][1] 1×9 8 17加起来等于90正好是两位数的总数。i3时f[3][0] 73×9 17 674f[3][1] 17×9 73 226加起来等于900正好是三位数的总数。这个规律不会骗人一旦你发现f[i][0]f[i][1]不等于9×10^(i-1)那一定是某一步写错了。3.2 首家为什么特殊f[1]不是9而是8方程拿到手下一步是定初始值。很多人会不假思索地写一位数里3出现偶数的有9个3出现奇数的有1个——错了错得离谱。一位数是从1到9不包括0。0不是一位数这一点在数学上是有定义的。所以一位数里根本没有“0”自然也不能把0算进“3出现偶数次”的集合里。正确的初始化是f[1][0] 8对应数字1、2、4、5、6、7、8、9这8个数里3出现0次0是偶数f[1][1] 1对应数字3本身3出现1次是奇数。你可能会问那我能不能设一个f[0][0] 1f[0][1] 0表示“0位数”时有1种情况就是空串然后从i1开始推理论上可以但直接算的话f[1][0] f[0][0]×9 f[0][1] 9又把0算进去了。这个0位数初始化只适合“首位允许是0”的问题也就是把N位数当成N位密码来数。但本题明确要求N位数首位不能为0所以最干净的做法就是单独处理f[1]然后从i2开始递推。3.3 对12345取模的时机与原理题目说结果很大要对12345取模。这里有个常见的理解误区有人觉得是不是最后输出前取一次模就行了不是如果不中间取模f数组很快就会被撑爆。但你需要理解“每一步取模不会改变最终答案”这个性质。模运算有分配律(a × b) % m ((a % m) × (b % m)) % m(a b) % m ((a % m) (b % m)) % m。所以每一步都取模和最后取一次模结果是完全相同的。具体到代码里每次算f[i][0]和f[i][1]的时候乘完加完立刻%12345。因为12345不大f[i-1]里的数最多是12344乘9后是111096再加12344总共才123440int完全放得下。如果你忘了中间取模f数组在n20左右就开始溢出打印出来全是负数这种错误特别难查。 一个安全的习惯是递推式里只要涉及乘法加法就在同一行内取模。3.4 一个自查技巧打印总数校验上面那个f[i][0]f[i][1]等于9×10^(i-1)的校验刷题时特别好用。具体做法是把递推过程打印出来每推一行都算一下两个数之和是否等于9×10^(i-1)一旦发现不等就可以断定这一行的转移方程或者取模时机出了问题。还有个小细节9×10^(i-1)本身很大i到1000时这个数也远超int范围所以校验时你自己要先把9×10^(i-1)对12345取模再和(f[i][0]f[i][1]) % 12345对比。其实更简单直接看f[i][0]f[i][1]在不取模的时候是否等于9×10^(i-1)但那样又会溢出。所以我建议改成打印(f[i][0]f[i][1])%MOD提前算好9×10^(i-1)%MOD来对照。这个习惯能省下大量调试时间。4. AC代码实现从二维数组到滚动变量再到递归4.1 二维数组版代码与逐行拆解先上一个最直接、最容易理解、也最建议打稳的版本#include iostream using namespace std; const int MOD 12345; const int MAXN 1005; int f[MAXN][2]; int main() { int n; cin n; f[1][0] 8; // 一位数中3出现偶数次的个数1,2,4,5,6,7,8,9 f[1][1] 1; // 一位数中3出现奇数次的个数3 for (int i 2; i n; i) { f[i][0] (f[i-1][0] * 9 f[i-1][1] * 1) % MOD; f[i][1] (f[i-1][1] * 9 f[i-1][0] * 1) % MOD; } cout f[n][0] endl; return 0; }代码没什么玄机f[MAXN][2]开全局是为了自动清零省得memset。n1000时MAXN开到1005完全够。如果n1for循环直接不执行输出f[1][0]8正确。注意f[i][0]和f[i][1]两行是相互独立赋值的f[i][0]只依赖f[i-1]一行的数据f[i][1]也只依赖f[i-1]一行的数据所以两条赋值语句谁先谁后都没关系这是二维数组版最省心的点。4.2 滚动变量版省空间但要小心更新顺序递推永远只依赖上一行的数据所以根本不需要开整个二维数组。用两个变量a和b分别表示“当前i位数中偶数个3的个数”和“奇数个3的个数”每轮算完就丢掉旧数据。代码如下#include iostream using namespace std; const int MOD 12345; int main() { int n; cin n; int a 8; // f[1][0] int b 1; // f[1][1] for (int i 2; i n; i) { int na (a * 9 b) % MOD; // 新的偶数状态 int nb (b * 9 a) % MOD; // 新的奇数状态 a na; b nb; } cout a endl; return 0; }这里有个新手特别容易踩的坑必须先把新的na和nb算好再同时更新a和b。如果直接写a (a9 b)%MOD然后b (b9 a)%MOD第二行里的a就已经是更新后的新值了整个递推就全乱套。我在第5节会专门把这个坑展开说。用滚动变量的好处不仅仅是省那么几KB内存更重要的是它逼着你把“这一轮”和“下一轮”的边界想清楚对理解递推的时间轴非常有帮助。4.3 记忆化递归写法换一个角度看状态循环写的递推是自底向上递归写的话就是自顶向下。这里介绍一种能加深理解的写法先定义calc(i, parity)表示“长度为i、首位允许为0的字符串”中数字3出现次数奇偶性为parity的方案数。这样就可以递归#include iostream #include cstring using namespace std; const int MOD 12345; int memo[1005][2]; int calc(int i, int parity) { if (i 0) return (parity 0) ? 1 : 0; if (memo[i][parity] ! -1) return memo[i][parity]; // 当前位填3奇偶翻转 int res calc(i-1, parity ^ 1); // 当前位填非3数字0~9中除了3共9种奇偶不变 res (res 9 * calc(i-1, parity)) % MOD; return memo[i][parity] res; } int main() { int n; cin n; memset(memo, -1, sizeof(memo)); // 最高位只能填1~9 // 最高位填3剩下n-1位必须让3的总数为奇数 // 最高位填非3非0的数字有8种剩下n-1位必须让3的总数为偶数 int ans (calc(n-1, 1) 8 * calc(n-1, 0)) % MOD; cout ans endl; return 0; }这个写法把“首位限制”和“后续位”分开处理乍一看比循环复杂但它把状态和转移暴露得更直白适合初学者对照理解。需要注意递归深度最大1000层在多数OJ上没问题但如果你遇到栈溢出的评测环境还是老老实实用循环。5. 踩坑实录这道题我见过最典型的四个错误5.1 坑一把f[1][0]初始化成9导致n1就错这是高频错误错误率可能超过一半。原因很直接脑子里想着“除了3以外有9个数字”忽略了“一位数的集合里没有0”。f[1][0]9会直接导致n1时输出9而正确答案是8。更隐蔽的是即使n2错误初始化也会让答案偏离只是如果最后对12345取模可能表面看不出规律。自查方法先把n1的答案和n2的答案手算出来。n1时1到9一共9个数只有3含奇数个3剩下8个都是偶数个3答案8。n2时两位数一共有90个73个偶数个3、17个奇数个3答案73。如果代码输出不对优先检查初始化。这里我还想特别强调一个做题习惯任何计数类题目在写递推之前先自己把最小规模的数据手算出来。这不仅是给代码准备测试数据更是逼自己确认对题意的理解没有偏差。5.2 坑二忘记中间取模数一大了全是负数递推式里如果只在最后取模n20左右f数组就会超过int上限。因为f[i-1]如果已经到了20亿级别乘9之后直接溢出成负数。这时候你看到的不是“WA”而是“输出负数”甚至有些时候因为溢出后碰巧模出来的数和正确答案一致导致你排查半天找不到问题。我的建议是从第一天写递推题开始就在每个加法乘法表达式里对MOD取模养成肌肉记忆。不要等出了问题再补。这个习惯在n1000、MOD12345的题里特别重要因为中间结果每行都可能有12344级别的数乘9以后依然在int安全范围内所以mod放在表达式最后非常干净。5.3 坑三滚动变量更新顺序写反数据全乱前面4.2节的代码里我把新值先存到na和nb再赋值给a和b这是有原因的。如果你写成a (a * 9 b) % MOD; b (b * 9 a) % MOD;第二行的a已经被更新成了第i轮的值但按照递推方程b的更新应该使用第i-1轮的a。这一字之差整个递推链条就断了。它的表现和坑二不一样不是溢出而是答案从某个n开始逐渐偏离正确值并且越来越离谱但总数校验又看不出因为你没打印总数。这个坑在二维数组版里不存在因为f[i][0]和f[i][1]都是往新的一行里写不会覆盖旧数据。所以如果你对滚动更新的时序还没完全掌握就先用二维数组稳了再优化成滚动变量。5.4 坑四边界n1处理不当甚至漏掉输入n1的时候for循环应该一次都不执行。只要初始化和循环条件写对这段不会有问题但有些人喜欢从0开始初始化f[0][0]1那就得额外判断首位稍微走神就会错。还有一个实际问题有些OJ为了减少题目数量会把多组测试数据塞到一个输入文件里要求你while(cin n)循环处理。如果题面写的是“输入一行一个整数n”那单组就好但保险起见你的主程序最好也支持多组输入——可以把数组或滚动变量放在while循环内部重置避免上一组的数据污染下一组。这道题原题是单组输入但如果你的代码写成while(cinn)在单组评测下也能过因为程序在读完最后一个数据后正常退出。我一般建议写成while(cinn)的形式一举两得。6. 练透递推从1313延伸到骨牌问题和更多变形6.1 递推题的通用三件套做完1313我强烈建议你停下来总结一套属于自己的递推做题流程。不管题目是讲的位数、骨牌、爬楼梯还是平面分割核心就三步定义状态、写转移方程、定初始值。定义状态时问自己三个问题这个题目要计数的是什么对象影响后续变化的信息有哪些这些信息能不能压缩成有限的几个状态在1313里对象是N位数影响后续的信息只有一个“3出现次数的奇偶性”所以状态是二维的。写转移方程时问自己从i-1规模到i规模新增的那个部分有几种处理方式每种方式分别影响哪些状态再复杂的问题只要新增部分的处理方式能被有限枚举转移方程就一定能写出来。定初始值时问自己最小规模是什么最小规模里有没有特殊的约束比如首位不能为0把最小规模的几种情况全部手算出来作为递推的基石。6.2 同章经典2×n骨牌覆盖问题信息学奥赛一本通递推章节里和1313齐名的还有一道典型的骨牌问题用1×2和2×1两种骨牌铺满2×n的矩形有多少种铺法。它的递推式是f[n] f[n-1] f[n-2]很多人背下来了但不理解为什么。用三件套分析铺满2×n矩形考虑最左边那一列怎么处理。第一种做法竖着放一块1×2的骨牌剩下的是一个2×(n-1)的矩形方案数是f[n-1]第二种做法横着放两块2×1的骨牌占掉左边两列剩下的是一个2×(n-2)的矩形方案数是f[n-2]。所以f[n]就是f[n-1]加f[n-2]。和1313对比一下骨牌问题是一维状态因为铺完剩下的矩形只有一个信息它还差多宽。1313是二维状态因为有奇偶两个信息。但递推的核心“从规模小的推到规模大的”是相通的。如果你能把这两题的“为什么这样设状态”讲给自己听递推这一章就算入门了。6.3 三个变形练习检验你是否真懂只做一道题远远不够我建议你试试这几个变形都能用递推解决第一个变形求N位数中有偶数个3且至少包含一个3的个数。这个可以直接复用f[n][0]但要减去“一个3都没有”的情况因为一个3都没有也属于偶数个3。没有3的N位数个数是8×9^(n-1)所以答案是f[n][0] - 8×9^(n-1)注意取模后可能为负要加MOD调整。第二个变形求N位数中数字3出现偶数次且数字5出现偶数次的个数。状态从二维变成四维f[i][a][b]a表示3出现次数的奇偶b表示5出现次数的奇偶。每次新增一位有10种填法分别判断填3、填5、填其他数字时对a和b的影响。这个变形练的是“状态扩展能力”题目变复杂后你更能体会到状态设计是递推的灵魂。第三个变形进阶如果n开到10^18普通递推循环1e18次肯定超时。这时可以观察转移方程是个线性变换写成矩阵形式然后用快速幂优化到O(log n)。状态向量是[f[i][0], f[i][1]]转移矩阵是[[9, 1], [1, 9]]初始化向量是[8, 1]。这一步不是必做的但如果你想在提高组往深了走递推矩阵快速幂是绕不开的组合。我个人在实际操作中还有一个体会刷递推题别急着看题解先逼自己写出完整的“状态定义、转移方程、初始值”三段笔记再写代码。1313这题我写过不止一遍每次写都有新理解——第一次是学会了设二维状态第二次是理解了取模时机第三次是明白了滚动变量的时序再往后才是矩阵快速幂的拓展。这个递进过程比单纯记住一道题的代码有价值得多。希望你能绕开我踩过的坑把这题吃透顺便把递推这种“用已知推未知”的思维方式真正长在自己身上。