从阶乘逆元到组合数计算：一个公式打通LeetCode刷题效率瓶颈

从阶乘逆元到组合数计算一个公式打通LeetCode刷题效率瓶颈在算法竞赛和LeetCode刷题中组合数计算是许多动态规划和数论问题的核心操作。想象一下这样的场景你正在解决一个需要频繁计算C(n, m) mod p的问题每次调用都要重新计算阶乘和逆元时间复杂度直接拉满。有没有一种方法能让我们像查表一样快速获取组合数这就是阶乘逆元预处理的魔力。1. 为什么需要阶乘逆元优化组合数计算的传统方式是直接套用公式C(n, m) n! / (m! × (n-m)!)但在模运算的世界里除法需要转换为乘以逆元。每次计算都要重新求逆元时间复杂度高达O(log p)这在需要大量组合数查询的场景下会成为性能瓶颈。典型应用场景动态规划中的路径计数问题概率与统计相关的题目排列组合类数论问题需要大量预处理组合数的竞赛题目提示当题目要求对组合数取模且n的范围在1e5以上时阶乘逆元预处理几乎是必选方案2. 构建阶乘与逆元查询系统2.1 预处理阶乘数组首先我们需要建立阶乘数组fact和逆元数组inv_factMOD 10**9 7 max_n 10**5 # 根据题目调整 # 初始化阶乘数组 fact [1] * (max_n 1) for i in range(1, max_n 1): fact[i] fact[i-1] * i % MOD2.2 线性递推求逆元利用数论中的线性递推公式我们可以在O(n)时间内求出所有逆元inv[i] (MOD - MOD // i) * inv[MOD % i] % MODPython实现示例inv [1] * (max_n 1) for i in range(2, max_n 1): inv[i] (MOD - MOD // i) * inv[MOD % i] % MOD2.3 构建阶乘逆元数组有了单个数的逆元后阶乘逆元可以通过递推得到inv_fact [1] * (max_n 1) inv_fact[max_n] pow(fact[max_n], MOD-2, MOD) # 费马小定理求最大阶乘逆元 for i in range(max_n - 1, -1, -1): inv_fact[i] inv_fact[i 1] * (i 1) % MOD3. 组合数查询的O(1)实现完成上述预处理后组合数查询变得极其高效def comb(n, m): if n m or m 0: return 0 return fact[n] * inv_fact[m] % MOD * inv_fact[n - m] % MOD性能对比方法预处理时间单次查询时间适合场景传统方法无O(log p)少量查询阶乘逆元O(n)O(1)大量查询4. 实战应用与避坑指南4.1 LeetCode例题解析以62. 不同路径为例组合数解法可以直接套用我们的模板class Solution: def uniquePaths(self, m: int, n: int) - int: # 预处理阶乘和逆元 total m n - 2 return comb(total, min(m-1, n-1))4.2 常见问题排查模数不是质数此时费马小定理失效需要改用扩展欧几里得算法求逆元数组越界确保max_n大于题目中可能的n最大值初始化错误记住fact[0] inv_fact[0] 1负数处理在模运算中负数结果需要加上MOD再取模4.3 性能优化技巧双模数处理对大质数模数可以用两个不同模数然后CRT合并结果懒加载如果n的范围不确定可以实现按需扩展数组内存优化对于极大n可以只存储必要的阶乘和逆元5. 进阶应用多项式与生成函数预处理阶乘和逆元的技巧在生成函数计算中同样威力巨大。例如计算多项式乘积时def multiply_poly(a, b, MOD): n len(a) m len(b) res [0] * (n m - 1) for i in range(n): for j in range(m): res[ij] (res[ij] a[i] * b[j] % MOD * comb(ij, i)) % MOD return res这种技巧在解决某些计数问题时能大幅简化计算过程。