刷《信息学奥赛一本通》的读者大概率在 1312 这道“昆虫繁殖”上卡过一下。这题表面上是一道生物题实际上是非常经典的递推入门题很多学校的信奥课都会拿它来讲“为什么需要状态拆分”。我当年第一次做的时候满脑子都在模拟每一对虫子的产卵和成长结果越写越乱样例都跑不对。后来换了思路先画时间轴再用“成虫数组 当月卵数组”两个状态互相推代码很快就写出来了。这篇文章就把完整思路、递推式的推导过程、参考代码和最容易踩的坑都整理出来给正在刷一本通、被这道题卡住的初学者一些可以直接照做的经验。1. 先别急着写代码读懂 x、y、z、n 四个参数1.1 这道题的任务到底是什么不同版本的一本通题号可能略有差别但以《信息学奥赛一本通》C 版的常见编排来说1312 对应“昆虫繁殖”。题面大意是有一种昆虫每对成虫过 x 个月开始产卵每对成虫每个月产 y 对卵每对卵要过 z 个月才能长成成虫。现在假设一开始只有一对成虫问 n 个月后总共有多少对成虫。这里四个参数一定要先分清楚x从“成为成虫的那个月”到“第一次可以产卵”需要经过的整月数。初始那一对成虫也不能例外它们在第 0 个月就已经是成虫但要等到第 x 个月才第一次产卵。y每对成虫每个月产卵的对数。这里要特别注意题面后面通常还会有一句话叫“每对成虫每个月初产卵”也就是说不是只产一次而是从可以产卵的那个月开始每个月都产。z卵长成成虫需要的整月数。第 i 个月初产下的卵要到第 iz 个月初才会变成新的成虫。n我们要求的是第 n 个月月初的成虫数量还是第 n 个月月末的一般递推题的数组下标都表示“第 i 个月初”所以第 n 个月初的数量就是答案。很多初学者会把题目理解成“每对成虫过 x 个月产一次卵”然后写出来的递推式完全不一样。实际上按一本通这道题的常规题意应该理解成“过 x 个月后每个月都产 y 对卵”。这也直接决定了后面的递推式为什么是那个样子。1.2 用一个月一个月的方式把“虫生”捋清楚我第一次做这题时是拿一张草稿纸把时间轴一段一段画出来的。假设 x2y1z3那么时间线上的事件大概是这样的第 0 个月有 1 对成虫年龄为 0 个月。第 1 个月成虫年龄变成 1 个月还没到 x2所以不产卵。第 2 个月成虫年龄变成 2 个月满足“过 2 个月”的条件于是第一次产下 1 对卵。第 3 个月这对成虫继续产 1 对卵。同时第 2 个月产下的卵还没有满 3 个月所以要等到第 5 个月才变成虫。第 4 个月这对成虫继续产 1 对卵第 2 个月产的卵依然在孵化中。第 5 个月第 2 个月产的卵满 3 个月变成新的 1 对成虫同时老成虫继续产 1 对卵。这样捋过一遍之后就会发现整个系统里有两种“延迟”成虫产卵要延迟 x 个月卵变成虫要延迟 z 个月。如果只用一维数组存“每个月成虫总数”你根本不知道这个月新增的成虫是从哪一批卵来的也不知道这个月该由哪一批成虫来产卵。所以必须分开记录。2. 两个数组互相接力的递推式是怎么来的2.1 状态设计adult[i] 和 egg[i]这道题的核心状态就两个adult[i]第 i 个月月初的成虫对数。egg[i]第 i 个月月初新产下的卵对数。这里“新产下”三个字很重要。egg[i] 不是“第 i 个月正在孵化的所有卵”而是“第 i 个月这个月刚产下来的那批卵”。如果你想问“哪些卵会在第 i 个月变成成虫”答案是 egg[i-z]也就是第 i-z 个月产下的那批卵因为它们刚好经过了 z 个月。初始条件也很好定adult[0] 1因为一开始就有一对成虫。egg[0] 0因为第 0 个月没有产卵。下标从 0 开始这是很多新手不适应的点。但只要你把“第 0 个月有一对成虫”作为起点后面所有递推式都会变得很自然。2.2 两个方程是怎么推出来的第一个方程是“产卵方程”。第 i 个月月初谁有资格产卵答案是第 i-x 个月月初就已经存在的那些成虫。因为“过 x 个月”的意思就是从这个月往回数 x 个月那个月已有的成虫到了第 i 个月刚好满 x 个月所以开始产卵。因此egg[i] adult[i-x] * y注意这里用的是 adult[i-x]不是 adult[i-x-1]。这个下标差一位是最容易错的地方。把初始成虫放在第 0 个月它到第 x 个月第一次产卵那么第 x 个月对应的 i-x 正好是 0取到的就是 adult[0] 1。如果你用 adult[i-x-1]在第 x 个月就会取到 adult[-1]明显不对。第二个方程是“成虫方程”。第 i 个月月初的成虫数应该等于第 i-1 个月月初已有的成虫数再加上这个月刚刚从卵变成虫的数量。刚刚变成虫的是 egg[i-z]所以adult[i] adult[i-1] egg[i-z]这两个方程是互相依赖的。adult[i] 的更新依赖 egg[i-z]egg[i] 的更新依赖 adult[i-x]。它们用的都是更早月份的数据所以在循环 i 从 1 到 n 递增时先算谁都不会出错。我自己习惯先算 egg[i]再算 adult[i]这样逻辑读起来更顺。2.3 为什么不建议用递归或者“模拟每一对虫”很多新手第一反应是写一个函数递归地去算“第 n 个月有多少成虫”。但递归在这里会有严重的重复计算问题因为 adult[i] 会被很多更晚的状态反复引用指数级别地爆炸。就算你用记忆化也不如直接递推直观。模拟每一对虫子的生命周期同样不可行。成虫数量是指数增长的n 稍微大一点个体数量就会多到没法枚举。递推做法的好处是时间复杂度只有 O(n)空间复杂度也是 O(n)完全不用担心这个问题。还有一点值得说这道题虽然可以只用滚动数组优化空间但竞赛里真没必要。开两个一维数组每个下标对应一个月份逻辑最清晰。等以后再碰到状态更多的题目再考虑滚动数组也不迟。3. 参考实现从公式到能跑的代码3.1 把递推式翻译成代码时的细节写代码之前先想好几个边界情况如果当前月份 i 小于 x说明还没有成虫满足“过 x 个月”的条件egg[i] 应该保持 0。如果当前月份 i 小于 z说明还没有任何卵长成成虫adult[i] 应该直接继承 adult[i-1]。数组下标不能越界所以 ix 和 iz 的判断一定要有。我建议数组用 vector 而不是写死长度。因为不同 OJ 的 n 范围可能不一样写死 55 虽然能过常见版本但用 vector 更稳。你可以先读入 n然后开长度为 n1 的数组表示第 0 到第 n 个月。3.2 C 参考代码#include bits/stdc.h using namespace std; int main() { int x, y, z, n; cin x y z n; vectorlong long adult(n 1, 0); vectorlong long egg(n 1, 0); adult[0] 1; for (int i 1; i n; i) { if (i x) { egg[i] adult[i - x] * y; } if (i z) { adult[i] adult[i - 1] egg[i - z]; } else { adult[i] adult[i - 1]; } } cout adult[n] \n; return 0; }这段代码里最需要注意的是 long long。即使 y 很小昆虫数量也会快速膨胀int 根本扛不住。后面我会专门说数据范围的问题。3.3 手动验算一组数据为了确认递推式没写错我通常会在草稿纸上手算一组小数据。比如输入x 1y 2z 1n 8意思是一对成虫过 1 个月后开始产卵每个月产 2 对卵卵过 1 个月变成成虫。手算结果如下表月份 iegg[i] 当月新产卵adult[i] 当月成虫001121223365410115222164243786858170171这个表可以这样验证第 1 个月初始成虫满 1 个月开始产 2 对卵但卵还没变成虫所以成虫数还是 1。第 2 个月第 1 个月产的 2 对卵变成成虫加上原来的 1 对一共 3 对。此时这 3 对成虫都是“过 1 个月”的产卵状态因为第 0 月那对已经成年第 2 月新增的那 2 对也要从第 2 月往后数 1 个月所以第 2 个月产卵数是 adult[1] * 2 2对应 egg[2]2。后面都是同样的逻辑。如果代码输出是 171那这组数据就说明递推式在时间轴上的对应关系没问题。我建议读者拿到任何一组测试数据都先手算到 n3 或 n4再和代码输出比较这是调这种递推题最有效的方法。4. 我见过最多的几个坑越界、爆 int 和错位4.1 数据范围与 long long 问题昆虫繁殖这类递推题的答案增长速度非常快这是初学者最容易忽略的。哪怕 y1z1成虫数量也会像斐波那契数列一样往上冲到 n50 时早就超过 int 上限了。如果 y 再大一点比如 y10一个月新增的卵数量会比前一月所有成虫总数还多很快就能到十亿甚至百亿级别。所以代码里一定要用 long long。我见过不少同学在本地用 int 跑小数据没事一提交就 Wrong Answer排查半天才发现是乘法溢出。这种错误非常隐蔽因为不会直接报运行时错误只是输出一个明显不对的负数或乱值。如果你担心 long long 还不够可以看题目给的 n 范围。一本通原题里 n 通常不会大到需要用高精度但在其他变体题里如果 n 超过 60我建议直接用 Python 写高精度或者上大数模板别在 C 里硬算。4.2 下标越界和循环边界最常见的运行时错误就是数组越界。很多人知道公式是 egg[i] adult[i-x] * y却忘了 i 比较小时 i-x 是负数。在 C 里访问负数下标可能不会立刻崩溃但读到的值完全随机导致结果莫名其妙。解决方式就是我在参考代码里写的那样先判断 if (i x)再执行 egg[i] 的更新。同理adult[i] 的更新也要先判断 if (i z)。还有一种边界情况是 n 小于 z。比如 x2z5n3整个过程中没有任何卵能变成成虫所以答案应该一直是 1。如果没有 else adult[i]adult[i-1] 这句话adult[3] 可能是一个未初始化的值输出就会出错。这里一定要保证每个月份 adult[i] 都有确定值。4.3 三种典型的“理解错位”和排查方法我在帮学弟学妹看代码时发现这道题最容易出三种错第一种是把 x 和 z 搞反。产卵延迟和卵孵化延迟是两个不同的延迟一旦写反结果会以完全不同的速度增长。判断方法是自己手算一个小数据如果 xz那么结果就很好算如果 x 和 z 不同你手算两组值对比一下就能看出自己的代码是不是把两个参数弄混了。第二种是 egg[i] 存成了“累计卵数”。有的人会把 egg[i] 写成 egg[i] egg[i-1] adult[i-x] * y然后 adult[i] adult[i-1] egg[i-z]。这样看上去好像很有道理但实际会把历史所有卵都算进来导致成年数量爆炸式增长。要记住 egg[i] 是当月新产卵不是卵的总存量。真正需要的是“延迟 z 个月的某一批卵”所以直接用 egg[i-z] 就行。第三种是初始下标平移错误。有人把 adult[1] 1 作为初始状态然后递推式也跟着改最后发现 n 个月和 n 个月的答案对不上。我建议统一从 adult[0] 1 开始因为题面说“开始只有一对成虫”这个“开始”就是第 0 个月。排查时不要盯着代码干看。拿笔手算一组 n3 或 n4 的数据把 egg[i] 和 adult[i] 两行都写出来再和代码打印的中间结果对比。只要你的手算值是可信的很快就能定位是哪个公式、哪个下标出了问题。5. 从昆虫繁殖延伸这类递推题还能怎么变形5.1 变体一成虫会死亡昆虫繁殖的经典版本默认成虫不会死所以 adult[i] 只需要在 adult[i-1] 的基础上加新增成虫。如果题目改成“每对成虫只能活 p 个月”那递推式就要变成adult[i] adult[i-1] egg[i-z] - dead[i]dead[i] 表示第 i 个月死掉的成虫数量。要算 dead[i]你必须知道每批“新变成成虫”的数量也就是 newAdult[i] egg[i-z]。如果成虫从变成成虫那天起 p 个月后死亡那么 dead[i] newAdult[i-p]。如果还要考虑初始成虫的寿命就要单独把 adult[0] 剔除出去。这就是“斐波那契兔子问题”的升级版。核心思路仍然不变先找到延迟量再为延迟量单独维护状态。成年人每月数量、新产卵数量、死亡数量分开存就不会乱。5.2 变体二每过 x 个月才产一次卵我前面强调过这道题的通常理解是“过 x 个月后每个月都产”。但有些题目会明确说“每对成虫每隔 x 个月产一次卵”那就完全不一样了。这种情况下不能再用 egg[i] adult[i-x] * y因为不是每个月都在产而是每隔 x 个月产一次。这时候你需要给每对成虫维护“距离下一次产卵还差几个月”或者维护“上次产卵的月份”。如果只给一个全局数组很难描述清楚不同批次成虫不同的产卵周期。更常见的做法是改成模拟每个批次的产卵时间或者把产卵事件看作另一个延迟队列。碰到这种变体一定要先读清楚题面的“每个月初”“每过”“每隔”这几个词。5.3 这类递推题的通法画时间轴再写方程刷过几道一本通的递推题之后你会发现它们都有类似结构某个事件在未来某个月才产生结果于是当前月的状态要由“过去某个月”的状态推过来。昆虫繁殖里的 x 和 z 就是两个延迟参数。我现在的习惯是拿到题先做三件事把第 0 个月的初始状态写在纸上。把“某个月发生了什么事件”按时间轴列出来标出产卵月、孵化月。用两三个月的例子手算一遍确定下标关系再开始写代码。大多数递推题出错不是公式不会而是下标没有敲定。比如“过 x 个月”到底对应 i-x 还是 i-x-1手算一次就能看出来。这个方法比查任何题解都可靠。最后再说一点我个人的经验我第一次做这道题时把 i-x 写成了 i-x-1样例能过但换一组数据就废了。后来我给学弟学妹讲这道题时都会强调一句话——先把第 0 个月当成坐标原点所有“过几个月”的延迟都从这个原点开始数下标就不会偏。手算一张小表拿着表去对代码中间结果比什么都管用。