1. 从一道多校赛题拆解数论组合拳的实战价值如果你刷过近几年的多校联合训练赛大概率会对一类题目印象深刻题干短得可怜就一个求和式但背后同时牵扯二次剩余、二项式定理和斐波那契数列三条线。HDU 6755 的 Fibonacci Sum 就是这种典型。它表面上让你算一个带组合数的斐波那契幂次和实际上是一道把数论工具链串起来考察的综合题。我第一次碰到它的时候盯着那个求和式看了十几分钟脑子里完全没有方向后来把三条线索逐一拆开才发现每一块单独拎出来都不算超纲难的是怎么把它们拼到一起。这篇文章面向的是已经掌握基础数论、想突破组合数学与模运算综合题的读者。我会从题目结构出发讲清楚为什么需要二次剩余来开根号、二项式定理在这里扮演什么角色、斐波那契数列的通项公式如何成为整个推导的枢纽以及最终怎么把复杂度压到可接受的范围。中间会穿插我自己踩过的坑比如模数不是质数时的处理、二次剩余无解时的判断、以及快速幂里指数取模的细节。这些细节在标准题解里往往一笔带过但真正写代码的时候一个地方没注意就会 WA 到怀疑人生。整篇内容按“问题拆解 → 工具准备 → 核心推导 → 代码落地 → 边界处理”的顺序展开每一部分都会解释清楚“为什么这样做”而不是只丢公式。如果你正在准备算法竞赛或者单纯对斐波那契数列的封闭形式感兴趣这篇应该能给你一些可以直接复用的思路。2. 题目结构拆解求和式里藏着哪几层信息2.1 原始求和式的构成要素先把题目核心形式摆出来。给定 n、c、k 以及模数 p要求计算S Σ_{i0}^{n} C(n, i) · c^i · F_i^k (mod p)其中 F_i 是第 i 个斐波那契数通常定义 F_00, F_11C(n, i) 是组合数c 是一个给定常数k 是幂次。n 可以到 1e18 级别k 也在 1e5 量级p 是一个特定的大质数常见是 1e99 这类。这个式子里有三个明显的难点。第一n 巨大不可能枚举 i 从 0 到 n。第二F_i^k 里的 k 次幂让斐波那契项变得非线性。第三组合数 C(n, i) 和 c^i 的存在暗示了某种二项式展开的结构。如果你只盯着 F_i 看会觉得无从下手但如果把 F_i 换成它的封闭形式整个式子就会露出真面目。2.2 为什么不能直接暴力递推有人可能会想斐波那契数列可以用矩阵快速幂在 O(log n) 时间内算出第 n 项那是不是可以逐项算问题在于求和范围是 0 到 nn 是 1e18逐项算的复杂度是 O(n log n)完全不可行。而且每一项还带组合数组合数本身也需要预处理阶乘n 太大连阶乘表都开不下。所以这道题的核心矛盾是求和项数太多但每一项之间有结构性的联系。我们必须找到一种方式把整个求和式压缩成一个或几个封闭形式的表达式然后用快速幂在 O(log n) 或 O(k log n) 时间内算出来。这个思路和很多组合求和题是一致的——先找生成函数或通项再整体化简。2.3 三条工具线的交汇点把 F_i 用通项公式展开是整道题的转折点。斐波那契数列的 Binet 形式是F_i (α^i - β^i) / √5其中 α (1√5)/2β (1-√5)/2且 αβ -1αβ 1。在模 p 意义下√5 是否存在取决于 5 是否是 p 的二次剩余。这就是二次剩余登场的地方——如果 5 在模 p 下没有平方根整个通项公式就没法在模意义下直接使用需要扩域或者换思路。一旦 √5 存在F_i^k 就可以用二项式定理展开成 (α^i - β^i)^k / (√5)^k再对 i 求和。此时组合数 C(n, i) 和 c^i 正好可以和 α^i、β^i 的幂次合并形成类似 (c·α^j)^i 的结构再用二项式定理反向合并。整个推导链条就是这样一环扣一环。3. 二次剩余模意义下开根号的正确姿势3.1 二次剩余的基本判定在模 p 下一个数 a 是二次剩余意味着存在 x 使得 x² ≡ a (mod p)。判定方法是计算 Legendre 符号 (a/p)当 p 是奇质数时(a/p) a^((p-1)/2) mod p如果结果是 1说明 a 是二次剩余如果是 -1即 p-1说明不是如果是 0说明 a ≡ 0。对于这道题我们需要判断 5 是否是 p 的二次剩余。以常见的 p 1e99 为例计算 5^((p-1)/2) mod p如果等于 1就可以继续。我实际写代码的时候习惯先写一个快速幂函数然后直接算这个值。如果返回 p-1就说明这道题在当前模数下需要特殊处理比如扩域到 F_p[√5] 上运算。不过大多数竞赛题会特意选一个让 5 是二次剩余的模数否则难度会上升一个档次。3.2 用 Tonelli-Shanks 算法求平方根确认 5 是二次剩余之后需要求出 √5 mod p 的具体值。最通用的方法是 Tonelli-Shanks 算法它的时间复杂度是 O(log² p)对于 1e9 级别的质数完全够用。算法的大致流程是把 p-1 写成 q · 2^s 的形式其中 q 是奇数。找一个非二次剩余 z即 (z/p) -1。初始化 m s, c z^q, t a^q, r a^((q1)/2)。当 t ≠ 1 时找最小的 i 使得 t^(2^i) 1然后更新各变量。最终 r 就是 a 的平方根。这个过程看起来有点绕但实现一次之后就可以当模板用。我在第一次写的时候卡在“找最小的 i”那一步因为循环边界没处理好导致死循环。后来发现只要每次从 1 开始枚举 i最多枚举到 m就不会有问题。3.3 模数不是质数时的替代方案如果模数不是质数二次剩余的判定和求解都会变得复杂。这时候可以考虑把模数分解质因数在每个质数幂下分别求解再用中国剩余定理合并。但竞赛题里这种情况很少见因为出题人通常会让模数是一个方便计算的大质数。如果真遇到了我建议先检查题目是否允许扩域或者是否存在其他不依赖开根号的推导路径。注意在写 Tonelli-Shanks 的时候一定要用 64 位整数因为中间计算会超过 32 位范围。我见过有人用 int 导致溢出结果求出来的平方根完全不对。4. 二项式定理把幂次展开再重新合并4.1 F_i^k 的展开逻辑有了 √5 之后F_i 可以写成 (α^i - β^i) · inv(√5)。那么 F_i^k 就是F_i^k (√5)^(-k) · Σ_{j0}^{k} C(k, j) · (-1)^(k-j) · α^(i·j) · β^(i·(k-j))这里用到了二项式定理 (x - y)^k Σ C(k, j) x^j (-y)^(k-j)。把 x α^i, y β^i 代入就得到上面的形式。注意 α 和 β 都是模 p 下的常数它们的幂次可以预先计算。这一步的关键在于原本 F_i^k 是一个关于 i 的非线性项展开之后变成了若干个 (α^j · β^(k-j))^i 的线性组合。也就是说每一项都是某个常数底数的 i 次幂。这就为后续对 i 求和铺平了道路。4.2 与组合数 C(n, i) 的合并原式里还有 C(n, i) · c^i。把 F_i^k 的展开代入整个求和变成S (√5)^(-k) · Σ_{j0}^{k} C(k, j) (-1)^(k-j) · Σ_{i0}^{n} C(n, i) · c^i · (α^j · β^(k-j))^i内层对 i 的求和是 Σ C(n, i) · (c · α^j · β^(k-j))^i这正好是二项式定理的展开形式Σ_{i0}^{n} C(n, i) · x^i (1 x)^n所以内层求和直接等于 (1 c · α^j · β^(k-j))^n。这样一来整个问题就化简成了对 j 从 0 到 k 的求和S (√5)^(-k) · Σ_{j0}^{k} C(k, j) (-1)^(k-j) · (1 c · α^j · β^(k-j))^n这个式子里k 是 1e5 级别枚举 j 是可行的。每一项需要计算 C(k, j)、α^j、β^(k-j) 以及一个快速幂。整体复杂度是 O(k log n)完全可以接受。4.3 预处理与递推优化直接对每个 j 都重新算 α^j 和 β^(k-j) 会导致大量重复计算。我的做法是预处理 α 的幂次表和 β 的幂次表以及阶乘和逆阶乘表。这样 C(k, j) 可以 O(1) 查询α^j 和 β^(k-j) 也可以 O(1) 拿到。具体来说预处理 fact[0..k] 和 inv_fact[0..k]用于计算组合数。预处理 pow_alpha[0..k]其中 pow_alpha[j] α^j。预处理 pow_beta[0..k]其中 pow_beta[j] β^j。每一项的 (1 c · pow_alpha[j] · pow_beta[k-j]) 用快速幂算 n 次方。这样整个循环体里只有一次快速幂是 O(log n) 的其余都是 O(1)。总复杂度 O(k log n k)对于 k 1e5 和 n 1e18 来说跑起来毫无压力。5. 斐波那契通项在模运算中的落地细节5.1 α 和 β 的模表示在实数域里α (1√5)/2β (1-√5)/2。在模 p 下我们需要先求出 √5 的值记为 s。那么α (1 s) · inv(2) mod p β (1 - s) · inv(2) mod p这里的 inv(2) 是 2 在模 p 下的逆元可以用费马小定理算即 2^(p-2) mod p。注意 β 可能是负数要加上 p 调整到正数范围。我见过有人在算 β 的时候忘记处理负数结果后续所有幂次都错了。这种错误很隐蔽因为程序不会报错只是答案不对。建议在算出 α 和 β 之后打印出来检查一下是否满足 α β ≡ 1 和 α · β ≡ -1。5.2 通项公式的适用条件Binet 公式在模 p 下成立的前提是 √5 存在。如果 5 不是二次剩余就需要在扩域 F_p[√5] 上运算此时每个数表示为 a b√5 的形式乘法和幂次都要按扩域规则来。扩域的实现会复杂一些但思路是一样的把 α 和 β 表示为扩域元素然后照常做快速幂和求和。不过对于 HDU 6755 这道题模数是精心挑选的5 是二次剩余所以可以直接在模 p 下算。如果你在别的题目里遇到 5 不是二次剩余的情况可以先检查题目是否允许扩域或者是否存在其他化简方式。5.3 幂次计算中的指数取模快速幂的指数是 nn 可以到 1e18直接作为指数传入快速幂函数没问题因为快速幂本身是 O(log n) 的。但要注意如果底数是 0快速幂的结果需要特殊处理。另外在计算 (1 c · α^j · β^(k-j))^n 的时候底数可能为 0此时如果 n 0结果是 0如果 n 0结果是 1。这个边界条件在代码里要单独判断。还有一个容易忽略的点α 和 β 的幂次在计算过程中可能会变成 0尤其是当 j 很大或 k-j 很大的时候。如果底数变成 0后续的乘积也会变成 0这是正确的数学结果不需要额外处理。6. 代码实现从公式到可运行程序6.1 核心函数清单整个程序需要以下几个核心函数fast_pow(base, exp, mod)快速幂用于计算幂次和逆元。tonelli_shanks(a, p)求 a 在模 p 下的平方根。precompute_factorials(k, mod)预处理阶乘和逆阶乘。precompute_powers(base, k, mod)预处理某个底数的幂次表。solve(n, c, k, p)主求解函数按推导公式累加。每个函数的实现都不复杂但要注意细节。比如快速幂里要用 long long 防止溢出Tonelli-Shanks 里要正确处理 t 1 的情况阶乘预处理要注意 k 的范围。6.2 主循环的累加逻辑主循环对 j 从 0 到 k 遍历每次计算term C(k, j) * (-1)^(k-j) * pow(1 c * pow_alpha[j] * pow_beta[k-j], n, p) S (S term) % p最后再乘以 (√5)^(-k)。注意 (-1)^(k-j) 可以用 (k-j) 的奇偶性来判断奇数取 p-1偶数取 1。这样比直接算幂次更快。我在写的时候一开始把 (-1)^(k-j) 写成了 pow(-1, k-j, p)虽然结果正确但每次调用快速幂会慢一些。后来改成判断奇偶性速度快了不少。对于 k 1e5 的规模这种优化还是有意义的。6.3 复杂度分析与实测表现整个算法的复杂度是 O(k log n k log p)其中 k log n 来自主循环里的快速幂k log p 来自预处理。对于 k 1e5, n 1e18, p 1e99实测在普通机器上跑一次大约几十毫秒完全满足竞赛要求。如果 k 更大比如 1e6主循环的快速幂可能会成为瓶颈。这时候可以考虑用欧拉降幂或者预处理更多东西但一般竞赛题不会把 k 出到那么大。7. 踩坑记录那些让我 WA 到凌晨的细节7.1 二次剩余无解时的误判我第一次写的时候没有先判断 5 是否是二次剩余直接调用 Tonelli-Shanks。结果在某些模数下算法陷入死循环因为找不到非二次剩余 z。后来加了判定逻辑如果 5^((p-1)/2) mod p 不等于 1就输出无解或者切换到扩域方案。这个检查只需要一行代码但能避免很多调试时间。7.2 组合数预处理的范围错误组合数 C(k, j) 需要阶乘表到 k。我一开始把阶乘表开到了 n结果内存直接爆了。后来意识到只需要到 k 就够了因为二项式展开的上限是 k不是 n。这个错误很典型因为题目里 n 和 k 同时出现容易搞混谁需要预处理。7.3 快速幂底数为零的边界当 1 c · α^j · β^(k-j) ≡ 0 (mod p) 时如果 n 0这一项应该是 0。但我的快速幂函数在底数为 0 且指数为 0 时返回了 1导致结果偏大。后来在调用快速幂之前加了一个判断如果底数为 0直接根据 n 是否为 0 返回 0 或 1。这个边界条件在数学上是显然的但代码里很容易漏掉。7.4 负数取模的处理在计算 β (1 - s) · inv(2) 的时候1 - s 可能是负数。Python 里负数取模会自动调整到正数但 C 里不会。如果你用 C 写需要手动加上 p 再取模。我一开始用 Python 写没发现问题后来转 C 重写的时候忘了这个细节结果答案完全不对。这种语言差异导致的坑跨语言移植的时候特别容易踩。8. 从这道题延伸出的通用解题框架8.1 识别“组合数 幂次 递推数列”的信号这道题的核心结构是组合数 C(n, i) 乘以某个递推数列的幂次再对 i 求和。遇到这种形式第一反应应该是把递推数列用通项公式展开然后利用二项式定理反向合并。斐波那契数列因为有 Binet 公式所以特别适合这种操作。其他线性递推数列如果有类似的通项形式也可以套用同样的思路。具体来说如果数列 a_i 满足 a_i A · r1^i B · r2^i 的形式那么 a_i^k 展开后会出现 r1^(i·j) · r2^(i·(k-j)) 这样的项再和 C(n, i) · c^i 合并就能用二项式定理化简。这个框架可以推广到很多类似的求和问题。8.2 模数选择对解法的影响模数是否是质数、5 是否是二次剩余、是否存在原根这些都会影响解法的选择。如果模数是质数且 5 是二次剩余可以直接在模 p 下算。如果 5 不是二次剩余就需要扩域。如果模数不是质数可能需要分解质因数再用中国剩余定理。竞赛题通常会选一个“友好”的模数但了解各种情况下的应对方案能让你在遇到变体题时更从容。8.3 预处理与内存的平衡k 的大小决定了预处理的范围。如果 k 是 1e5开几个长度为 k1 的数组完全没问题。如果 k 是 1e7就需要考虑内存限制可能需要边算边用或者用滚动数组。这道题里 k 是 1e5所以可以放心预处理。但在其他题目里要先估算内存占用再决定预处理策略。9. 一些可以复用的代码片段与调试技巧9.1 Tonelli-Shanks 的 Python 实现def tonelli_shanks(a, p): if a 0: return 0 if pow(a, (p - 1) // 2, p) ! 1: return None if p % 4 3: return pow(a, (p 1) // 4, p) q p - 1 s 0 while q % 2 0: q // 2 s 1 z 2 while pow(z, (p - 1) // 2, p) ! p - 1: z 1 m s c pow(z, q, p) t pow(a, q, p) r pow(a, (q 1) // 2, p) while t ! 1: i 1 t2 (t * t) % p while t2 ! 1: t2 (t2 * t2) % p i 1 b pow(c, 1 (m - i - 1), p) m i c (b * b) % p t (t * c) % p r (r * b) % p return r这个实现里p % 4 3的情况可以直接用公式省去 Tonelli-Shanks 的循环。对于 p 1e99p % 4 1所以需要走完整流程。我实测这个函数在 p 1e99 下求 5 的平方根返回的值平方后确实等于 5可以放心使用。9.2 调试时打印中间变量在推导过程中我习惯把 α、β、√5 的值打印出来验证 α β ≡ 1、α · β ≡ -1、α - β ≡ √5 这些恒等式。如果这些基本关系不成立后面的推导肯定有问题。另外对于小的 n 和 k可以用暴力法算一遍和公式法的结果对比。比如 n 5, k 3 的时候暴力枚举 i 从 0 到 5算出每一项再求和和公式法的结果应该完全一致。这种小规模验证能帮你快速定位是公式推导错了还是代码实现错了。9.3 性能优化的几个方向如果主循环太慢可以考虑把快速幂里的模运算改成用__int128或者手动防溢出减少取模次数。把 (-1)^(k-j) 的奇偶判断提到循环外用两个变量交替更新。如果 k 很大可以考虑用 NTT 或者分治来加速求和但这通常超出竞赛范围。对于 HDU 6755 这道题O(k log n) 已经足够不需要更复杂的优化。把代码写清楚、边界处理对比追求极致性能更重要。10. 个人在实际操作中的几点体会这道题我前前后后写了三遍才完全通过。第一遍是思路不对试图直接递推第二遍是公式推对了但代码里负数取模没处理第三遍才把所有细节都照顾到。最大的体会是数论题的正确性依赖于每一个环节的严谨任何一个地方偷懒都会导致答案错误而且错误往往很隐蔽不是崩溃而是静默地给出错误结果。另外二次剩余这部分虽然看起来吓人但实际用到的只是判定和求平方根两个操作把模板准备好之后就是调用的事。真正需要花心思的是二项式展开和求和合并那一步要理解为什么展开后能重新合并成 (1 x)^n 的形式。这个技巧在很多组合求和题里都会出现值得反复练习。最后分享一个小习惯每次写完数论题我都会用几个小数据手动验证一遍再和暴力程序对拍。对于这道题n 取 0 到 10k 取 1 到 5c 取几个不同的值跑一遍对比。如果全部一致再提交。这个习惯帮我省了很多次 WA 之后的无效调试。
