C++算法
组合数学入门：核心概念与 4 种求组合数方法
组合数学核心概念涵盖计数原理、排列组合及二项式定理。针对求组合数问题，提供四种解法：循环直接计算适合单次查询且 m 较小；杨辉三角打表适合 n 较小多次查询；阶乘加逆元表适合 n 较大多次查询且模数为质数；卢卡斯定理适合 n 极大且模数为质数的情况。通过对比各方法的适用场景、时间复杂度及空间限制，指导根据具体数据范围选择最优算法方案。
组合数学核心概念涵盖计数原理、排列组合及二项式定理。针对求组合数问题，提供四种解法：循环直接计算适合单次查询且 m 较小；杨辉三角打表适合 n 较小多次查询；阶乘加逆元表适合 n 较大多次查询且模数为质数；卢卡斯定理适合 n 极大且模数为质数的情况。通过对比各方法的适用场景、时间复杂度及空间限制，指导根据具体数据范围选择最优算法方案。
在编程世界里，组合数学是算法竞赛和实际开发中概率统计场景的基础。其核心在于对计数原理、排列组合、二项式定理的深刻理解，以及灵活运用各种方法求解组合数。
本文从基础概念入手，拆解组合数学的核心知识点，聚焦'求组合数'这一高频考点，详细讲解 4 种不同场景下的最优解法。
计数原理包含两个核心：加法原理和乘法原理。
定义：如果完成一个事件有 n 类独立的方法，第 i 类方法有 a_i 种具体实现，那么完成这个事件的总方法数就是所有类别方法数的和。
（也就是 a₁+a₂+...+aₙ）。
通俗理解：就像去餐厅吃饭，主食有米饭、面条、馒头 3 种选择，任选一种就能解决主食问题，总选择数就是 3 种，这就是加法原理的直观体现——'分类选择，选一个就够'。
定义：如果完成一个事件需要 n 个连续的步骤，第 i 个步骤有 a_i 种实现方式，那么完成这个事件的总方法数就是所有步骤方法数的乘积。
（也就是 a₁×a₂×...×aₙ）。
通俗理解：要是不仅选主食，还要选菜。主食有 3 种，菜有 4 种，那么一顿饭的搭配方案就是 3×4=12 种——因为先选主食（3 种选择），再选菜（4 种选择），两个步骤必须都完成，才能构成一顿完整的饭，这就是'分步执行，缺一不可'。
题目：书架上有不同的数学书 3 本，不同的物理书 4 本，不同的化学书 5 本。
问题 1：从中任取一本，有多少种不同的取法？ 解答：取一本书属于'分类选择'，数学书、物理书、化学书是三类独立的选择，用加法原理：3+4+5=12 种。 问题 2：从中每种各取一本，有多少种不同的取法？ 解答：每种各取一本需要分三步——先取数学书（3 种），再取物理书（4 种），最后取化学书（5 种），用乘法原理：3×4×5=60 种。
这两个问题清晰地展示了加法原理和乘法原理的区别：加法原理对应'分类'，乘法原理对应'分步'。
排列组合主要研究'从 n 个不同元素中选取 m 个元素'的计数问题，关键区别在于'选取的元素是否有序'。
定义：从 n 个不同的元素中，任取 m 个元素（m≤n）排成一列，所有可能的取法个数称为排列数，记作 P(n,m)。
计算公式：
（注：n! 表示 n 的阶乘，即 n×(n-1)×...×1；0! 规定为 1）
理解：排列强调'顺序'。比如从 1、2、3、4 四个数中选 3 个排成一列，123 和 321 是不同的排列，因为顺序不同。计算时，第一个位置有 n 种选择，第二个位置有 n-1 种（选了一个元素后剩下的），以此类推，直到选够 m 个位置，所以是 m 个连续整数的乘积。
示例：计算 P(4,3)
按照公式：
=(4−3)! / 4!=4×3×2×1 / 1=4×3×2=24 种，和直观枚举的结果一致。
定义：从 n 个不同的元素中，任取 m 个元素（m≤n）组成一组（不考虑顺序），所有可能的取法个数称为组合数，记作 C(n,m) 或 (n choose m)。
计算公式：
理解：组合不考虑顺序，只关注'选了哪些元素'。比如从 1、2、3、4 中选 3 个元素，{1,2,3} 和 {3,2,1} 是同一个组合。因此，组合数是排列数除以 m!（m 个元素的全排列数，即消除顺序带来的重复计数）。
核心性质：
这个性质非常实用，比如计算 C(100,98) 时，直接用 C(100,2) 计算更简单（因为 100-98=2），大大减少计算量。
二项式定理揭示了 (a+b)ⁿ展开式的系数与组合数的关系，而杨辉三角则是二项式系数的直观表现形式。
公式：
其中，C(n,k) 就是二项式展开式中第 k+1 项的系数（称为二项式系数）。
示例：展开 (a+b)³
根据定理：
代入组合数计算：= 1×a³×1 + 3×a²×b + 3×a×b² + 1×1×b³= a³ + 3a²b + 3ab² + b³
杨辉三角是一个由数字组成的三角形，它的第 i 行（从 0 开始计数）恰好是 (a+b)ⁱ展开式的二项式系数。
杨辉三角的结构：
每行的首尾元素都是 1。
中间的每个元素等于它上方两个元素的和，即 C(n,m) = C(n-1,m-1) + C(n-1,m)。这个规律是后续用杨辉三角求组合数的理论基础。
杨辉三角的实用价值在于'打表'——可以提前预处理出一定范围内的所有二项式系数（即组合数），后续查询时直接取用，效率极高。
组合数的计算是算法题中的高频考点，但不同题目的数据范围差异很大，因此需要根据 n、m 的大小、查询次数等条件选择合适的方法。
直接利用组合数的计算公式：
由于计算结果需要取模（组合数通常很大），而除法取模不能直接计算，因此需要用乘法逆元来替代除法。根据费马小定理，当 p 是质数时，a 的逆元为 a^(p-2) mod p。
具体步骤：
计算分子：n×(n-1)×...×(n-m+1) mod p（共 m 项相乘）。 计算分母：m! mod p。 计算分母的乘法逆元（用快速幂实现）。 组合数结果 = 分子 × 逆元 mod p。
#include <iostream>
using namespace std;
typedef long long LL;
// 快速幂：计算 a^b mod 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;
}
// 计算 C(n, m) mod p，p 为质数且 p > n
LL C(int n, int m, int p) {
if (n < m) return 0;
LL up = 1, down = 1;
// 计算分子：n*(n-1)*...*(n-m+1) mod p
for (LL i = n - m + 1; i <= n; ++i) {
up = up * i % p;
}
// 计算分母：m! mod p
for (LL i = 2; i <= m; ++i) {
down = down * i % p;
}
// 分母的逆元：down^(p-2) mod p
LL inv_down = qpow(down, p - 2, p);
// 组合数 = 分子 * 逆元 mod p
return up * inv_down % p;
}
int main() {
// 测试：计算 C(5, 2) mod 1e9+7
int n = 5, m = 2, p = 1e9 + 7;
cout << C(n, m, p) << endl;
;
}
单次查询：O(m)，因为分子和分母各需要循环 m 次，快速幂的时间复杂度是 O(log p)。
优点：实现简单，无需预处理，适合单次查询或 m 较小的场景。 缺点：当 m 较大（比如 m=1e6）时，循环次数过多，效率较低；不适合多次查询。
利用杨辉三角的递推公式：
（边界条件：C(n,0)=1）。
提前预处理一个二维数组 f[n][m]，其中 f[n][m] 表示 C(n,m)，然后每次查询时直接返回 f[n][m] 即可，查询时间复杂度为 O(1)。
杨辉三角的递推本质是动态规划：f[i][j] 表示从 i 个元素中选 j 个的组合数，它可以由'不选第 i 个元素（从 i-1 个中选 j 个）'和'选第 i 个元素（从 i-1 个中选 j-1 个）'两种情况相加得到。由于 n≤2000，二维数组的大小是 2001×2001（约 400 万），空间占用很小，预处理时间也仅为 O(n²)。
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 2010;
LL f[N][N]; // f[n][m] = C(n, m) mod p
// 预处理杨辉三角，计算所有 C(n, m) mod p
void get_comb(int max_n, int p) {
// 边界条件：C(n, 0) = 1
for (int i = 0; i <= max_n; ++i) {
f[i][0] = 1;
}
// 递推计算杨辉三角
for (int i = 1; i <= max_n; ++i) {
for (int j = 1; j <= i; ++j) {
f[i][j] = (f[i-1][j] + f[i-1][j-1]) % p;
}
}
}
int main() {
int max_n = 2000, p = 1e9 + 7;
get_comb(max_n, p); // 预处理
// 多次查询示例
int q;
cin >> q;
while (q--) {
int n, m;
cin >> n >> m;
cout << (m > n ? 0 : f[n][m]) << endl;
}
return 0;
}
预处理：O(n²)。单次查询：O(1)。
优点：预处理后查询极快，适合多次查询、n 较小的场景。 缺点：n 的范围受限（n≤2000），当 n 较大时，二维数组会超内存。
利用组合数的阶乘公式：
要快速计算这个公式，需要提前预处理两个数组：
阶乘数组 f：f[i] = i! mod p。 阶乘逆元数组 g：g[i] = (i!)⁻¹ mod p。
根据费马小定理，g[n] = f[n]^(p-2) mod p。而逆元数组可以从后往前递推：g[i] = (i+1) × g[i+1] mod p。
具体步骤：
预处理阶乘数组 f[0...max_n]。 预处理阶乘逆元数组 g[0...max_n]。 每次查询时，若 m > n 则返回 0，否则返回 f[n] × g[m] % p × g[n-m] % p。
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
const int MOD = 1e9 + 7;
LL f[N]; // f[i] = i! mod MOD
LL g[N]; // g[i] = (i!)^{-1} mod MOD
// 快速幂：计算 a^b mod 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(int max_n) {
f[0] = 1;
for (int i = 1; i <= max_n; ++i) {
f[i] = f[i-1] * i % MOD;
}
// 预处理阶乘逆元数组：先计算 g[max_n]，再递推
g[max_n] = qpow(f[max_n], MOD - 2, MOD);
for (int i = max_n - 1; i >= 0; --i) {
g[i] = (LL)(i + 1) * g[i + 1] % MOD;
}
}
// 计算 C(n, m) mod MOD
LL C(int n, m) {
(n < m) ;
f[n] * g[m] % MOD * g[n - m] % MOD;
}
{
max_n = ;
(max_n);
q;
cin >> q;
(q--) {
n, m;
cin >> n >> m;
cout << (n, m) << endl;
}
;
}
预处理：O(n)。单次查询：O(1)。
优点：预处理效率高，查询速度快，适合 n 较大、多次查询的场景。 缺点：仅适用于 p 为质数且 p > n 的情况。
当 n 和 m 很大时，无法直接预处理阶乘数组，此时需要用卢卡斯定理（Lucas Theorem）来分解问题。
卢卡斯定理的核心公式：
（其中 p 为质数）
通俗理解：将 n 和 m 分别表示为 p 进制数，然后对每一位分别计算组合数，最后将结果相乘取模。
具体步骤：
递归分解：将 n 和 m 分别除以 p，得到商 n'=n/p、m'=m/p，余数 r=n% p、s=m% p。 计算低位组合数：C(r, s) mod p（r 和 s 都小于 p，可直接用方法一计算）。 递归计算高位组合数：C(n', m') mod p。 结果为两者的乘积 mod p。 递归终止条件：当 m=0 时，返回 1。
卢卡斯定理的本质是'分治'，将大数值的组合数分解为小数值的组合数计算。由于 p≤1e5，每次递归计算 C(r, s) 的时间复杂度是 O(p)，而递归深度是 O(log_p n)，总体时间复杂度为 O(p + log_p n)。
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL f[N]; // 阶乘数组
LL g[N]; // 阶乘逆元数组
// 快速幂：计算 a^b mod 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;
}
// 预处理阶乘和逆元数组（针对当前 p）
void init(LL p) {
int max_fact = p - 1;
f[0] = 1;
for (int i = 1; i <= max_fact; ++i) {
f[i] = f[i-1] * i % p;
}
g[max_fact] = qpow(f[max_fact], p - 2, p);
for (int i = max_fact - 1; i >= 0; --i) {
g[i] = (LL)(i + 1) * g[i + 1] % p;
}
}
// 计算 C(n, m) mod p，其中 n < p，m < p
LL C(LL n, LL m, LL p) {
if (n < m) return 0;
return f[n] * g[m] % p * g[n - m] % p;
}
{
(m == ) ;
(n / p, m / p, p) * (n % p, m % p, p) % p;
}
{
T;
cin >> T;
(T--) {
LL n, m, p;
cin >> n >> m >> p;
(p);
cout << (n, m, p) << endl;
}
;
}
预处理：O(p)。递归查询：O(log_p n)。
优点：解决了大数值 n 和 m 的组合数计算问题，适用范围极广。 缺点：实现相对复杂，需要理解递归分治的思想。
为了方便大家在实际题目中快速选择合适的方法，这里整理了 4 种方法的核心参数对比：
| 方法 | 适用场景 | 时间复杂度 | 空间复杂度 | 核心限制 |
|---|---|---|---|---|
| 循环直接计算 | 单次查询、m 较小 | O(m) | O(1) | p 为质数且 p > n |
| 杨辉三角打表 | 多次查询、n≤2000 | 预处理 O(n²)，查询 O(1) | O(n²) | n≤2000 |
| 阶乘 + 逆元表 | 多次查询、n≤1e6 | 预处理 O(n)，查询 O(1) | O(n) | p 为质数且 p > n |
| 卢卡斯定理 | 多次查询、n≤1e18 | 预处理 O(p)，查询 O(log_p n) | O(p) | p 为质数 |
如果是单次查询，且 m 较小，直接用「循环直接计算」。 如果是多次查询，且 n≤2000，用「杨辉三角打表」。 如果是多次查询，且 n≤1e6、p 是质数且 p > n，用「阶乘 + 逆元表」。 如果 n 和 m 是大数值，或者 p≤n，用「卢卡斯定理」。
学习组合数学，关键在于理解'有序与无序''分类与分步'的区别，以及灵活运用乘法逆元、快速幂、递归分治等技巧。在实际做题时，一定要先分析题目的数据范围（n、m 的大小、查询次数、p 的性质），再选择合适的方法。没有最好的方法，只有最适合的方法。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online