从阶乘逆元到组合数计算：一个公式打通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_fact：

MOD = 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 % MOD

2.2 线性递推求逆元

利用数论中的线性递推公式，我们可以在O(n)时间内求出所有逆元：

inv[i] = (MOD - MOD // i) * inv[MOD % i] % MOD

Python实现示例：

inv = [1] * (max_n + 1) for i in range(2, max_n + 1): inv[i] = (MOD - MOD // i) * inv[MOD % i] % MOD

2.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) % MOD

3. 组合数查询的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

性能对比：

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 常见问题排查

1. 模数不是质数：此时费马小定理失效，需要改用扩展欧几里得算法求逆元
2. 数组越界：确保max_n大于题目中可能的n最大值
3. 初始化错误：记住fact[0] = inv_fact[0] = 1
4. 负数处理：在模运算中，负数结果需要加上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[i+j] = (res[i+j] + a[i] * b[j] % MOD * comb(i+j, i)) % MOD return res

这种技巧在解决某些计数问题时能大幅简化计算过程。