递推算法（二）：计数递推，按最后一步分类
本文是优编程公众号「信息学竞赛重难点算法数据结构专题」第三节「递推算法」的第 2 篇，本节共 5 篇。本篇讲计数递推的建式方法和三种常见处理：用前缀和计算连续项之和、用终止状态处理边界、用高精度输出完整答案，例题是台阶问题、GESP 六级游戏和数楼梯。适合备战 GESP 五、六级和 CSP-J 的同学。
一、本篇导读递推是用数列前面若干项计算后面一项的方法。写一道递推题要先确定三要素：状态（f[i]表示什么）、递推式（f[i]由哪些更小的状态合成）、初始条件与边界（开头几项的值，下标何时越界）。计数题里「什么都不做」通常算 1 种方案，所以初值常为 。
本节第 1 篇的下楼梯（GESP 六级样题）每步只能走 1、2、3 级，递推式 只有三项。本篇处理三种更一般的情况：
1. 每步可走 级，递推式右边是 项的和，逐项相加代价为 。
2. 游戏在数值小于等于某个界时结束，状态「越过边界」时如何计数。
3. 答案超过 long long，题目又要求完整输出。
计数递推的建式依据是加法原理：把全部方案按某个特征分成若干类，各类互不重叠、合起来覆盖全部方案，总数等于各类方案数之和。
最常用的分类特征是「最后一步做了什么」。以台阶问题为例，到达第 级的最后一步可能跨 1 级、2 级、……、级。跨 级的那一类方案，去掉最后一步后恰好是「到达第 级」的全部方案，所以这一类有 种。各类相加得到递推式。
分类是否正确，检查两点：不同类之间不会出现同一个方案（不重）；每个方案都属于某一类（不漏）。
也可以按「第一步做了什么」分类，本篇的游戏就是这样：设 f[i]为当前数为 时到游戏结束的方案数，第一步减 或减 ，分成两类。两种分类方式得到的递推式形式相同，区别在于状态的含义是「从起点到 」还是「从 到终点」，要在注释里写清楚。
2.2 连续项之和与前缀和
递推式形如
时，每次逐项相加要 ，总复杂度 。右边是一段下标连续的项之和，可以维护前缀和 ，于是
每项 算出，总复杂度降到 。时说明窗口已经覆盖到 ，直接取 。
这个方法在本节第 5 篇的逆序对数列中还会用到，那里的求和出现在二维递推里。
2.3 取模规则
答案要求对 取模时：
1. 加法和乘法每一步都可以取模，结果不变：。
2. 减法取模后可能得到负数，要写成 (x - y + MOD) % MOD。
3. 两个小于 的数相加，结果小于 。时 ，用 int不会溢出；两个数相乘则可能达到 ，要用 long long。
题目要求输出完整答案、答案又超过 时，用数组按位存储大数：d[0]存个位，d[1]存十位，依次类推，另用一个变量记录位数。加法从低位到高位逐位相加，满十进一，最后若还有进位，位数加 1。输出时从最高位往个位输出。
递推只依赖最近几项时，不必把每一项都存下来，用下标 i % 3轮流使用三个数组即可，这叫滚动存储。
三、真题精讲例 1：台阶问题
题意简述
有 级台阶，每次可以向上迈 级，求到达第 级的方式数，对 取模。，。样例：5 2输出 8。
思路分析
的数据 、，枚举每一步跨几级可以拿到这部分分。枚举的运行次数不少于方案数，方案数随 指数增长，稍大就无法完成。
按最后一步分类，设 f[i]为到达第 级的方式数：
直接按式子写，每项加 次，总共约 次加法取模，本题数据下可以通过。
但这个式子右边是一段连续项之和，用 2.2 节的前缀和可以把每项降到 ：。两种写法在本题数据下都能通过，差别体现在 与 同阶时：若 ，逐项相加约 次，前缀和写法仍是 次。考场上看到递推式右边有一段连续项的和，就应当想到前缀和。
得分要点
1. ：站在地面上算 1 种方式。
2. 时不减，窗口已经覆盖到 。
3. 前缀和相减后要加 MOD再取模，否则会出现负数。
4. 的情况也要正确：此时 恒小于 0，代码自然处理。
usingnamespacestd;
constintMOD =100003;
intn, k;
intf[100005];// f[i] = 到达第 i 级台阶的方案数
ints[100005];// s[i] = f[0] + f[1] + ... + f[i]，前缀和
intmain{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
// 初始条件：站在第 0 级算 1 种方案
f[0] =1;
s[0] =1;
for(inti =1; i <= n; i++) {
// f[i] = f[i-k] + ... + f[i-1]，用前缀和一步算出
f[i] = s[i -1];
// 窗口左端是 i-k，i-k-1 >= 0 时要减掉窗口外的部分
if(i - k -1>=0) f[i] = (f[i] - s[i - k -1] + MOD) % MOD;
s[i] = (s[i -1] + f[i]) % MOD;
}
cout << f[n] <<'\n';
return0;
}复杂度分析
1. 时间复杂度：；逐项相加的写法为 。
2. 空间复杂度：。
算法思考：递推式右边是「一段下标连续的项之和」时，同步维护前缀和，把求和变成两项相减。这个处理与递推式本身无关，可以直接用到任何形如 的递推上。
例 2：游戏题意简述
有四个正整数 。每轮操作可以把 减去 或减去 ，当 时游戏结束。求不同操作序列的个数，对 取模；即使 ，「减 」和「减 」也算不同的操作。。样例：114 51 4 1输出 176。
思路分析
的数据满足 、，答案是 。逐一枚举每一轮的选择也能得到答案，但要走遍全部 个操作序列，时约 个，在 1 秒内很难完成。
本题的状态是「当前的数」。设 f[i]为当前数为 时，到游戏结束共有多少种操作序列。按第一步分类：
1. 若 ，游戏已经结束，只有「不再操作」这 1 种，。
2. 若 ，第一步减 后数变成 ，之后有 种；减 同理。所以 。
可能小于等于 0，这时游戏同样已经结束，方案数为 1。代码中先判断 i - a <= c，成立就直接取 1，不去访问 f[i-a]，这样负下标的问题一并解决。
计算方向：依赖 、，都比 小，所以 从 1 循环到 。
得分要点
1. 时 ，这是「游戏已结束」的终止状态，不是 0。
2. 减完后 （包括变成 0 或负数）都算 1 种，先判断再访问数组，避免负下标。
3. 时两种操作仍算不同，递推式照常把两项相加，不需要特判。
4. 两个小于 的数相加不超过 int上限，先相加再取模即可。
usingnamespacestd;
intn, a, b, c;
intf[200005];// f[i] = 当前数为 i 时，到游戏结束共有多少种操作序列
intmain{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> a >> b >> c;
for(inti =1; i <= n; i++) {
// 边界：i <= c 时游戏已经结束，只有“不再操作”这 1 种
if(i <= c) {
f[i] =1;
continue;
}
// 第一步减 a 或减 b，减完如果 <= c（包括变成 0 或负数）就结束，算 1 种
intx = (i - a <= c) ?1: f[i - a];
inty = (i - b <= c) ?1: f[i - b];
f[i] = (x + y) % MOD;// x、y 都小于 MOD，相加不会超过 int
}
cout << f[n] <<'\n';
return0;
}复杂度分析
1. 时间复杂度：。
2. 空间复杂度：。
算法思考：状态可以是「已经走了多少」，也可以是「还剩多少」。本题用后者，游戏结束条件就是递推的边界，所有越过边界的状态统一记为 1。
例 3：数楼梯题意简述
楼梯有 阶，每步上 1 阶或 2 阶，求走法总数，要求完整输出，。样例：输入 4，输出 5。
思路分析
按最后一步分类：，，。这就是斐波那契数列向后平移一位，。
本题的考点在数据范围。斐波那契数列每项约为前一项的 1.618 倍：
1. long long最大约 ，还能存下，就溢出了，所以 long long只能算到 。的数据 ，用 long long可以拿到这部分分。
2. 时答案有 1045 位，必须用高精度。
高精度的做法见 2.4 节：每个大数用一个数组逐位存储，d[0]为个位。只依赖 、，所以只开 3 个大数，第 项存在第 i % 3个里，算 时读取第 (i-1) % 3和 (i-2) % 3个。
运算量估算：共 次加法，每次处理不超过 1045 位，总计约 次单位运算。若想再快，可以每个数组元素存 4 位十进制数（万进制），运算次数降到约四分之一，输出时除最高位外都要补足 4 位；本题数据下十进制已经足够。
得分要点
1. 先算出答案的位数（约 1045 位），再决定数组大小，本题开 1100。
2. 两数位数不同时，短的那个高位视为 0，代码中用 j < len[p]判断。
3. 最高位有进位时位数要加 1，漏掉会少输出最高位。
4. 输出从最高位到个位；若改用万进制，除最高位外每段都要补足 4 位。
usingnamespacestd;
intn;
intf[3][1100];// 滚动存三个大数，f[t][0] 是个位，f[t][1] 是十位……
intlen[3];// len[t] = 第 t 个大数的位数
intmain{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
// 初始条件：f(1) = 1，f(2) = 2，分别存在下标 1%3 和 2%3
f[1][0] =1; len[1] =1;
f[2][0] =2; len[2] =1;
for(inti =3; i <= n; i++) {
intp = (i -1) %3, q = (i -2) %3, r = i %3;// f(i) = f(i-1) + f(i-2)
intl =max(len[p], len[q]);
intjw =0;// 进位
for(intj =0; j < l; j++) {
intx = jw;
if(j < len[p]) x += f[p][j];
if(j < len[q]) x += f[q][j];
f[r][j] = x %10;
jw = x /10;
}
if(jw >0) {// 最高位还有进位，位数加 1
f[r][l] = jw;
l++;
}
len[r] = l;
}
// 从最高位往个位输出
intt = n %3;
for(intj = len[t] -1; j >=0; j--) cout << f[t][j];
cout <<'\n';
return0;
}复杂度分析
1. 时间复杂度：，为答案位数，约 次单位运算。
2. 空间复杂度：，只滚动保存 3 个大数。
算法思考：递推式本身只有一行，本题的工作量都在「答案存不下」上。拿到题先估算答案大小：超过 long long且不取模，就要准备高精度；递推只依赖最近几项时，用滚动存储控制空间。
四、本篇小结1. 计数递推按最后一步（或第一步）分类建式，分类要不重不漏，每一类去掉这一步后是规模更小的同类问题。
2. 递推式右边是一段连续项之和时，用前缀和把每项的计算降到 ，相减后加模数再取模。
3. 「游戏结束」这类条件对应递推的终止状态，越过边界的状态统一处理，先判断再访问数组。
4. 答案超出 long long又要完整输出时用高精度加法，配合滚动存储节省空间。
下一篇讲递推式的建立与化简。本篇三道题都能按最后一步直接分类，第 3 篇的题目需要多想一步：数的计算的递推式带求和号，要通过相邻两项作差化简成一行；栈要按关键事件把方案切成两段，用乘法原理建式；Hanoi 双塔问题要从移动过程中找出递推关系，再求出通项公式。
优编程，专注 C++ 信息学竞赛赛道。「递推算法」系列下一篇讲解递推式的建立与化简，敬请关注。
——优编程信奥总教练 郑新元
