1. 从暴力到优雅组合数计算的效率跃迁在算法竞赛和日常编程中组合数 C(n, m) 的计算是一个高频需求。无论是概率统计、排列组合问题还是动态规划的状态转移都离不开它。很多新手的第一反应是直接套用公式 C(n, m) n! / (m! * (n-m)!)然后写一个阶乘函数。这个思路直观但存在两个致命问题一是阶乘数值增长极快极易超出整数类型的表示范围二是即使使用高精度每次查询都重新计算阶乘时间复杂度为 O(n)在多次查询比如 AcWing 886 这类题目通常需要回答大量询问的场景下会带来 O(q * n) 的总复杂度这无疑是无法接受的。这就引出了我们今天要深入探讨的核心预处理优化的O(n)版本。这个方案的精髓在于“空间换时间”和“数论预处理”。它并非简单地缓存阶乘而是通过预处理阶乘和阶乘的逆元将每次查询组合数的操作降低到 O(1) 的时间复杂度。这里的“O(n)”指的是预处理阶段的时间复杂度而非单次查询。对于需要处理十万甚至百万级别查询的题目这种优化是决定性的。接下来我将带你一步步拆解这个方案的原理、实现细节以及那些容易踩坑的地方。2. 核心基石模运算下的乘法逆元要理解预处理优化必须先搞懂“模运算下的乘法逆元”这个概念。这是整个方案的数学基础。在普通的实数域里一个数 a 的乘法逆元就是它的倒数 1/a因为 a * (1/a) 1。在模运算的世界里我们也想找到一个类似的数。具体来说对于一个整数 a 和一个模数 p通常 p 是一个质数如果存在一个整数 x使得(a * x) % p 1那么 x 就称为 a 在模 p 意义下的乘法逆元记作a^(-1)或inv(a)。为什么逆元如此重要因为我们想在模 p 下计算除法。直接做除法(a / b) % p是没有定义的。但如果我们找到了 b 的逆元inv(b)那么就可以将除法转化为乘法(a / b) % p (a * inv(b)) % p。这完美契合了组合数公式C(n, m) n! / (m! * (n-m)!)的需求——我们可以通过计算n! * inv(m!) * inv((n-m)!) % p来得到结果。那么如何高效地求解逆元呢当模数 p 为质数时最常用的方法是费马小定理配合快速幂。费马小定理指出若 p 是质数且整数 a 不是 p 的倍数则a^(p-1) ≡ 1 (mod p)。 将等式两边同时除以 a得到a^(p-2) ≡ a^(-1) (mod p)。 因此a在模p下的逆元inv(a) a^(p-2) % p。计算a^(p-2) % p可以使用快速幂算法时间复杂度为 O(log p)。如果对每一个阶乘值都单独用快速幂求逆元预处理的总复杂度会变成 O(n log p)虽然比暴力好但还不够极致。我们接下来要介绍的“线性求逆元”方法可以将预处理逆元数组的复杂度优化到真正的 O(n)。3. 预处理流水线阶乘数组与逆元数组的构建我们的目标是预处理两个数组fact[i]: 存储 i! % p 的值。infact[i]: 存储 (i!)^(-1) % p 的值即 i! 的逆元。有了这两个数组计算组合数就变成了一个简单的公式C(n, m) fact[n] * infact[m] % p * infact[n-m] % p整个预处理过程分为三步这才是实现“优化的O(n)版本”的关键3.1 第一步初始化与边界处理首先我们需要确定预处理的范围。通常题目会给出数据范围比如 n, m ≤ 10^5。那么我们的数组大小至少要是 N 100010。 模数 p 通常给定为质数例如常见的 1e97。const int N 100010, MOD 1e9 7; long long fact[N], infact[N]; // 使用long long防止中间结果溢出边界条件0! 1并且规定1的逆元也是1。fact[0] infact[0] 1;这个初始化至关重要因为它是后续所有递推的起点。3.2 第二步线性预处理阶乘数组这一步非常直观就是一个简单的递推fact[i] fact[i-1] * i % MOD从i1循环到最大值N-1即可。时间复杂度 O(N)。3.3 第三步线性预处理阶乘逆元数组这是整个算法的精华所在也是“优化的O(n)”中“优化”二字的体现。我们不是对每个fact[i]单独用快速幂求逆元而是利用一个巧妙的递推关系。我们知道infact[i]是fact[i]的逆元。 考虑fact[i] fact[i-1] * i % MOD。 对等式两边同时取逆元逆元运算满足(a*b)^(-1) a^(-1) * b^(-1)infact[i] infact[i-1] * inv(i) % MOD问题转化为如何快速得到inv(i)即整数i的逆元这里我们使用线性递推求 1 到 n 的逆元公式inv(i) (MOD - MOD / i) * inv(MOD % i) % MOD这个公式的推导基于模运算的欧几里得算法扩展这里不展开证明但我们可以验证其正确性并理解如何使用。因此预处理infact数组的步骤是先利用上述公式预处理出1到N-1每个数字i的逆元inv[i]。再利用递推式infact[i] infact[i-1] * inv[i] % MOD求出每个阶乘的逆元。核心代码实现如下// 第一步预处理数字逆元 inv[i] inv[1] 1; // 1的逆元是1 for (int i 2; i N; i ) { inv[i] (MOD - MOD / i) * inv[MOD % i] % MOD; } // 第二步预处理阶乘逆元 infact[i] infact[0] 1; for (int i 1; i N; i ) { infact[i] infact[i - 1] * inv[i] % MOD; }注意inv[i]数组可以只作为临时变量使用在计算完infact[i]后就不需要保存了这样可以节省空间。但为了清晰理解流程这里分开表示。至此我们完成了所有预处理工作。总时间复杂度为 O(N)空间复杂度为 O(N)。之后每次查询组合数都是 O(1) 的常数时间操作。4. 完整实现与细节打磨将以上所有步骤整合并考虑输入输出我们得到 AcWing 886 题目的标准解法框架。#include iostream using namespace std; const int N 100010, MOD 1e9 7; long long fact[N], infact[N]; // 快速幂函数这里用于验证或备用在线性递推方法中并非必需 long long qmi(long long a, long long k, long long p) { long long res 1; while (k) { if (k 1) res res * a % p; a a * a % p; k 1; } return res; } int main() { // 1. 初始化边界 fact[0] infact[0] 1; // 2. 预处理阶乘数组 fact[] for (int i 1; i N; i ) { fact[i] fact[i - 1] * i % MOD; } // 3. 预处理阶乘逆元数组 infact[] // 方法一线性递推求逆元推荐效率O(N) infact[0] 1; long long inv_i 1; // 用于临时存储 i 的逆元 for (int i 1; i N; i ) { // 线性求 i 的逆元 // 公式inv(i) (MOD - MOD/i) * inv(MOD%i) % MOD // 由于循环从1开始我们需要计算 inv[i]这里用临时变量演示 // 实际可以写为 // inv[i] (MOD - MOD / i) * inv[MOD % i] % MOD; // 需要额外inv数组 // infact[i] infact[i - 1] * inv[i] % MOD; // 更简洁的写法合并步骤只用一个临时变量 // 假设我们已经有了 inv(i)这里用快速幂演示另一种方法非最优用于理解 // 实际竞赛中对于固定的MOD通常直接写出线性递推代码。 // 下面这行是使用快速幂求逆元复杂度O(N log MOD)用于对比理解 // infact[i] infact[i - 1] * qmi(i, MOD - 2, MOD) % MOD; // 正确的线性递推写法需要一个小数组或临时变量链式计算 // 由于推导稍复杂竞赛中常直接背下线性求逆元模板。 // 这里给出一种常见的、易于实现的预处理infact的写法利用费马小定理和fact数组 // 先预处理 fact 然后 infact[N-1] qmi(fact[N-1], MOD-2, MOD) // 再倒着递推 infact[i] infact[i1] * (i1) % MOD; } // 更常见的完整线性预处理写法如下 fact[0] infact[0] 1; for (int i 1; i N; i ) { fact[i] fact[i - 1] * i % MOD; } // 先求出最大那个阶乘的逆元 infact[N - 1] qmi(fact[N - 1], MOD - 2, MOD); // 倒着推回所有阶乘的逆元 for (int i N - 2; i 0; i --) { infact[i] infact[i 1] * (i 1) % MOD; } // 这个方法是因为 (i!)^(-1) ((i1)!)^(-1) * (i1) % MOD // 推导 (i1)! i! * (i1) i! (i1)! / (i1) // 取逆元 (i!)^(-1) (i1) * ((i1)!)^(-1)) % MOD int n; scanf(%d, n); while (n -- ) { int a, b; scanf(%d%d, a, b); // 组合数公式 C(a, b) fact[a] * infact[b] % MOD * infact[a - b] % MOD printf(%lld\n, fact[a] * infact[b] % MOD * infact[a - b] % MOD); } return 0; }5. 两种逆元预处理路径的对比与选择在上面的代码中我们看到了两种预处理infact数组的方法方法A线性递推求数字逆元先正序求出每个数字i的逆元inv[i]再利用infact[i] infact[i-1] * inv[i] % MOD正序递推。方法B利用最大阶乘逆元倒推先求出fact[N-1]的逆元用一次快速幂再利用关系式infact[i] infact[i1] * (i1) % MOD倒序递推。两种方法的时间复杂度都是 O(N)空间复杂度也都是 O(N)。在实际竞赛中两者效率相差无几都可以使用。但它们体现了不同的思路方法A更通用。inv[i]数组本身可能在其他地方也有用。其递推公式inv[i] (MOD - MOD/i) * inv[MOD%i] % MOD是一个需要记忆的模板。方法B更直观尤其是关系式infact[i] infact[i1] * (i1) % MOD直接从阶乘定义推导而来更容易理解。它只需要一次快速幂O(log MOD)对整体复杂度影响可忽略。个人经验与选择我通常更倾向于使用方法B。原因有三第一推导过程更自然不易记错公式第二代码结构清晰先正序算fact再一次幂运算最后倒序算infact第三在调试时逻辑链路更直白。方法A的线性求逆元公式虽然巧妙但万一记忆模糊容易推导错误。6. 关键边界与常见“坑点”剖析即使理解了算法实现时依然有几个细节必须严格把控否则极易出错。6.1 模运算的乘法陷阱核心计算公式fact[a] * infact[b] % MOD * infact[a - b] % MOD中连续乘法的取模顺序非常重要。(fact[a] * infact[b]) % MOD的结果再乘以infact[a-b]必须再次取模。更安全的写法是每乘一次就取一次模或者使用long long类型暂存结果。因为三个10^9量级的数相乘中间结果会超过64位整数的表示范围约1.8e19即使使用long long也可能溢出。最稳妥的写法是long long res fact[a]; res res * infact[b] % MOD; res res * infact[a - b] % MOD; printf(%lld\n, res);6.2 数组下标与查询范围预处理数组的大小N必须严格大于题目可能询问的最大n值。例如题目说a, b ≤ 10^5那么N至少需要100010。在查询时要确保输入的a和b满足b a且a, b非负。虽然题目通常会保证输入合法但在自己设计函数时务必加入合法性检查例如if (b a || b 0) return 0; // 组合数定义当 b a 或 b 0 时结果为06.3 对模数 p 的假设整个算法严重依赖于一个前提模数 p 是一个质数并且需要与所有阶乘值互质因为要求逆元。通常题目中给出的MOD 1e97就是一个质数。如果模数不是质数费马小定理失效就需要使用扩展欧几里得算法来求逆元或者采用其他方法如卢卡斯定理用于小质数或分解质因数用于非质数模数。绝对不要在不验证模数是否为质数的情况下直接套用此模板。6.4 初始化的重要性fact[0] infact[0] 1这行初始化代码是递推的基石。忘记初始化会导致后续所有计算结果错误。这是一个典型的“差之毫厘谬以千里”的坑。7. 性能实测与复杂度分析我们来量化一下这种优化带来的收益。假设我们需要回答q 10^5次查询每次查询的n平均为10^5。暴力法每次计算单次计算阶乘需要 O(n)总复杂度O(q * n) ≈ 10^10次运算完全不可行。预处理阶乘快速幂求逆元预处理fact数组 O(N)。每次查询需要计算两次快速幂求m!和(n-m)!的逆元单次查询复杂度 O(log MOD)。总复杂度O(N q * log MOD) ≈ 10^5 10^5 * 30 ≈ 3*10^6可以接受。预处理阶乘线性逆元本文方法预处理fact和infact数组 O(N)。每次查询仅为三次取模乘法和一次取模运算 O(1)。总复杂度O(N q) ≈ 2*10^5。比上一种方法又减少了一个log因子在大规模查询下优势明显。在实际的在线判题系统OJ上这种优化通常意味着“通过”与“超时”的区别。对于 AcWing 886 这道题使用未优化的方法几乎一定会超时。8. 举一反三方案变体与扩展思考掌握了这个核心方法我们可以解决一系列变种问题多模数问题如果题目有多个不同的质数模数我们需要为每个模数预处理一套fact和infact数组。更大范围的计算当n很大比如10^18但模数p较小比如10^5时可以使用卢卡斯定理Lucas Theorem将大问题分解为多个小问题再对小问题使用本方法求解。非质数模数如果模数不是质数无法保证逆元存在。此时可以尝试将模数分解质因数将组合数表示为质因数的幂次形式最后再用中国剩余定理合并结果。或者如果模数可以拆成若干个互质的因子且每个因子是质数的幂也可以分别计算后合并。组合恒等式的预处理有时需要频繁查询C(n, k)对固定的n和所有k。可以利用关系式C(n, k) C(n, k-1) * (n-k1) / k并预处理k的逆元实现 O(n) 预处理O(1) 查询所有k。这个“预处理逆元”的思想不仅用于组合数它实际上是在模运算下将除法转为乘法的通用策略。在任何需要频繁进行模除法的场景下例如多项式运算、动态规划中的状态转移涉及除法都可以考虑预先计算好相关元素的逆元。回过头看从最原始的阶乘相除到引入模逆元再到线性预处理这个过程完美体现了算法优化中“以空间换时间”和“预处理”的核心思想。它要求我们不仅记住模板更要理解其背后的数论原理和设计动机。下次当你再遇到需要大量计算组合数的问题时希望这套“预处理优化的O(n)版本”能成为你手中得心应手的利器。