CF1452D这题我第一次做完之后最大的感受是明明是道计数题答案却直接落到斐波那契数列上而且一旦看穿这一点代码短到让人觉得是不是漏了什么。题目本身来自一场Div.2轮次题面里有一排基站和信号塔塔的覆盖范围要求是奇数最后问总方案数并对 998244353 取模。很多人在赛场上盯着这个题发呆不是不会写递推而是没有把表面问题转换成“把一个长度为 n 的序列切成若干奇数段求和”的模型自然也就想不到答案和斐波那契有关。这篇文章就把从建模到推导、再到各种变式处理的完整思路拆开讲一遍适合刚接触组合计数 DP 的选手也适合想搞明白“为什么又是斐波那契”的老手。1. 题目到底在问什么从信号塔覆盖到奇数段拆分1.1 原始题面和我理解的建模过程原题模拟了一排 n 个位置每个位置可以是普通站点也可以放置信号塔。信号塔的覆盖范围是一段连续的位置并且这个范围的长度必须是奇数。两个塔的覆盖范围不能相交最后要求所有位置都被覆盖。问这样的放置方案有多少种答案对 998244353 取模。赛场上很多人的第一反应是枚举每个塔放在哪、覆盖到哪里这样想就走远了。这道题的关键在于塔的覆盖区间是连续的且互不重叠的从左往右看整条线路被这些区间完全切开中间没有任何空隙因此问题就等价于“把 n 拆分成若干个奇数长度段”。为什么等价你可以把第一个塔看成覆盖最左侧一段第二个塔必须紧挨着第一个塔的右边界继续覆盖以此类推直到所有位置覆盖完。塔本身没有额外的功率、优先级之类的限制所以每一组“长度均为奇数”的有序分段都唯一对应一种合法放置方案。反过来任何一种合法覆盖方案也一定对应这样一组分段。抓住“覆盖长度为奇数”这个约束题面就不再是地理题而是一个纯粹的计数问题。1.2 是“有序拆分”不是“拆分数”很多人在这一步会踩一个概念坑把“拆分”理解成无序整数拆分。比如 n3无序拆分只有两种3 和 111。但在本题里段从左到右是有顺序的“13”和“31”是两种完全不同的覆盖方案。为什么顺序必须保留因为塔的位置不同。n4 时先放一个覆盖长度为 1 的塔再放一个覆盖长度为 3 的塔和先放长度为 3 的塔再放长度为 1 的塔两组塔的坐标完全不同显然是两种方案。如果一开始把模型误建成无序拆分数后面推导出的数列也会变成分区数序列样例都过不了。我见过不少选手在赛场上卡在这一步代码写着写着就变成了整数划分 DP结果越写越复杂。实际上只要确认“从左往右切分顺序天然固定”后面所有递推都有一个坚实的立足点。1.3 小数据先跑一遍建立直觉在推导任何公式之前先把小规模情况枚举一遍是个好习惯。设 f[n] 为长度 n 的覆盖方案数。n所有合法分段f[n]1[1]12[11]13[3], [111]24[13], [31], [1111]35[5], [113], [131], [311], [11111]56略8看到 1, 1, 2, 3, 5, 8基本已经可以猜出答案是斐波那契数列。这个时候再回头构造递推式会轻松很多。先有猜想再去证明比直接对着题意凭空想状态要省力得多这也是我打计数题时一直用的思路。2. 从枚举结果到递推式斐波那契是怎么冒出来的2.1 先写暴力生成器看前几项为了更放心我在本地会先写一个几行的暴力递归把前十几项跑出来确认规律没有在 n 变大后突然改变。def dfs(rem): if rem 0: return 1 total 0 for length in range(1, rem 1, 2): total dfs(rem - length) return total for n in range(1, 16): print(n, dfs(n))输出1 1 2 1 3 2 4 3 5 5 6 8 7 13 8 21 9 34 10 55 ...这段代码当然不能直接提交指数级复杂度n 稍大就爆炸。但用于验证思路非常值钱。实际比赛中我经常先写这种暴力跑出前十几项再和熟知的数列比对。如果发现是斐波那契后面的推导就有方向了。2.2 递推式的直观推导按第一段长度分类现在用正向递推推导这个规律。设 f[n] 为长度 n 的覆盖方案数。考虑最左边那个奇数段的长度它可能是 1、3、5、7……也就是所有不超过 n 的正奇数。如果最左边长度是 1剩余 n-1 的覆盖方案数是 f[n-1] 如果最左边长度是 3剩余 n-3 的覆盖方案数是 f[n-3] 如果最左边长度是 5剩余 n-5 的覆盖方案数是 f[n-5]以此类推。所以f[n] f[n-1] f[n-3] f[n-5] ...这个式子本身不是二项递推而是很多项相加直接算复杂度不好看。但注意 f[n-2] 也有同样的展开f[n-2] f[n-3] f[n-5] f[n-7] ...把第二行代入第一行就会发现 f[n] 的右边除 f[n-1] 之外那一长串正好就是 f[n-2]。于是得到f[n] f[n-1] f[n-2]这就是标准的斐波那契递推。整个过程其实就是一个“错位相消”的思想把多步依赖消成两步依赖这也是很多看似复杂的递推最终简化成二阶递推的常见原因。2.3 边界 f[0]1 的直觉空段也是一种方案递推式出来了还有一个边界要处理。当剩余长度正好被第一段切完时比如 n3 时最左边直接取 3剩余长度为 0我们需要把 f[0] 定义成 1代表“空覆盖也是一种合法完成状态”。于是f[0] 1空状态什么都不切也算一种完成方式f[1] f[0] 1长度 1 只能是 [1]f[2] f[1] f[0] 1 1 2 吗不是所以这里要特别小心。重新检查f[2] f[1] f[0] 1 1 2 看起来会和枚举冲突。问题出在 f[2] 展开时最左边奇数段可以取 1 或 3但不能取 3因为长度不够。而 f[0]1 对应“最左边取整个长度 2”的情况但长度 2 不是奇数所以这个项不应该存在。换句话说f[n] f[n-1] f[n-3] ... 中“最左边取整个 n”这一项只有当 n 是奇数时才存在对应 f[0]1。对于 n2n 是偶数不存在“整段长度 2”这一项。那为什么前面的错位代入又成立呢因为 f[n-2] f[n-3] f[n-5] ... 恰好固定包含了 f[n-3] 以及更小的奇数项没有包含“n-2 整段”这一项因为要吸收进 f[n] 的也只有从 f[n-3] 往后的那些项不涉及 f[n-2] 整段。所以这个代入对于任意 n≥2 都对但计算 f[2] 时仍要回归定义f[2] f[1] f[0] 里 f[0] 对应的是偶数 2 的整段不合法所以这步递推式在 n2 时其实不适用。更稳的做法是直接约定 f[1]1, f[2]1然后从 i3 开始用 f[i]f[i-1]f[i-2]。这样得到的序列是 1, 1, 2, 3, 5, 8, 13, ...完全对应枚举表。理解 f[0]1 作为空状态是重要的但实际编码时为了避免上述边界陷阱我习惯显式初始化 f[0]1, f[1]1然后从 2 开始迭代同时从小样例验证 f[2]1一旦发现 f[2] 算出 2 就要回头检查是因为公式边界没处理好。3. 代码这样写几个容易翻车的小细节3.1 O(n) 递推的标准写法n 最大是 2e5O(n) 的递推完全够用。这里给出最直接的滚动写法#include bits/stdc.h using namespace std; int main() { const long long MOD 998244353; int n; cin n; long long f0 1; // f[0] long long f1 1; // f[1] if (n 1) { cout 1 \n; return 0; } for (int i 2; i n; i) { long long nxt (f0 f1) % MOD; f0 f1; f1 nxt; } cout f1 \n; return 0; }用数组版本也完全没问题2e5 的 long long 数组才 1.6MB内存无所谓。滚动变量主要图个省心不用维护下标也能顺手规避一部分只会在下标上出现的低级错误。3.2 索引与边界从 1 开始还是从 2 开始关于下标真的值得单独拿出来说。这个题最容易写错的点就是 f[2]。很多人推完递推式后直接写 f[2]f[1]f[0]2然后输出 n2 时答案变成 2样例测不出来交上去就 WA。原因前面已经说过了f[n] f[n-1] f[n-3] ... 中如果 n 是偶数就不会出现“整段 n”这一项所以 f[2] 只能来自 f[1]答案是 1。而用错位代入得到的 f[2]f[1]f[0] 把不存在的“整段 2”也算进去了。所以实际编码最保险的起点是f[0] 1作为空状态f[1] 1从 i2 开始用 f[i] (f[i-1] f[i-2]) % MOD并单独验证 f[2] 1。你可能会看到网上一些题解说答案是 fib[n1]那是它们把斐波那契的起点定义成了 fib[0]0, fib[1]1。两种定义只差一个下标位移千万别混。我自己的核对手段是写完后用 n5 和 n6 各测一次要求输出 5 和 8。这两个数能对上基本就不会错位了。3.3 取模细节与防溢出MOD 998244353 是一个常见的质数模数。本题只涉及加法如果只从 int 的角度看两个 long long 相加也不会爆 long long但我依然建议全程使用 long long。竞赛里很多时候会把加法改成乘法比如后面要算组合数或者矩阵乘法int 就会非常危险。统一用 long long 可以少动很多脑筋。另外每次加法后立刻取模不要等累加完了再取。循环中如果连续加若干次不取模虽然本题数据量下不一定溢出但这是一个非常坏的习惯遇到更复杂的转移条件时很容易出事。Python 选手则要注意别写递归2e5 的递归深度会直接爆栈列表递推就完事了。4. n 范围变大之后矩阵快速幂与生成函数的两个延伸视角4.1 当 n 达到 1e18 时怎么办如果哪天这题的 n 被加强了变成 1e18O(n) 就不可能了。斐波那契数列的经典加速方式是矩阵快速幂。我们用这样的状态转移M [[1, 1], [1, 0]]那么[F_{k1}, F_k]^T M * [F_k, F_{k-1}]^T要求 F_n就计算 M^(n-1) 再乘以初始向量。注意我们的下标定义和教材里的 F00, F11 不一样我这里用的是 F01, F11写矩阵时要格外注意最终向量的组合方式。using ll long long; const ll MOD 998244353; const int SZ 2; struct Mat { ll a[SZ][SZ]; Mat(bool unit false) { memset(a, 0, sizeof(a)); if (unit) { a[0][0] a[1][1] 1; } } }; Mat mul(const Mat x, const Mat y) { Mat z; for (int i 0; i SZ; i) for (int k 0; k SZ; k) { if (x.a[i][k] 0) continue; for (int j 0; j SZ; j) z.a[i][j] (z.a[i][j] x.a[i][k] * y.a[k][j]) % MOD; } return z; } ll fib(ll n) { if (n 1) return 1; Mat base; base.a[0][0] 1; base.a[0][1] 1; base.a[1][0] 1; base.a[1][1] 0; Mat res(true); ll e n - 1; while (e) { if (e 1) res mul(res, base); base mul(base, base); e 1; } // res * [F1, F0]^T而 F0F11 return (res.a[0][0] res.a[0][1]) % MOD; }自测方式还是一样fib(5) 返回 5fib(6) 返回 8fib(1) 返回 1fib(0) 返回 1。把这四个值先跑对再上大样例。4.2 从递推到生成函数为什么系数恰好是斐波那契如果只是想 AC前面的内容已经够了。但如果你想彻底搞清楚“为什么是斐波那契”生成函数是一个更上层的视角。设方案数列为 a[n]定义生成函数 G(x) Σ a[n] x^n。每个奇数长度段对应一个组件组件集合是 {1, 3, 5, ...}它的生成函数是A(x) x x^3 x^5 ... x / (1 - x^2)多个组件任意拼接对应的就是G(x) 1 A(x) A(x)^2 A(x)^3 ... 1 / (1 - A(x))代入 A(x)G(x) 1 / (1 - x / (1 - x^2)) (1 - x^2) / (1 - x - x^2)分母 1 - x - x^2 是经典斐波那契数列的生成函数分母乘上 (1 - x^2) 只是做了一个轻微的下标修正最终系数正好是 a[n] F[n]。生成函数的价值在于当你把“奇数段”这个条件换成别的集合时不需要重新想状态转移只需要替换 A(x) 然后展开系数。很多看上去毫无头绪的计数题用生成函数都能直接推通项。4.3 大范围时别忘了特判矩阵快速幂写多了最容易栽的两个地方一是 n0 或 n1 没特判矩阵乘完返回错误结果二是矩阵乘法循环写错尤其是把外层 i、内层 j、中间 k 的循环顺序搞混导致算出来的矩阵根本不是那回事。我的习惯是矩阵快速幂函数开头就做 if (n 1) return 1 的特判并且每写完一次就用小数据回归一遍。因为矩阵代码本身抽象一旦出错不好肉眼排查提前用 1、2、5、6 这几个小值守住最后接大数据时才不会慌。5. 变式训练改一个条件解法怎么跟着变5.1 改成“只能拆成偶数段”这题的题眼是“奇数”如果题目改成“每段长度必须是偶数”数列会变成另一个简单序列。设 g[n] 为偶数长度段的有序拆分方案数ng[n]21426488规律是 g[2]1, g[4]2, g[6]4, g[8]8也就是 2^(n/2 - 1)。这个结论也可以用隔板法理解把每个偶数段统一看成若干个“2”的单位整条长度 n 被切成 n/2 个单位单位之间的空隙有 n/2 - 1 个每个空隙可以切或不切一共 2^(n/2 - 1) 种方案。对比一下就能发现奇数段对应二阶递推斐波那契偶数段对应一阶递推幂函数。差别来自“单位长度能不能单独成块”这也解释了为什么奇数约束会产生二阶依赖。5.2 限制最大段长 L 时怎么递推如果额外要求每段长度不能超过某个上限 L前面的 f[n] f[n-1] f[n-2] 就不再成立了。这种情况下老老实实回到原始定义f[n] Σ f[n-l]其中 l 取所有不超过 L 的正奇数直接这样做是 O(nL)当 n 和 L 都到 2e5 就会超时。优化套路也很固定用前缀和快速求区间和。具体来说维护奇偶两个前缀和数组因为每次加的奇数 l 只跟 f 的奇偶下标有关。每次计算 f[n] 时用前缀和求一段连续奇数下标 f 值的和就能在 O(1) 时间内完成转移。这种“枚举最后一刀或第一段 前缀和优化”的组合在分段计数题里几乎是标配值得单独练一练。5.3 如果还要求“恰好分成 k 段”有些变式题会限定“恰好拆成 k 个奇数段”。这种情况甚至可以不用 DP直接用组合数给出通项。每个奇数段可以写成 1 2a_j其中 a_j ≥ 0。那么n k 2 * (a_1 a_2 ... a_k)所以 a_1 ... a_k (n - k) / 2。为了保证整数n 和 k 必须同奇偶并且 n ≥ k。接下来就是把 (n-k)/2 个“2 单位”分给 k 个位置允许空位这是一个经典隔板法答案是C((nk)/2 - 1, k - 1)这个通项可以用来反推 DP 是否正确。很多变式题表面上是在考 DP其实先写出组合数通项再回来验证转移往往能更快发现问题。最后说点我的实际体验我在做这题的时候没有一上来就推导生成函数而是先写了个暴力枚举看到 1, 1, 2, 3, 5, 8 之后花了五分钟写好递推就交了。后来复盘才把生成函数和矩阵快速幂补上。现在回头看这类题的通用做法其实很清晰小数据打表 - 识别数列 - 反推递推 - 按数据范围选优化。如果一上来就硬想状态定义和转移方程很容易陷进去。另外几乎所有分段覆盖类计数题都可以先定义好“空状态” f[0]1这个边界一立许多递推都会自己理顺。遇到疑似斐波那契规律时也别忘了用小样例验证下标位移这是最隐蔽也最不值当的丢分点。希望这篇对你有用下次在计数题里再看到斐波那契冒头你知道它大概率就藏在递推的错位相消里。 
长河君 · 2026/10/14 15:12:24 · 阅读 1.2k CF1452D解析：从组合计数到斐波那契递推的建模与优化
CF1452D这题我第一次做完之后最大的感受是明明是道计数题答案却直接落到斐波那契数列上而且一旦看穿这一点代码短到让人觉得是不是漏了什么。题目本身来自一场Div.2轮次题面里有一排基站和信号塔塔的覆盖范围要求是奇数最后问总方案数并对 998244353 取模。很多人在赛场上盯着这个题发呆不是不会写递推而是没有把表面问题转换成“把一个长度为 n 的序列切成若干奇数段求和”的模型自然也就想不到答案和斐波那契有关。这篇文章就把从建模到推导、再到各种变式处理的完整思路拆开讲一遍适合刚接触组合计数 DP 的选手也适合想搞明白“为什么又是斐波那契”的老手。1. 题目到底在问什么从信号塔覆盖到奇数段拆分1.1 原始题面和我理解的建模过程原题模拟了一排 n 个位置每个位置可以是普通站点也可以放置信号塔。信号塔的覆盖范围是一段连续的位置并且这个范围的长度必须是奇数。两个塔的覆盖范围不能相交最后要求所有位置都被覆盖。问这样的放置方案有多少种答案对 998244353 取模。赛场上很多人的第一反应是枚举每个塔放在哪、覆盖到哪里这样想就走远了。这道题的关键在于塔的覆盖区间是连续的且互不重叠的从左往右看整条线路被这些区间完全切开中间没有任何空隙因此问题就等价于“把 n 拆分成若干个奇数长度段”。为什么等价你可以把第一个塔看成覆盖最左侧一段第二个塔必须紧挨着第一个塔的右边界继续覆盖以此类推直到所有位置覆盖完。塔本身没有额外的功率、优先级之类的限制所以每一组“长度均为奇数”的有序分段都唯一对应一种合法放置方案。反过来任何一种合法覆盖方案也一定对应这样一组分段。抓住“覆盖长度为奇数”这个约束题面就不再是地理题而是一个纯粹的计数问题。1.2 是“有序拆分”不是“拆分数”很多人在这一步会踩一个概念坑把“拆分”理解成无序整数拆分。比如 n3无序拆分只有两种3 和 111。但在本题里段从左到右是有顺序的“13”和“31”是两种完全不同的覆盖方案。为什么顺序必须保留因为塔的位置不同。n4 时先放一个覆盖长度为 1 的塔再放一个覆盖长度为 3 的塔和先放长度为 3 的塔再放长度为 1 的塔两组塔的坐标完全不同显然是两种方案。如果一开始把模型误建成无序拆分数后面推导出的数列也会变成分区数序列样例都过不了。我见过不少选手在赛场上卡在这一步代码写着写着就变成了整数划分 DP结果越写越复杂。实际上只要确认“从左往右切分顺序天然固定”后面所有递推都有一个坚实的立足点。1.3 小数据先跑一遍建立直觉在推导任何公式之前先把小规模情况枚举一遍是个好习惯。设 f[n] 为长度 n 的覆盖方案数。n所有合法分段f[n]1[1]12[11]13[3], [111]24[13], [31], [1111]35[5], [113], [131], [311], [11111]56略8看到 1, 1, 2, 3, 5, 8基本已经可以猜出答案是斐波那契数列。这个时候再回头构造递推式会轻松很多。先有猜想再去证明比直接对着题意凭空想状态要省力得多这也是我打计数题时一直用的思路。2. 从枚举结果到递推式斐波那契是怎么冒出来的2.1 先写暴力生成器看前几项为了更放心我在本地会先写一个几行的暴力递归把前十几项跑出来确认规律没有在 n 变大后突然改变。def dfs(rem): if rem 0: return 1 total 0 for length in range(1, rem 1, 2): total dfs(rem - length) return total for n in range(1, 16): print(n, dfs(n))输出1 1 2 1 3 2 4 3 5 5 6 8 7 13 8 21 9 34 10 55 ...这段代码当然不能直接提交指数级复杂度n 稍大就爆炸。但用于验证思路非常值钱。实际比赛中我经常先写这种暴力跑出前十几项再和熟知的数列比对。如果发现是斐波那契后面的推导就有方向了。2.2 递推式的直观推导按第一段长度分类现在用正向递推推导这个规律。设 f[n] 为长度 n 的覆盖方案数。考虑最左边那个奇数段的长度它可能是 1、3、5、7……也就是所有不超过 n 的正奇数。如果最左边长度是 1剩余 n-1 的覆盖方案数是 f[n-1] 如果最左边长度是 3剩余 n-3 的覆盖方案数是 f[n-3] 如果最左边长度是 5剩余 n-5 的覆盖方案数是 f[n-5]以此类推。所以f[n] f[n-1] f[n-3] f[n-5] ...这个式子本身不是二项递推而是很多项相加直接算复杂度不好看。但注意 f[n-2] 也有同样的展开f[n-2] f[n-3] f[n-5] f[n-7] ...把第二行代入第一行就会发现 f[n] 的右边除 f[n-1] 之外那一长串正好就是 f[n-2]。于是得到f[n] f[n-1] f[n-2]这就是标准的斐波那契递推。整个过程其实就是一个“错位相消”的思想把多步依赖消成两步依赖这也是很多看似复杂的递推最终简化成二阶递推的常见原因。2.3 边界 f[0]1 的直觉空段也是一种方案递推式出来了还有一个边界要处理。当剩余长度正好被第一段切完时比如 n3 时最左边直接取 3剩余长度为 0我们需要把 f[0] 定义成 1代表“空覆盖也是一种合法完成状态”。于是f[0] 1空状态什么都不切也算一种完成方式f[1] f[0] 1长度 1 只能是 [1]f[2] f[1] f[0] 1 1 2 吗不是所以这里要特别小心。重新检查f[2] f[1] f[0] 1 1 2 看起来会和枚举冲突。问题出在 f[2] 展开时最左边奇数段可以取 1 或 3但不能取 3因为长度不够。而 f[0]1 对应“最左边取整个长度 2”的情况但长度 2 不是奇数所以这个项不应该存在。换句话说f[n] f[n-1] f[n-3] ... 中“最左边取整个 n”这一项只有当 n 是奇数时才存在对应 f[0]1。对于 n2n 是偶数不存在“整段长度 2”这一项。那为什么前面的错位代入又成立呢因为 f[n-2] f[n-3] f[n-5] ... 恰好固定包含了 f[n-3] 以及更小的奇数项没有包含“n-2 整段”这一项因为要吸收进 f[n] 的也只有从 f[n-3] 往后的那些项不涉及 f[n-2] 整段。所以这个代入对于任意 n≥2 都对但计算 f[2] 时仍要回归定义f[2] f[1] f[0] 里 f[0] 对应的是偶数 2 的整段不合法所以这步递推式在 n2 时其实不适用。更稳的做法是直接约定 f[1]1, f[2]1然后从 i3 开始用 f[i]f[i-1]f[i-2]。这样得到的序列是 1, 1, 2, 3, 5, 8, 13, ...完全对应枚举表。理解 f[0]1 作为空状态是重要的但实际编码时为了避免上述边界陷阱我习惯显式初始化 f[0]1, f[1]1然后从 2 开始迭代同时从小样例验证 f[2]1一旦发现 f[2] 算出 2 就要回头检查是因为公式边界没处理好。3. 代码这样写几个容易翻车的小细节3.1 O(n) 递推的标准写法n 最大是 2e5O(n) 的递推完全够用。这里给出最直接的滚动写法#include bits/stdc.h using namespace std; int main() { const long long MOD 998244353; int n; cin n; long long f0 1; // f[0] long long f1 1; // f[1] if (n 1) { cout 1 \n; return 0; } for (int i 2; i n; i) { long long nxt (f0 f1) % MOD; f0 f1; f1 nxt; } cout f1 \n; return 0; }用数组版本也完全没问题2e5 的 long long 数组才 1.6MB内存无所谓。滚动变量主要图个省心不用维护下标也能顺手规避一部分只会在下标上出现的低级错误。3.2 索引与边界从 1 开始还是从 2 开始关于下标真的值得单独拿出来说。这个题最容易写错的点就是 f[2]。很多人推完递推式后直接写 f[2]f[1]f[0]2然后输出 n2 时答案变成 2样例测不出来交上去就 WA。原因前面已经说过了f[n] f[n-1] f[n-3] ... 中如果 n 是偶数就不会出现“整段 n”这一项所以 f[2] 只能来自 f[1]答案是 1。而用错位代入得到的 f[2]f[1]f[0] 把不存在的“整段 2”也算进去了。所以实际编码最保险的起点是f[0] 1作为空状态f[1] 1从 i2 开始用 f[i] (f[i-1] f[i-2]) % MOD并单独验证 f[2] 1。你可能会看到网上一些题解说答案是 fib[n1]那是它们把斐波那契的起点定义成了 fib[0]0, fib[1]1。两种定义只差一个下标位移千万别混。我自己的核对手段是写完后用 n5 和 n6 各测一次要求输出 5 和 8。这两个数能对上基本就不会错位了。3.3 取模细节与防溢出MOD 998244353 是一个常见的质数模数。本题只涉及加法如果只从 int 的角度看两个 long long 相加也不会爆 long long但我依然建议全程使用 long long。竞赛里很多时候会把加法改成乘法比如后面要算组合数或者矩阵乘法int 就会非常危险。统一用 long long 可以少动很多脑筋。另外每次加法后立刻取模不要等累加完了再取。循环中如果连续加若干次不取模虽然本题数据量下不一定溢出但这是一个非常坏的习惯遇到更复杂的转移条件时很容易出事。Python 选手则要注意别写递归2e5 的递归深度会直接爆栈列表递推就完事了。4. n 范围变大之后矩阵快速幂与生成函数的两个延伸视角4.1 当 n 达到 1e18 时怎么办如果哪天这题的 n 被加强了变成 1e18O(n) 就不可能了。斐波那契数列的经典加速方式是矩阵快速幂。我们用这样的状态转移M [[1, 1], [1, 0]]那么[F_{k1}, F_k]^T M * [F_k, F_{k-1}]^T要求 F_n就计算 M^(n-1) 再乘以初始向量。注意我们的下标定义和教材里的 F00, F11 不一样我这里用的是 F01, F11写矩阵时要格外注意最终向量的组合方式。using ll long long; const ll MOD 998244353; const int SZ 2; struct Mat { ll a[SZ][SZ]; Mat(bool unit false) { memset(a, 0, sizeof(a)); if (unit) { a[0][0] a[1][1] 1; } } }; Mat mul(const Mat x, const Mat y) { Mat z; for (int i 0; i SZ; i) for (int k 0; k SZ; k) { if (x.a[i][k] 0) continue; for (int j 0; j SZ; j) z.a[i][j] (z.a[i][j] x.a[i][k] * y.a[k][j]) % MOD; } return z; } ll fib(ll n) { if (n 1) return 1; Mat base; base.a[0][0] 1; base.a[0][1] 1; base.a[1][0] 1; base.a[1][1] 0; Mat res(true); ll e n - 1; while (e) { if (e 1) res mul(res, base); base mul(base, base); e 1; } // res * [F1, F0]^T而 F0F11 return (res.a[0][0] res.a[0][1]) % MOD; }自测方式还是一样fib(5) 返回 5fib(6) 返回 8fib(1) 返回 1fib(0) 返回 1。把这四个值先跑对再上大样例。4.2 从递推到生成函数为什么系数恰好是斐波那契如果只是想 AC前面的内容已经够了。但如果你想彻底搞清楚“为什么是斐波那契”生成函数是一个更上层的视角。设方案数列为 a[n]定义生成函数 G(x) Σ a[n] x^n。每个奇数长度段对应一个组件组件集合是 {1, 3, 5, ...}它的生成函数是A(x) x x^3 x^5 ... x / (1 - x^2)多个组件任意拼接对应的就是G(x) 1 A(x) A(x)^2 A(x)^3 ... 1 / (1 - A(x))代入 A(x)G(x) 1 / (1 - x / (1 - x^2)) (1 - x^2) / (1 - x - x^2)分母 1 - x - x^2 是经典斐波那契数列的生成函数分母乘上 (1 - x^2) 只是做了一个轻微的下标修正最终系数正好是 a[n] F[n]。生成函数的价值在于当你把“奇数段”这个条件换成别的集合时不需要重新想状态转移只需要替换 A(x) 然后展开系数。很多看上去毫无头绪的计数题用生成函数都能直接推通项。4.3 大范围时别忘了特判矩阵快速幂写多了最容易栽的两个地方一是 n0 或 n1 没特判矩阵乘完返回错误结果二是矩阵乘法循环写错尤其是把外层 i、内层 j、中间 k 的循环顺序搞混导致算出来的矩阵根本不是那回事。我的习惯是矩阵快速幂函数开头就做 if (n 1) return 1 的特判并且每写完一次就用小数据回归一遍。因为矩阵代码本身抽象一旦出错不好肉眼排查提前用 1、2、5、6 这几个小值守住最后接大数据时才不会慌。5. 变式训练改一个条件解法怎么跟着变5.1 改成“只能拆成偶数段”这题的题眼是“奇数”如果题目改成“每段长度必须是偶数”数列会变成另一个简单序列。设 g[n] 为偶数长度段的有序拆分方案数ng[n]21426488规律是 g[2]1, g[4]2, g[6]4, g[8]8也就是 2^(n/2 - 1)。这个结论也可以用隔板法理解把每个偶数段统一看成若干个“2”的单位整条长度 n 被切成 n/2 个单位单位之间的空隙有 n/2 - 1 个每个空隙可以切或不切一共 2^(n/2 - 1) 种方案。对比一下就能发现奇数段对应二阶递推斐波那契偶数段对应一阶递推幂函数。差别来自“单位长度能不能单独成块”这也解释了为什么奇数约束会产生二阶依赖。5.2 限制最大段长 L 时怎么递推如果额外要求每段长度不能超过某个上限 L前面的 f[n] f[n-1] f[n-2] 就不再成立了。这种情况下老老实实回到原始定义f[n] Σ f[n-l]其中 l 取所有不超过 L 的正奇数直接这样做是 O(nL)当 n 和 L 都到 2e5 就会超时。优化套路也很固定用前缀和快速求区间和。具体来说维护奇偶两个前缀和数组因为每次加的奇数 l 只跟 f 的奇偶下标有关。每次计算 f[n] 时用前缀和求一段连续奇数下标 f 值的和就能在 O(1) 时间内完成转移。这种“枚举最后一刀或第一段 前缀和优化”的组合在分段计数题里几乎是标配值得单独练一练。5.3 如果还要求“恰好分成 k 段”有些变式题会限定“恰好拆成 k 个奇数段”。这种情况甚至可以不用 DP直接用组合数给出通项。每个奇数段可以写成 1 2a_j其中 a_j ≥ 0。那么n k 2 * (a_1 a_2 ... a_k)所以 a_1 ... a_k (n - k) / 2。为了保证整数n 和 k 必须同奇偶并且 n ≥ k。接下来就是把 (n-k)/2 个“2 单位”分给 k 个位置允许空位这是一个经典隔板法答案是C((nk)/2 - 1, k - 1)这个通项可以用来反推 DP 是否正确。很多变式题表面上是在考 DP其实先写出组合数通项再回来验证转移往往能更快发现问题。最后说点我的实际体验我在做这题的时候没有一上来就推导生成函数而是先写了个暴力枚举看到 1, 1, 2, 3, 5, 8 之后花了五分钟写好递推就交了。后来复盘才把生成函数和矩阵快速幂补上。现在回头看这类题的通用做法其实很清晰小数据打表 - 识别数列 - 反推递推 - 按数据范围选优化。如果一上来就硬想状态定义和转移方程很容易陷进去。另外几乎所有分段覆盖类计数题都可以先定义好“空状态” f[0]1这个边界一立许多递推都会自己理顺。遇到疑似斐波那契规律时也别忘了用小样例验证下标位移这是最隐蔽也最不值当的丢分点。希望这篇对你有用下次在计数题里再看到斐波那契冒头你知道它大概率就藏在递推的错位相消里。