查询)
1. 项目概述从暴力到优雅的质变组合数计算这个在算法竞赛和面试中老生常谈的问题听起来似乎平平无奇。不就是 C(n, m) n! / (m! * (n-m)!) 吗很多新手朋友拿到题目第一反应可能就是直接套公式写个阶乘函数一除就完事了。但当你真正在 AcWing 886 这类题目里面对高达 10^5 次的查询和 10^5 量级的 n 与 m 时这种天真的想法会立刻让你体会到什么是“超时到绝望”。我最初也踩过这个坑以为算法题考的是数学公式后来才明白它真正考的是如何将数学知识转化为高效、可工程化的计算过程。“求组合数 II”这个标题其核心领域是算法竞赛中的数论与组合数学更具体点是模运算下的组合数高效计算。潜在需求非常明确在模数 p通常是质数如 1e97下需要应对海量10^5 量级的组合数查询每次查询必须达到近乎 O(1) 的响应速度。直接计算阶乘再除法即使每一步都取模单次查询的复杂度也是 O(n)对于 10^5 次查询就是 O(n^2)完全不可接受。因此标题中提到的“预处理优化的O(n)版本”就是破局的关键。它不是一个奇技淫巧而是一种标准的、必须掌握的预处理思想Precomputation和模逆元Modular Inverse技术的结合应用。简单来说它的核心思路是把昂贵的、重复的计算提前做好存起来用空间换时间。我们预先计算出所有可能用到的阶乘值fact[i]和阶乘的模逆元infact[i]这样每次查询 C(n, m) 时只需要一次查表O(1)和两次乘法、一次取模操作就能得到结果。这个“O(n)”指的是预处理阶段的复杂度查询本身是 O(1) 的。这不仅仅是解一道题更是一种重要的算法优化范式。它适用于任何需要频繁查询固定范围内某种函数值且该函数可分解为预计算量的组合的场景。理解并掌握它能让你在面对类似“大量查询斐波那契数列第n项”、“大量查询前缀和”等问题时拥有降维打击的思维工具。2. 核心思路与数学原理拆解2.1 为什么直接算阶乘不行模运算下的除法陷阱我们先回顾最直接的公式C(n, m) n! / (m! * (n-m)!)。 在普通整数运算下这没问题。但题目通常要求结果对一个质数p如1e97取模。我们学过模运算的基本规则(a b) % p (a % p b % p) % p(a * b) % p (a % p * b % p) % p但是没有(a / b) % p (a % p / b % p) % p这条规则因为模运算下的“除法”定义完全不同。在模p的世界里我们要把 “除以 b” 转化为 “乘以 b 的乘法逆元”。b 的乘法逆元inv(b)满足b * inv(b) ≡ 1 (mod p)。 所以a / b (mod p)等价于a * inv(b) (mod p)。因此组合数公式在模p下正确的形式是C(n, m) ≡ n! * inv(m!) * inv((n-m)!) (mod p)这里inv(x)表示 x 在模 p 下的乘法逆元。问题转化为如何高效计算n!以及n!的逆元2.2 破局关键费马小定理与快速幂求逆元既然 p 是质数本题通常保证是质数我们可以请出数论中的一位“老朋友”——费马小定理。 费马小定理指出若 p 是质数且整数 a 不是 p 的倍数则a^(p-1) ≡ 1 (mod p)。 由此可以推出a * a^(p-2) ≡ 1 (mod p)。 对比逆元的定义a * inv(a) ≡ 1 (mod p)我们得到inv(a) ≡ a^(p-2) (mod p)。这意味着对于任意非零的 a在模 p 意义下我们可以通过计算a^(p-2) mod p来得到它的逆元。计算幂次我们又有另一位“老朋友”——快速幂算法它可以在 O(log p) 的时间复杂度内完成计算。所以最基础的优化版本呼之欲出预处理出所有fact[i] i! % p然后对于每次查询 C(n, m)我们用公式C(n, m) fact[n] * quick_pow(fact[m], p-2) * quick_pow(fact[n-m], p-2) % p其中quick_pow是快速幂函数。这个算法单次查询的复杂度是 O(log p)因为要算两次快速幂。对于 10^5 次查询总复杂度约为 O(2 * 10^5 * log(1e97))大约在 10^7 量级在C中通常可以勉强通过但并非最优且常数较大。2.3 终极优化线性预处理阶乘逆元“预处理优化的O(n)版本”的精髓就在于把quick_pow也通过预处理消除掉让查询真正变成 O(1)。我们不仅预处理阶乘数组fact[N]还预处理阶乘的逆元数组infact[N]。使得infact[i] ≡ inv(i!) (mod p)。那么组合数公式就变成了C(n, m) fact[n] * infact[m] * infact[n-m] % p查询时只需要三次乘法和一次取模。现在核心问题变成如何高效地预处理出infact数组如果对每个 i 都用快速幂计算inv(i!)那预处理复杂度就是 O(n log p)和上面基础版没区别。这里用到了一个非常巧妙的递推关系。 我们知道fact[i] fact[i-1] * i % p对于逆元我们能否找到类似的关系有的。目标已知infact[i] inv(i!)求infact[i-1]。 根据定义i! * infact[i] ≡ 1 (mod p)而i! (i-1)! * i所以(i-1)! * i * infact[i] ≡ 1 (mod p)观察这个式子(i-1)!的逆元infact[i-1]应该满足(i-1)! * infact[i-1] ≡ 1。 对比上下两式我们可以得到infact[i-1] ≡ i * infact[i] (mod p)这是一个从后向前的递推式也就是说如果我们能先求出infact[n]最大的那个就可以用infact[i-1] i * infact[i] % p这个公式一路倒着推回来线性时间内填满整个infact数组。那么infact[n]怎么求用一次快速幂即可infact[n] quick_pow(fact[n], p-2)。预处理流程总结fact[0] 1;// 0的阶乘定义为1正推计算fact[i] fact[i-1] * i % p(i从1到N)计算infact[N] quick_pow(fact[N], p-2)// 只做一次快速幂倒推计算infact[i-1] infact[i] * i % p(i从N down to 1)同样定义infact[0] 1;// 0的阶乘逆元也是1整个预处理过程的时间复杂度是 O(N)空间复杂度是 O(N)。之后的海量查询每次都是 O(1)。实操心得很多朋友在推导infact[i-1]的递推式时会卡住。一个记忆技巧是infact数组是“阶乘”的逆元所以它的递推必然和“乘法”有关而且是“除回去”的感觉。从infact[i]到infact[i-1]相当于把i这个因子从“整体逆元”中“拿出去”所以需要乘以i。多推演几遍就能形成直觉。3. 代码实现与逐行解析理解了数学原理我们来看 C 实现。这里假设模数MOD 1e97预处理的最大范围N 100005根据题目要求调整。3.1 数据结构定义与初始化#include iostream using namespace std; typedef long long LL; // 使用long long防止乘法溢出 const int N 100010; // 预处理的最大范围通常比题目数据范围稍大 const int MOD 1e9 7; // 常用质数模数 LL fact[N]; // fact[i] i! % MOD LL infact[N]; // infact[i] (i!)^(-1) % MOD // 快速幂模板函数计算 a^k % p LL qmi(LL a, LL k, LL p) { LL res 1; while (k) { if (k 1) res res * a % p; a a * a % p; k 1; } return res; } // 预处理函数 void init() { 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; // 注意这里的下标关系 // 公式是 infact[i] infact[i1] * (i1) % MOD // 因为我们的递推式是 infact[i-1] infact[i] * i % MOD // 将 i 替换为 i1得到 infact[i] infact[i1] * (i1) % MOD } }代码解析与注意事项typedef long long LL这是关键中的关键。fact和infact在计算过程中会进行乘法即使对MOD取模中间结果也可能超过int范围约21亿。1e97这个模数本身就和int最大值很接近两个这样的数相乘肯定会溢出。long long可以安全地容纳中间结果。快速幂函数qmi这是标准写法。a a * a % p这一行同样要注意使用LL类型或者将a声明为LL。预处理范围N务必根据题目给出的n的最大可能值来设置。通常设为100010或200010比题目上限100000大一点防止边界错误。这是一个非常常见的“踩坑点”。倒推循环for (int i N - 2; i 0; i -- )为什么从N-2开始因为infact[N-1]我们已经用快速幂求出来了。循环体内是infact[i] infact[i 1] * (i 1) % MOD这对应了推导公式infact[i-1] infact[i] * i % MOD。你可以这样理解当循环变量为i时我们正在计算infact[i]它等于infact[i1]已经算好的后一项乘以(i1)。初始化fact[0] infact[0] 1这是数学定义。0的阶乘是11在模任何数下的逆元也是1。这保证了公式C(n, 0) C(n, n) fact[n] * infact[0] * infact[n] % MOD 1的正确性。3.2 查询函数与主程序逻辑预处理完成后查询就变得异常简单。// 查询组合数 C(a, b) % MOD LL C(int a, int b) { if (b a) return 0; // 组合数定义如果下项大于上项结果为0 // 核心查询公式O(1) 时间复杂度 return fact[a] * infact[b] % MOD * infact[a - b] % MOD; } int main() { init(); // 程序开始先调用一次预处理一劳永逸 int n; scanf(“%d”, n); // 查询次数 while (n -- ) { int a, b; scanf(“%d%d”, a, b); printf(“%lld\n”, C(a, b)); // 注意输出格式为 long long } return 0; }查询函数C(a, b)的细节边界检查if (b a) return 0;这是组合数的数学性质。虽然题目可能保证输入合法但加上这一步是良好的编程习惯使函数更健壮。乘法的取模顺序return fact[a] * infact[b] % MOD * infact[a - b] % MOD;这里为什么分两次取模而不是写成(fact[a] * infact[b] * infact[a - b]) % MOD 原因是防止溢出。即使fact[a]和infact[b]都在MOD以内它们相乘的结果可能超出long long范围吗1e97约等于1e9两个1e9相乘是1e18这在long long约9e18的安全范围内。但三个1e9相乘就是1e27远超long long范围会导致溢出。因此每乘一次就取一次模是最安全的写法。fact[a] * infact[b] % MOD的结果肯定小于MOD再乘以一个小于MOD的数结果小于1e18在long long安全范围内最后再取模。printf(“%lld\n”, C(a, b));由于函数返回类型是LL即long long输出时必须使用%lld格式符。在部分OJ或编译器环境下使用%d输出long long会导致错误结果这是一个隐蔽的坑。避坑指南在实际竞赛或面试中我强烈建议将组合数查询函数写成一个“万能”版本包含更多的边界检查例如判断b 0的情况。虽然题目可能不考但这体现了思维的严密性。此外如果模数p不是质数费马小定理失效这套方法就行不通了需要改用扩展欧几里得算法求逆元或者使用其他方法如Lucas定理。所以在应用此方法前务必确认p是质数这一前提条件。4. 算法性能分析与对比为了让你更直观地理解“预处理O(n)版本”的优势我们将其与几种常见方法进行对比。方法预处理时间复杂度单次查询时间复杂度适用场景优缺点暴力计算(公式取模)无O(n)n, m 非常小 (n 20)实现简单但完全无法应对大数据。基础优化(阶乘快速幂求逆)无O(log p)查询次数较少 (q 1000)无需预处理节省空间。查询成本尚可但q大了就慢。递推法(使用公式 C(n,m)C(n-1,m)C(n-1,m-1))O(n²)O(1)n, m 较小 (n 2000)查询极快但预处理是平方级空间也是 O(n²)限制大。预处理阶乘与逆元 (本文方法)O(n)O(1)n 较大 (n ≤ 1e5)查询量巨大 (q ≤ 1e5)空间 O(n)预处理线性查询常数。是此类问题的标准答案。Lucas定理无或 O(p)O(log_p n)n, m 巨大 (1e9)但模数 p 较小 (p ≤ 1e5)处理n,m远大于模数的情况是另一种维度的武器。从对比可以看出当问题规模落在“n 在 1e5 量级查询次数 q 也在 1e5 量级”这个典型区间时O(n) 预处理 O(1) 查询的方案在时间复杂度和空间复杂度上取得了完美的平衡。复杂度计算示例假设n_max 100000,q 100000,MOD 1e97。预处理阶段计算fact数组需要 1e5 次乘法和取模计算infact[N-1]需要一次O(log MOD) ≈ 30次运算的快速幂倒推infact数组又需要 1e5 次运算。总计约2 * 10^5 30次运算在 C 中瞬间完成。查询阶段每次查询 3 次乘法、2 次取模总计5 * 10^5次运算同样飞快。 整个程序的总运算量在10^6量级现代 CPU 可以在零点几秒内完成。如果使用基础优化版每次查询做两次快速幂单次查询约 60 次运算总查询运算量达6 * 10^6虽然也可能通过但常数大了很多在时间限制严格的题目中可能处于临界状态。而递推法的 O(n²) 预处理需要 1e10 次运算完全不可行。5. 典型问题排查与扩展思考5.1 常见错误与调试技巧即使理解了原理实现时也可能遇到各种问题。下面是我和学员们常踩的坑错误输出错误或负数可能原因1最常见乘法溢出。检查所有*运算符的两边是否都是long long类型。在fact[i] fact[i - 1] * i % MOD中如果fact[i-1]是inti也是int相乘的结果会先以int计算此时就可能已经溢出然后再转换为long long取模为时已晚。确保fact数组是LL类型并且i在乘法前被强制转换或确保表达式以LL类型计算。一种安全的写法是fact[i] fact[i - 1] * (LL)i % MOD。可能原因2取模遗漏或顺序错误。确保每一步可能溢出的乘法后面都紧跟了% MOD。回顾我们查询函数的写法。可能原因3infact数组递推公式写反。记住是infact[i-1] infact[i] * i % p即用“大的”阶乘逆元去推导“小的”。如果写成了infact[i] infact[i-1] * i % p就错了因为infact[i-1]是(i-1)!的逆元乘以i得到的是( (i-1)! * i )^(-1) (i!)^(-1) / i并不是infact[i]。错误运行超时 (TLE)可能原因预处理范围N设置过大或过小。如果N设置得远超题目需要的最大值例如设为1e6预处理本身就会消耗较多时间。如果N设置小了当查询的a大于N时访问fact[a]会越界可能导致程序崩溃或进入死循环。务必根据题目数据范围精确设置N。可能原因在每次查询中重复计算逆元。确认你的代码结构是“一次预处理init() 多次调用C(a,b)”。如果误把预处理过程尤其是快速幂求infact[N]放到了查询函数里复杂度就退化成了 O(q log p)。错误答案全为0可能原因fact[0]或infact[0]未初始化为1。这会导致后续所有递推值都为0。调试建议写一个简单的暴力程序用于小数据范围n20内验证你的优化算法是否正确。用几组随机的小数据对拍能快速定位逻辑错误。5.2 方法扩展当 p 不是质数时怎么办本文方法的核心依赖于费马小定理它要求模数p必须是质数。如果p不是质数比如p10007这是个质数假设它不是我们该如何求组合数模p呢有几种常见思路扩展欧几里得算法求逆元费马小定理只是求逆元的一种方法且要求p是质数。更通用的求逆元方法是扩展欧几里得算法它只要求待求逆的数a与模数p互质即gcd(a, p) 1。在组合数计算中m!和(n-m)!可能与p不互质如果p有因子出现在这些阶乘里此时逆元甚至可能不存在。所以这种方法也有局限性。质因数分解法将组合数C(n, m)的分子分母进行质因数分解在模p意义下约分后再计算乘积。这种方法比较通用但实现较为复杂。Lucas定理当p是质数时Lucas定理可以将大组合数C(n, m)分解为若干个小组合数C(n_i, m_i)的乘积其中n_i, m_i是n, m在p进制下的各位数字。这常用于n, m非常大远超p但p本身不大的情况。它需要预处理出0到p-1的阶乘和逆元。中国剩余定理 (CRT)如果p可以分解为若干互质的因子如p p1^a1 * p2^a2我们可以分别计算C(n, m) mod p1^a1和C(n, m) mod p2^a2然后用中国剩余定理合并结果。这是解决非质数模数组合数问题最强大的通用方法但实现难度最高。对于算法竞赛最常考的仍然是模质数的情况尤其是1e97。掌握本文的预处理逆元法足以应对 90% 以上的相关问题。5.3 一个思维挑战如何优化空间我们的算法需要O(2N)的空间来存储fact和infact数组。如果N非常大比如1e7内存可能成为瓶颈两个long long数组需要约 160MB。有没有办法只用一个数组有一种思路是只预处理fact数组查询时用快速幂计算infact[m]和infact[n-m]。这回到了我们最初的基础优化版查询是 O(log p)。这是一种典型的时间-空间权衡。另一种更巧妙的思路是利用公式infact[i] fact[i]^(p-2)我们可以在查询时用快速幂实时计算。但这样并没有节省空间只是省了infact数组却增加了查询时间。真正的优化需要结合具体问题。例如如果查询的m和n-m范围有限我们可以只预处理这个范围内的infact。在实际应用中N1e5时两个数组占用的内存很小约 1.6MB完全不需要担心。这里提出这个问题是为了启发你在设计算法时时刻保有对时间复杂度和空间复杂度的双重考量。最后我个人在刷题和教学中的体会是组合数预处理这个技巧其价值远超一道题。它完美诠释了“预处理”和“空间换时间”的思想。当你下次遇到需要频繁查询某个函数值的问题时不妨先想想这个函数能不能拆解成几个可以预先计算好的部分有没有递推关系可以让我线性地填充一个查询表这种思维转换是算法能力提升的一个重要标志。
1. 项目概述从暴力到优雅的质变组合数计算这个在算法竞赛和面试中老生常谈的问题听起来似乎平平无奇。不就是 C(n, m) n! / (m! * (n-m)!) 吗很多新手朋友拿到题目第一反应可能就是直接套公式写个阶乘函数一除就完事了。但当你真正在 AcWing 886 这类题目里面对高达 10^5 次的查询和 10^5 量级的 n 与 m 时这种天真的想法会立刻让你体会到什么是“超时到绝望”。我最初也踩过这个坑以为算法题考的是数学公式后来才明白它真正考的是如何将数学知识转化为高效、可工程化的计算过程。“求组合数 II”这个标题其核心领域是算法竞赛中的数论与组合数学更具体点是模运算下的组合数高效计算。潜在需求非常明确在模数 p通常是质数如 1e97下需要应对海量10^5 量级的组合数查询每次查询必须达到近乎 O(1) 的响应速度。直接计算阶乘再除法即使每一步都取模单次查询的复杂度也是 O(n)对于 10^5 次查询就是 O(n^2)完全不可接受。因此标题中提到的“预处理优化的O(n)版本”就是破局的关键。它不是一个奇技淫巧而是一种标准的、必须掌握的预处理思想Precomputation和模逆元Modular Inverse技术的结合应用。简单来说它的核心思路是把昂贵的、重复的计算提前做好存起来用空间换时间。我们预先计算出所有可能用到的阶乘值fact[i]和阶乘的模逆元infact[i]这样每次查询 C(n, m) 时只需要一次查表O(1)和两次乘法、一次取模操作就能得到结果。这个“O(n)”指的是预处理阶段的复杂度查询本身是 O(1) 的。这不仅仅是解一道题更是一种重要的算法优化范式。它适用于任何需要频繁查询固定范围内某种函数值且该函数可分解为预计算量的组合的场景。理解并掌握它能让你在面对类似“大量查询斐波那契数列第n项”、“大量查询前缀和”等问题时拥有降维打击的思维工具。2. 核心思路与数学原理拆解2.1 为什么直接算阶乘不行模运算下的除法陷阱我们先回顾最直接的公式C(n, m) n! / (m! * (n-m)!)。 在普通整数运算下这没问题。但题目通常要求结果对一个质数p如1e97取模。我们学过模运算的基本规则(a b) % p (a % p b % p) % p(a * b) % p (a % p * b % p) % p但是没有(a / b) % p (a % p / b % p) % p这条规则因为模运算下的“除法”定义完全不同。在模p的世界里我们要把 “除以 b” 转化为 “乘以 b 的乘法逆元”。b 的乘法逆元inv(b)满足b * inv(b) ≡ 1 (mod p)。 所以a / b (mod p)等价于a * inv(b) (mod p)。因此组合数公式在模p下正确的形式是C(n, m) ≡ n! * inv(m!) * inv((n-m)!) (mod p)这里inv(x)表示 x 在模 p 下的乘法逆元。问题转化为如何高效计算n!以及n!的逆元2.2 破局关键费马小定理与快速幂求逆元既然 p 是质数本题通常保证是质数我们可以请出数论中的一位“老朋友”——费马小定理。 费马小定理指出若 p 是质数且整数 a 不是 p 的倍数则a^(p-1) ≡ 1 (mod p)。 由此可以推出a * a^(p-2) ≡ 1 (mod p)。 对比逆元的定义a * inv(a) ≡ 1 (mod p)我们得到inv(a) ≡ a^(p-2) (mod p)。这意味着对于任意非零的 a在模 p 意义下我们可以通过计算a^(p-2) mod p来得到它的逆元。计算幂次我们又有另一位“老朋友”——快速幂算法它可以在 O(log p) 的时间复杂度内完成计算。所以最基础的优化版本呼之欲出预处理出所有fact[i] i! % p然后对于每次查询 C(n, m)我们用公式C(n, m) fact[n] * quick_pow(fact[m], p-2) * quick_pow(fact[n-m], p-2) % p其中quick_pow是快速幂函数。这个算法单次查询的复杂度是 O(log p)因为要算两次快速幂。对于 10^5 次查询总复杂度约为 O(2 * 10^5 * log(1e97))大约在 10^7 量级在C中通常可以勉强通过但并非最优且常数较大。2.3 终极优化线性预处理阶乘逆元“预处理优化的O(n)版本”的精髓就在于把quick_pow也通过预处理消除掉让查询真正变成 O(1)。我们不仅预处理阶乘数组fact[N]还预处理阶乘的逆元数组infact[N]。使得infact[i] ≡ inv(i!) (mod p)。那么组合数公式就变成了C(n, m) fact[n] * infact[m] * infact[n-m] % p查询时只需要三次乘法和一次取模。现在核心问题变成如何高效地预处理出infact数组如果对每个 i 都用快速幂计算inv(i!)那预处理复杂度就是 O(n log p)和上面基础版没区别。这里用到了一个非常巧妙的递推关系。 我们知道fact[i] fact[i-1] * i % p对于逆元我们能否找到类似的关系有的。目标已知infact[i] inv(i!)求infact[i-1]。 根据定义i! * infact[i] ≡ 1 (mod p)而i! (i-1)! * i所以(i-1)! * i * infact[i] ≡ 1 (mod p)观察这个式子(i-1)!的逆元infact[i-1]应该满足(i-1)! * infact[i-1] ≡ 1。 对比上下两式我们可以得到infact[i-1] ≡ i * infact[i] (mod p)这是一个从后向前的递推式也就是说如果我们能先求出infact[n]最大的那个就可以用infact[i-1] i * infact[i] % p这个公式一路倒着推回来线性时间内填满整个infact数组。那么infact[n]怎么求用一次快速幂即可infact[n] quick_pow(fact[n], p-2)。预处理流程总结fact[0] 1;// 0的阶乘定义为1正推计算fact[i] fact[i-1] * i % p(i从1到N)计算infact[N] quick_pow(fact[N], p-2)// 只做一次快速幂倒推计算infact[i-1] infact[i] * i % p(i从N down to 1)同样定义infact[0] 1;// 0的阶乘逆元也是1整个预处理过程的时间复杂度是 O(N)空间复杂度是 O(N)。之后的海量查询每次都是 O(1)。实操心得很多朋友在推导infact[i-1]的递推式时会卡住。一个记忆技巧是infact数组是“阶乘”的逆元所以它的递推必然和“乘法”有关而且是“除回去”的感觉。从infact[i]到infact[i-1]相当于把i这个因子从“整体逆元”中“拿出去”所以需要乘以i。多推演几遍就能形成直觉。3. 代码实现与逐行解析理解了数学原理我们来看 C 实现。这里假设模数MOD 1e97预处理的最大范围N 100005根据题目要求调整。3.1 数据结构定义与初始化#include iostream using namespace std; typedef long long LL; // 使用long long防止乘法溢出 const int N 100010; // 预处理的最大范围通常比题目数据范围稍大 const int MOD 1e9 7; // 常用质数模数 LL fact[N]; // fact[i] i! % MOD LL infact[N]; // infact[i] (i!)^(-1) % MOD // 快速幂模板函数计算 a^k % p LL qmi(LL a, LL k, LL p) { LL res 1; while (k) { if (k 1) res res * a % p; a a * a % p; k 1; } return res; } // 预处理函数 void init() { 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; // 注意这里的下标关系 // 公式是 infact[i] infact[i1] * (i1) % MOD // 因为我们的递推式是 infact[i-1] infact[i] * i % MOD // 将 i 替换为 i1得到 infact[i] infact[i1] * (i1) % MOD } }代码解析与注意事项typedef long long LL这是关键中的关键。fact和infact在计算过程中会进行乘法即使对MOD取模中间结果也可能超过int范围约21亿。1e97这个模数本身就和int最大值很接近两个这样的数相乘肯定会溢出。long long可以安全地容纳中间结果。快速幂函数qmi这是标准写法。a a * a % p这一行同样要注意使用LL类型或者将a声明为LL。预处理范围N务必根据题目给出的n的最大可能值来设置。通常设为100010或200010比题目上限100000大一点防止边界错误。这是一个非常常见的“踩坑点”。倒推循环for (int i N - 2; i 0; i -- )为什么从N-2开始因为infact[N-1]我们已经用快速幂求出来了。循环体内是infact[i] infact[i 1] * (i 1) % MOD这对应了推导公式infact[i-1] infact[i] * i % MOD。你可以这样理解当循环变量为i时我们正在计算infact[i]它等于infact[i1]已经算好的后一项乘以(i1)。初始化fact[0] infact[0] 1这是数学定义。0的阶乘是11在模任何数下的逆元也是1。这保证了公式C(n, 0) C(n, n) fact[n] * infact[0] * infact[n] % MOD 1的正确性。3.2 查询函数与主程序逻辑预处理完成后查询就变得异常简单。// 查询组合数 C(a, b) % MOD LL C(int a, int b) { if (b a) return 0; // 组合数定义如果下项大于上项结果为0 // 核心查询公式O(1) 时间复杂度 return fact[a] * infact[b] % MOD * infact[a - b] % MOD; } int main() { init(); // 程序开始先调用一次预处理一劳永逸 int n; scanf(“%d”, n); // 查询次数 while (n -- ) { int a, b; scanf(“%d%d”, a, b); printf(“%lld\n”, C(a, b)); // 注意输出格式为 long long } return 0; }查询函数C(a, b)的细节边界检查if (b a) return 0;这是组合数的数学性质。虽然题目可能保证输入合法但加上这一步是良好的编程习惯使函数更健壮。乘法的取模顺序return fact[a] * infact[b] % MOD * infact[a - b] % MOD;这里为什么分两次取模而不是写成(fact[a] * infact[b] * infact[a - b]) % MOD 原因是防止溢出。即使fact[a]和infact[b]都在MOD以内它们相乘的结果可能超出long long范围吗1e97约等于1e9两个1e9相乘是1e18这在long long约9e18的安全范围内。但三个1e9相乘就是1e27远超long long范围会导致溢出。因此每乘一次就取一次模是最安全的写法。fact[a] * infact[b] % MOD的结果肯定小于MOD再乘以一个小于MOD的数结果小于1e18在long long安全范围内最后再取模。printf(“%lld\n”, C(a, b));由于函数返回类型是LL即long long输出时必须使用%lld格式符。在部分OJ或编译器环境下使用%d输出long long会导致错误结果这是一个隐蔽的坑。避坑指南在实际竞赛或面试中我强烈建议将组合数查询函数写成一个“万能”版本包含更多的边界检查例如判断b 0的情况。虽然题目可能不考但这体现了思维的严密性。此外如果模数p不是质数费马小定理失效这套方法就行不通了需要改用扩展欧几里得算法求逆元或者使用其他方法如Lucas定理。所以在应用此方法前务必确认p是质数这一前提条件。4. 算法性能分析与对比为了让你更直观地理解“预处理O(n)版本”的优势我们将其与几种常见方法进行对比。方法预处理时间复杂度单次查询时间复杂度适用场景优缺点暴力计算(公式取模)无O(n)n, m 非常小 (n 20)实现简单但完全无法应对大数据。基础优化(阶乘快速幂求逆)无O(log p)查询次数较少 (q 1000)无需预处理节省空间。查询成本尚可但q大了就慢。递推法(使用公式 C(n,m)C(n-1,m)C(n-1,m-1))O(n²)O(1)n, m 较小 (n 2000)查询极快但预处理是平方级空间也是 O(n²)限制大。预处理阶乘与逆元 (本文方法)O(n)O(1)n 较大 (n ≤ 1e5)查询量巨大 (q ≤ 1e5)空间 O(n)预处理线性查询常数。是此类问题的标准答案。Lucas定理无或 O(p)O(log_p n)n, m 巨大 (1e9)但模数 p 较小 (p ≤ 1e5)处理n,m远大于模数的情况是另一种维度的武器。从对比可以看出当问题规模落在“n 在 1e5 量级查询次数 q 也在 1e5 量级”这个典型区间时O(n) 预处理 O(1) 查询的方案在时间复杂度和空间复杂度上取得了完美的平衡。复杂度计算示例假设n_max 100000,q 100000,MOD 1e97。预处理阶段计算fact数组需要 1e5 次乘法和取模计算infact[N-1]需要一次O(log MOD) ≈ 30次运算的快速幂倒推infact数组又需要 1e5 次运算。总计约2 * 10^5 30次运算在 C 中瞬间完成。查询阶段每次查询 3 次乘法、2 次取模总计5 * 10^5次运算同样飞快。 整个程序的总运算量在10^6量级现代 CPU 可以在零点几秒内完成。如果使用基础优化版每次查询做两次快速幂单次查询约 60 次运算总查询运算量达6 * 10^6虽然也可能通过但常数大了很多在时间限制严格的题目中可能处于临界状态。而递推法的 O(n²) 预处理需要 1e10 次运算完全不可行。5. 典型问题排查与扩展思考5.1 常见错误与调试技巧即使理解了原理实现时也可能遇到各种问题。下面是我和学员们常踩的坑错误输出错误或负数可能原因1最常见乘法溢出。检查所有*运算符的两边是否都是long long类型。在fact[i] fact[i - 1] * i % MOD中如果fact[i-1]是inti也是int相乘的结果会先以int计算此时就可能已经溢出然后再转换为long long取模为时已晚。确保fact数组是LL类型并且i在乘法前被强制转换或确保表达式以LL类型计算。一种安全的写法是fact[i] fact[i - 1] * (LL)i % MOD。可能原因2取模遗漏或顺序错误。确保每一步可能溢出的乘法后面都紧跟了% MOD。回顾我们查询函数的写法。可能原因3infact数组递推公式写反。记住是infact[i-1] infact[i] * i % p即用“大的”阶乘逆元去推导“小的”。如果写成了infact[i] infact[i-1] * i % p就错了因为infact[i-1]是(i-1)!的逆元乘以i得到的是( (i-1)! * i )^(-1) (i!)^(-1) / i并不是infact[i]。错误运行超时 (TLE)可能原因预处理范围N设置过大或过小。如果N设置得远超题目需要的最大值例如设为1e6预处理本身就会消耗较多时间。如果N设置小了当查询的a大于N时访问fact[a]会越界可能导致程序崩溃或进入死循环。务必根据题目数据范围精确设置N。可能原因在每次查询中重复计算逆元。确认你的代码结构是“一次预处理init() 多次调用C(a,b)”。如果误把预处理过程尤其是快速幂求infact[N]放到了查询函数里复杂度就退化成了 O(q log p)。错误答案全为0可能原因fact[0]或infact[0]未初始化为1。这会导致后续所有递推值都为0。调试建议写一个简单的暴力程序用于小数据范围n20内验证你的优化算法是否正确。用几组随机的小数据对拍能快速定位逻辑错误。5.2 方法扩展当 p 不是质数时怎么办本文方法的核心依赖于费马小定理它要求模数p必须是质数。如果p不是质数比如p10007这是个质数假设它不是我们该如何求组合数模p呢有几种常见思路扩展欧几里得算法求逆元费马小定理只是求逆元的一种方法且要求p是质数。更通用的求逆元方法是扩展欧几里得算法它只要求待求逆的数a与模数p互质即gcd(a, p) 1。在组合数计算中m!和(n-m)!可能与p不互质如果p有因子出现在这些阶乘里此时逆元甚至可能不存在。所以这种方法也有局限性。质因数分解法将组合数C(n, m)的分子分母进行质因数分解在模p意义下约分后再计算乘积。这种方法比较通用但实现较为复杂。Lucas定理当p是质数时Lucas定理可以将大组合数C(n, m)分解为若干个小组合数C(n_i, m_i)的乘积其中n_i, m_i是n, m在p进制下的各位数字。这常用于n, m非常大远超p但p本身不大的情况。它需要预处理出0到p-1的阶乘和逆元。中国剩余定理 (CRT)如果p可以分解为若干互质的因子如p p1^a1 * p2^a2我们可以分别计算C(n, m) mod p1^a1和C(n, m) mod p2^a2然后用中国剩余定理合并结果。这是解决非质数模数组合数问题最强大的通用方法但实现难度最高。对于算法竞赛最常考的仍然是模质数的情况尤其是1e97。掌握本文的预处理逆元法足以应对 90% 以上的相关问题。5.3 一个思维挑战如何优化空间我们的算法需要O(2N)的空间来存储fact和infact数组。如果N非常大比如1e7内存可能成为瓶颈两个long long数组需要约 160MB。有没有办法只用一个数组有一种思路是只预处理fact数组查询时用快速幂计算infact[m]和infact[n-m]。这回到了我们最初的基础优化版查询是 O(log p)。这是一种典型的时间-空间权衡。另一种更巧妙的思路是利用公式infact[i] fact[i]^(p-2)我们可以在查询时用快速幂实时计算。但这样并没有节省空间只是省了infact数组却增加了查询时间。真正的优化需要结合具体问题。例如如果查询的m和n-m范围有限我们可以只预处理这个范围内的infact。在实际应用中N1e5时两个数组占用的内存很小约 1.6MB完全不需要担心。这里提出这个问题是为了启发你在设计算法时时刻保有对时间复杂度和空间复杂度的双重考量。最后我个人在刷题和教学中的体会是组合数预处理这个技巧其价值远超一道题。它完美诠释了“预处理”和“空间换时间”的思想。当你下次遇到需要频繁查询某个函数值的问题时不妨先想想这个函数能不能拆解成几个可以预先计算好的部分有没有递推关系可以让我线性地填充一个查询表这种思维转换是算法能力提升的一个重要标志。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
