排列组合
引入¶
排列组合是组合数学中的基础。排列就是指从给定个数的元素中取出指定个数的元素进行排序；组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。排列组合与古典概率论关系密切。
在高中初等数学中，排列组合多是利用列表、枚举等方法解题。
加法 & 乘法原理¶
在计数问题中，常用的两个基本原则是 加法原理 和 乘法原理，是进行统计计算的基本思想。
加法原理¶
英文：Addition Principle
如果完成一件事有 $n$ 种不相重处的方法，其中第 $i$ 种方法有 $a_i$ 种形式，那么完成该事的总方案数是：
需要注意
- 各种方法 不能有重处，即不一样的类型。
示例
- 从红色球罐中抽一个球有 $3$ 种选择，从绿色球罐中抽有 $4$ 种选择，如果只允许从一个罐里抽，那么抽法总数为：$3 + 4 = 7$
乘法原理¶
英文：Multiplication Principle
如果完成一项工作需要连续进行 $n$ 步，其中第 $i$ 步有 $a_i$ 种选择，并且每一步之间 相互独立，那么完成该工作的总方案是：
需要注意
- 每步之间 不依赖，方法数不变
- 如果后续操作依赖于前面结果，需重新计算
示例
- 有 $3$ 件衣服，$2$ 条裤子，每次选择一套衣裤打扮，总方法为 $3 \times 2 = 6$
总结对比¶
| 原理 | 选择场景 | 情况 | 总数算法 |
|---|---|---|---|
| 加法原理 | 两个或多个相互独立的选择 | 或 的关系 | $a_1 + a_2 + \cdots + a_n$ |
| 乘法原理 | 连续几步操作 | 并且 的关系 | $a_1 \times a_2 \times \cdots \times a_n$ |
应用建议¶
- 先分析题目是 或 关系还是 并且 关系
- 如果是不同类型选一个，用 加法原理
- 如果是几步加结合，每步有选择，用 乘法原理
- 如果有重处，需要准确分组后再计
计数算法是运算的思维，加法乘法是基础。学会分析各步的类型是解题的关键。
排列数¶
排列数表示从 $n$ 个不同元素中选出 $m$ 个元素，并对这 $m$ 个元素进行全排列的方案数。
表示方法有：
- $\mathrm A_n^m$
- $\mathrm P_n^m$
公式如下：
$n!$ 表示 $n$ 的阶乘，例如：$6! = 1\times 2\times 3\times 4\times 5\times 6$
理解：
将 $n$ 个人中选 $m$ 个出来排队：
- 第一个位置有 $n$ 个选法
- 第二个位置有 $n-1$ 个
- 第 $m$ 个位置有 $n-m+1$ 个
根据乘法原理，总方案数即为：
组合数¶
组合数表示从 $n$ 个不同元素中选出 $m$ 个元素，不考虑顺序的方案数。
常见表示方法：
-
$\binom{n}{m}$（现在主流）
-
$\mathrm C_n^m$
组合数计算公式：
理解：
先考虑顺序得到 $\mathrm A_n^m$，然后去除 $m!$ 种不同的排列顺序：
当 $m > n$，规定 $\binom{n}{m}=0$
组合数的性质¶
- $\binom{n}{m}= \binom{n}{n-m}$
从 $n$ 个中选 $m$ 个与选 $n - m$ 个是等价的（选谁留下谁都一样）。
- 杨辉三角
组合数在杨辉三角中的表现如下：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
-
第 $i$ 行第 $j$ 个数为 $\binom{i}{j}$
- 注意 $i,j$ 从 $0$ 开始编号。
-
递推公式（杨辉三角递推式）：
- 若选择第 $n$ 个元素，则在前 $n-1$ 中选 $m-1$ 个
- 若不选第 $n$ 个元素，则在前 $n-1$ 中选 $m$ 个
- 两种策略互不重叠是或的关系，因此根据加法原理总方案数是选和不选的方案数之和。
总结对比表¶
| 项目 | 排列数 $\mathrm A_n^m$ | 组合数 $\binom{n}{m}$ |
|---|---|---|
| 定义 | 从 $n$ 中选 $m$ 并排序 | 从 $n$ 中选 $m$ 不排序 |
| 是否考虑顺序 | 考虑 | 不考虑 |
| 计算公式 | $\frac{n!}{(n-m)!}$ | $\frac{n!}{m!(n-m)!}$ |
| 最大值 | 当 $m=n$ 时 | 当 $m=\lfloor n/2 \rfloor$ 时最大 |
排列数组合数的求法¶
暴力求法¶
排列数公式可化简为：
如果需要取余，则边计算边取余即可。
// 求排列数 A(n, m)
long long A(int n, int m)
{
if (m > n) return 0;
long long res = 1;
for (int i = n - m + 1; i <= n; i++)
res *= i;
return res;
}
组合数公式可化简为：
// 求组合数 C(n, m)
long long C(int n, int m)
{
if (m > n) return 0;
long long up = 1, down = 1;
for (int i = n - m + 1; i <= n; i++) up *= i;
for (int i = 1; i <= m; i++) down *= i;
return up / down;
}
组合数取模实现
当需对 $10^9 + 7$ 这类大质数取模时，使用费马小定理处理除法：
保证 $m\nmid mod$ 即可（逆元存在）。
// 求组合数 C(n, m) % mod，其中 mod 是质数
long long C(int n, int m)
{
if (m > n) return 0;
long long up = 1, down = 1;
for (int i = n - m + 1; i <= n; i++) up = up * i % mod;
for (int i = 1; i <= m; i++) down = down * i % mod;
return up * ksm(down, mod - 2) % mod;
}
预处理¶
杨辉三角
根据递推式
- 适合 $n \leq 5000$ 等较小范围。
- 注意行和列的编号从 $0$ 开始，这样可以和组合数完全对应上。
// 预处理组合数 c[i][j] = C(i, j)
for (int i = 0; i <= 5000; i++)
{
for (int j = 0; j <= i; j++)
{
if (j == 0 || j == i) c[i][j] = 1;
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
线性预处理
定义 $fac_i=i!\bmod p$，$inv_i=i!^{-1}\bmod p$。
阶乘预处理
使用递推即可，fac[i] = fac[i - 1] * i % mod。注意爆 int 的风险。
阶乘的逆元预处理
注意到 $i!^{-1}=(i+1)!\cdot (i+1)$。
- 即 $\dfrac{1}{i!}=\dfrac{1}{(i+1)!}\cdot (i+1)$。
则可以单独求出 $n!^{-1}$ （费马小定理或扩展欧几里得），然后逆推得到所有阶乘的逆元。
constexpr int N = 1e6 + 5, mod = 1e9 + 7;
long long fac[N], inv[N]; // 根据题目需要的组合数范围开数组大小
// 预处理部分
void init(int n)
{
fac[0] = 1;
for (int i = 1; i <= n; i++)
fac[i] = fac[i - 1] * i % mod;
inv[n] = ksm(fac[n], mod - 2);
for (int i = n - 1; i >= 0; i--)
inv[i] = inv[i + 1] * (i + 1) % mod;
}
int C(int n, int m)
{
if (n < m) return 0;
return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int A(int n, int m)
{
if (n < m) return 0;
return fac[n] * inv[n - m] % mod;
}
预处理一般是根据题目的数据范围，例如一般预处理出 $1\sim 10^6$ 的相关信息。然后 $O(1)$ 查询需要的组合数或排列数。
高精度组合数¶
方法一
利用杨辉三角预处理，利用封装好的高精度加法即可实现。
vector<int> add(vector<int> &a, vector<int> &b)
{
// 两个三位数相加最多四位数
int len = max(a.size(), b.size()) + 1;
vector<int> c(len, 0); // 初始化一个长度为 len 且所有元素都是 0 的 vector
// c[i] = a[i] + b[i]
for (int i = 0; i < a.size(); i++) c[i] += a[i];
for (int i = 0; i < b.size(); i++) c[i] += b[i];
// 进位
for (int i = 0; i + 1 < c.size(); i++)
{
c[i + 1] += c[i] / 10;
c[i] %= 10;
}
// 去除前导 0，删除末尾的 0，使用 vector 的 Pop_back 函数删除即可
while (c.size() > 1 && c.back() == 0) c.pop_back();
return c;
}
vector<int> c[505][505];
void init()
{
for (int i = 0; i <= 500; i++)
{
for (int j = 0; j <= i; j++)
{
if (j == 0 || j == i) c[i][j] = {1};
else c[i][j] = add(c[i - 1][j], c[i - 1][j - 1]);
}
}
}
方法二
对组合数用勒让德定理进行质因子分解，从而转变为高精度乘法。
- 勒让德定理
$n!$ 中可以分解质因子 $p$ 的个数如下所示
int calc(int n, int p) // 求 n 的阶乘可以分解几个质因子 p
{
int res = 0;
while (n)
res += n / p, n /= p;
return res;
}
对组合数 $\binom{n}{m}$ 中某个质因子 $p$，其指数为：
接下来实现高精度乘以低精度的乘法即可。
Lucas 定理¶
Lucas 定理主要是求解 $\dbinom{n}{m} \bmod p$，且 $p$ 为素数。
- 应用在当 $n,m$ 很大，例如 $n\leq 10^{18}$，但 $p$ 一般不会太大。
对于素数 $p$，有
其中，当 $n<m$ 时，二项式系数 $\dbinom{n}{m}$ 规定为 $0$。
第一个组合数可以继续递归直到 $m,m<p$ 为止，第二个组合数可以预处理或者直接暴算。
递归至多进行 $O(\log_p n)$ 次，因而算法的复杂度为 $O(f(p)+g(p)\log_p n)$，其中，$f(p)$ 为预处理组合数的复杂度，$g(p)$ 为单次计算组合数的复杂度。
long long Lucas(long long n, long long m, long long p)
{
if (n < m) return 0;
if(m == 0) return 1;
return Lucas(n / p, m / p, p) * C(n % p, m % p, p) % p;
}
lucas 定理的证明¶
引理： $(1+x)^p \equiv 1+x^p \pmod p$
设 $p$ 为素数，根据二项式定理展开：
观察中间项（$1 < i < p$）的系数：
- $\binom{p}{i} = \dfrac{p!}{i!(p-i)!}$ 中分子含有 $p$，分母不含 $p$
- 所以 $p \mid \binom{p}{i}$，这些项在 $\pmod p$ 意义下为 $0$
故有：
构造：拆解 $\binom{n}{m}$ 为 $p$ 进制
欲证：
设：
目标转化为：
思路：分析 $(1+x)^n$ 中 $x^m$ 项的系数，使用乘法展开：
再用引理替换 $(1 + x)^p \equiv (1 + x^p)$。
展开与系数分析
将 $(1 + x^p)^s \cdot (1 + x)^q$ 展开：
我们要找 $x^m$ 的系数，设 $m = tp + r$，则：
- $x^{tp}$ 来自 $(1 + x^p)^s$ 的 $\binom{s}{t} x^{tp}$ 项
- $x^r$ 来自 $(1 + x)^q$ 的 $\binom{q}{r} x^r$ 项
故 $x^m$ 项系数为：
例题¶
[HNOI 2008] 越狱。¶
一个经典的容斥思想是：用总方案数减去不合法的方案数。
总方案数：即每个位置都有 $m$ 种选择，根据乘法原理：因此是 $m^n$。
不越狱的方案数：
- 第一个位置有 $m$ 种选择。
- 第二个位置有 $m-1$ 种选择。
- 第三个位置只需要和第二个不同即可，因此也是 $m-1$ 种选择。
- 以此类推，根据乘法原理：不越狱的方案数为 $m\cdot m^{n-1}$。
因此答案为
使用快速幂即可实现。注意取余问题细节。