在算法竞赛和日常编程中，组合数学是一个绕不开的话题。而求组合数 $C_n^m$（即从 $n$ 个元素中选出 $m$ 个元素的方案数）更是基础中的基础。
虽然数学公式 $C_n^m = \frac{n!}{m!(n-m)!}$ 看起来很简单，但在计算机中实现时，我们必须根据 $n, m$ 的数据范围 以及 模数 $p$ 的性质 来选择不同的算法，否则很容易面临 超时（TLE） 或 爆 long long 的问题。
本文总结了四种常见的组合数求法，帮你搞定所有场景。
核心公式
$$ C_n^m = \frac{A_n^m}{m!} = \frac{n!}{m!(n-m)!} $$
$$ C_n^m = C_{n-1}^m + C_{n-1}^{m-1} \quad (\text{杨辉三角递推性质}) $$
方法一：递推法（杨辉三角）
1. 适用场景 (When)
- 数据范围：
n, m较小，通常1 <= n <= 2000。 - 查询次数：查询次数
q很多（例如q <= 10^5）。 - 模数：可以是任意数，不需要是质数。
2. 核心原理 (Why)
基于组合数的递推性质 C(n, k) = C(n-1, k) + C(n-1, k-1)。
这就好比动态规划，我们可以预处理出一个二维数组（杨辉三角），之后查询只需要 O(1) 。因为只涉及加法，所以不用担心除法求逆元的问题。
3. 代码实现
const int N = 2010;
const int MOD = 1e9 + 7;
long long c[N][N];
void init() {
for (int i = 0; i < N; i++) {
c[i][0] = 1; // 边界情况
for (int j = 1; j <= i; j++) {
// C(i, j) = C(i-1, j) + C(i-1, j-1)
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
}
}
}方法二：预处理阶乘 + 乘法逆元
1. 适用场景 (When)
- 数据范围：
n较大，通常1 <= n <= 10^6。 - 查询次数：查询次数
q很多（例如q <= 10^5）。 - 模数：
p必须是质数，且p > n。
2. 核心原理 (Why)
利用公式 C(n, m) = n! / (m! * (n-m)!) % p 。
在模运算下，除以一个数等于乘以这个数的逆元。因为 p 是质数，我们可以根据费马小定理，数 x 的逆元就是 x^(p-2) % p 。
我们通过 $O(n)$ 的预处理计算出：
- 阶乘表
f[]：f[i] = i!。 - 阶乘逆元表
g[]：先用快速幂算出最大值n!的逆元，然后利用公式inv(i!) = inv((i+1)!) * (i+1)倒推算出所有阶乘的逆元 。
查询时仅需 O(1) 的时间复杂度。
3. 代码实现
typedef long long LL;
const int N = 100010; // 根据题目要求调整大小
int n, p; // 全局变量存储范围和模数
LL f[N], g[N]; // f: 阶乘, g: 阶乘逆元
// 快速幂求逆元: a^(p-2) % p
LL qpow(LL a, LL b, LL p)
{
LL ret = 1;
while(b)
{
if(b & 1) ret = ret * a % p;
a = a * a % p;
b >>= 1;
}
return ret;
}
void init()
{
// 1. 预处理阶乘
f[0] = 1;
for(int i = 1; i <= n; i++)
{
f[i] = f[i - 1] * i % p;
}
// 2. 预处理阶乘的逆元
// 先利用费马小定理算出最大值 n! 的逆元
g[n] = qpow(f[n], p - 2, p);
// 再逆向递推算出其他阶乘的逆元: inv(i!) = inv((i+1)!) * (i+1)
for(int i = n - 1; i >= 0; i--)
{
g[i] = (i + 1) * g[i + 1] % p;
}
}
// 查询组合数
LL C(int n, int m)
{
if(n < m) return 0;
// C(n, m) = n! * inv((n-m)!) * inv(m!)
return f[n] * g[n - m] % p * g[m] % p;
}方法三：直接定义法（循环求解）
1. 适用场景 (When)
- 数据范围：
m较小，或者单次查询。 - 模数：
p为质数且p > n。 - 特点：不想写复杂的预处理，或者
n虽大但m很小。
2. 核心原理 (Why)
直接利用定义：
$$ C_n^m = \frac{n \times (n-1) \times \dots \times (n-m+1)}{m!} $$
一边循环乘分子，一边计算分母 m! 的逆元。时间复杂度仅为 O(m)。
3. 代码实现
// 快速幂求逆元
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;
}
LL C(int n, int m, int p) {
if (m > n) return 0;
LL up = 1, down = 1;
// 循环计算分子和分母
for (int i = 1; i <= m; i++) {
up = up * (n - i + 1) % p;
down = down * i % p;
}
// 结果 = 分子 * 分母的逆元
return up * qmi(down, p - 2, p) % p;
}方法四：卢卡斯定理 (Lucas Theorem)
1. 适用场景 (When)
- 数据范围：
n, m极其巨大，例如1 <= n <= 10^18。 - 模数：
p是较小的质数（例如1 <= p <= 10^5）。
2. 核心原理 (Why)
n 太大导致无法预处理阶乘数组，但模数 p 很小。
卢卡斯定理将大组合数递归转化为小组合数的乘积：
$$ C_n^m \equiv C_{n \pmod p}^{m \pmod p} \times C_{n/p}^{m/p} \pmod p $$
递归边界是当 m=0 时返回 1。对于 n % p 这种小范围的组合数，可以直接用定义法求解。
3. 代码实现
typedef long long LL;
int 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;
}
// 定义法求小范围组合数 C(a, b) % p
LL C(int a, int b, int p) {
if (b > a) return 0;
LL res = 1;
// 相当于计算 (a * ... * (a-b+1)) / b!
for (int i = 1, j = a; i <= b; i++, j--) {
res = res * j % p;
res = res * qmi(i, p - 2, p) % p;
}
return res;
}
// 卢卡斯定理递归
LL lucas(LL n, LL m, int p) {
if (m == 0) return 1;
return lucas(n / p, m / p, p) * C(n % p, m % p, p) % p;
}总结：如何选择算法？（决策速查表）
| 数据范围 | 模数 $p$ | 特点 | 推荐算法 | 时间复杂度 |
|---|---|---|---|---|
| $n, m \le 2000$ | 任意 | 查询次数多 | 方法一：递推法 (杨辉三角) | 预处理 $O(n^2)$，查询 $O(1)$ |
| $n \le 10^6$ | 大质数 ($p>n$) | 标准情况 | 方法二：预处理阶乘 | 预处理 $O(n)$，查询 $O(1)$ |
| $n \le 10^{18}, m \le 10^5$ | 大质数 ($p>n$) | $m$ 很小，不想预处理 | 方法三：直接定义法 | 查询 $O(m \log p)$ |
| $n, m \le 10^{18}$ | 小质数 ($p \le 10^5$) | $n, m$ 巨大，$p$ 较小 | 方法四：卢卡斯定理 | $O(p + \log_p n)$ |
| $n \le 10^6$ | 非质数 或 无模数 | 需高精度或合数模 | 补充方法：分解质因数法 | 视具体实现而定 |