第一次在信息学奥赛一本通递推章节刷到1313题“位数问题”时，我盯着题干里“偶数个数字3”这句话半天没缓过神。老实说，我一开始是打算硬枚举的：for循环从10^(n-1)扫到10^n-1，逐个统计3出现的次数，再判断奇偶。这个思路对n=1、n=2当然没问题，可等我把n=10的数据敲进去，程序跑得比乌龟还慢，n=20直接卡死。那一刻我意识到：这题不是考你会不会写循环，是考你愿不愿意把“一个一个数”换成“用已知推未知”的递推。今天这篇就想把这题从读题到AC的全过程掰开揉碎讲清楚，包括状态为什么设计成二维、第一位为什么要单独处理、踩过的坑长什么样，文末再聊聊怎么用一套思路把递推章节的其他题也吃透。无论你是刚接触信息学奥赛一本通的新手，还是准备普及组复赛想巩固递推的选手，这篇都应该对你有用。
1. 位数问题到底在问什么：把题面翻译成人话
1.1 原题重述与数据范围
信息学奥赛一本通1313题，原名“位数问题”，题面很短：在所有的N位数中，有多少个数中有偶数个数字3？由于结果可能很大，你只需要输出这个答案对12345取余的值。输入一个整数n，输出一个整数，n的范围是1到1000。
这里有个容易忽略的细节——题目说的是“N位数”，不是“长度为N的字符串”。这意味着最高位不能是0。10到99是两位数，而00到99里的“05”这种不能算两位数。这个“首位不能为0”的约束，就是后面初始化时的关键，也是很多人第一次提交WA的原因。
n最大到1000，这不是个随便给的范围。如果n=1000时让我枚举，我连方案总数都数不清：所有N位数的个数是9×10^(n-1)，n=1000时这个数字有1000位，别说什么“逐个统计”了，哪怕只是把这个数完整打印出来，都要占1KB的输出空间。所以这道题从一开始就把枚举这条路彻底堵死了。
1.2 先算一笔账：硬枚举为什么必死无疑
我们可以做一个简单的复杂度分析。枚举的思路是：从10^(n-1)开始，到10^n-1结束，逐个检查。假设n=20，要检查的数字有9×10^19个，就算你的机器一秒能检查一亿个数字，也需要9×10^11秒，也就是差不多三万年。
就算退一步，不要求1秒内跑完，光是把n=1000对应的答案数量级写出来，就已经是一个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] × 1
f[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出现的次数不是偶数就是奇数，没有第三种情况。这个总数校验可以让你的错误无处遁形，后面踩坑部分我会展开说。
代入检验一下：i=2时，f[2][0] = 8×9 + 1 = 73，f[2][1] = 1×9 + 8 = 17，加起来等于90，正好是两位数的总数。i=3时，f[3][0] = 73×9 + 17 = 674，f[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] = 1，f[0][1] = 0，表示“0位数”时有1种情况（就是空串），然后从i=1开始推？理论上可以，但直接算的话，f[1][0] = f[0][0]×9 + f[0][1] = 9，又把0算进去了。这个0位数初始化只适合“首位允许是0”的问题，也就是把N位数当成N位密码来数。但本题明确要求N位数，首位不能为0，所以最干净的做法就是单独处理f[1]，然后从i=2开始递推。
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，总共才123440，int完全放得下。如果你忘了中间取模，f数组在n>20左右就开始溢出，打印出来全是负数，这种错误特别难查。 一个安全的习惯是：递推式里只要涉及乘法加法，就在同一行内取模。
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。n=1000时MAXN开到1005完全够。如果n=1，for循环直接不执行，输出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，导致n=1就错
这是高频错误，错误率可能超过一半。原因很直接：脑子里想着“除了3以外有9个数字”，忽略了“一位数的集合里没有0”。f[1][0]=9会直接导致n=1时输出9，而正确答案是8。更隐蔽的是，即使n=2，错误初始化也会让答案偏离，只是如果最后对12345取模，可能表面看不出规律。
自查方法：先把n=1的答案和n=2的答案手算出来。n=1时1到9一共9个数，只有3含奇数个3，剩下8个都是偶数个3，答案8。n=2时两位数一共有90个，73个偶数个3、17个奇数个3，答案73。如果代码输出不对，优先检查初始化。
这里我还想特别强调一个做题习惯：任何计数类题目，在写递推之前，先自己把最小规模的数据手算出来。这不仅是给代码准备测试数据，更是逼自己确认对题意的理解没有偏差。
5.2 坑二：忘记中间取模，数一大了全是负数
递推式里如果只在最后取模，n=20左右，f数组就会超过int上限。因为f[i-1]如果已经到了20亿级别，乘9之后直接溢出成负数。这时候你看到的不是“WA”，而是“输出负数”，甚至有些时候因为溢出后碰巧模出来的数和正确答案一致，导致你排查半天找不到问题。
我的建议是：从第一天写递推题开始，就在每个加法乘法表达式里对MOD取模，养成肌肉记忆。不要等出了问题再补。这个习惯在n=1000、MOD=12345的题里特别重要，因为中间结果每行都可能有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 坑四：边界n=1处理不当，甚至漏掉输入
n=1的时候，for循环应该一次都不执行。只要初始化和循环条件写对，这段不会有问题，但有些人喜欢从0开始初始化f[0][0]=1，那就得额外判断首位，稍微走神就会错。
还有一个实际问题：有些OJ为了减少题目数量，会把多组测试数据塞到一个输入文件里，要求你while(cin >> n)循环处理。如果题面写的是“输入一行一个整数n”，那单组就好；但保险起见，你的主程序最好也支持多组输入——可以把数组或滚动变量放在while循环内部重置，避免上一组的数据污染下一组。这道题原题是单组输入，但如果你的代码写成while(cin>>n)，在单组评测下也能过，因为程序在读完最后一个数据后正常退出。我一般建议写成while(cin>>n)的形式，一举两得。
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这题我写过不止一遍，每次写都有新理解——第一次是学会了设二维状态，第二次是理解了取模时机，第三次是明白了滚动变量的时序，再往后才是矩阵快速幂的拓展。这个递进过程，比单纯记住一道题的代码有价值得多。希望你能绕开我踩过的坑，把这题吃透，顺便把递推这种“用已知推未知”的思维方式真正长在自己身上。
