202606161406排列组合

排列组合

⁠1. 排列数

问题引入：有 $n$ 个座位，坐 $n$ 个同学，请问有多少种坐法？

对于第一个座位，可以从 $n$ 个同学里面任选一个坐，所以共有 $n$ 种选择。对于第二个座位，只能从剩下的 $n-1$ 个同学中挑一个坐，故有 $n-1$ 种选择。依此类推，最后一个座位，只剩最后一位同学，只有 $1$ 种选择。根据乘法原理共有，

$$n\times (n-1)\times \cdots \times 1=n!\triangleq A_n^n$$

种坐法。不失一般性，我们把它记为 $A_n^k$，叫做排列数，其含义是从 $n$ 个里面选 $k$ 个做排列，共有多少种排列方法。如无特殊说明，默认 $k\le n$.

类似的，3个座位，5个同学，有多少种坐法？第一个座位可选5，第二个可选4，第三个可选3，共有 $5\times 4\times 3=A_5^3$ 种坐法。再类似的，5个座位，3个同学，有多少种坐法？第一个同学任选5个座位，第二个任选余下的4个，第三个任选余下的3个，所以共有 $5\times 4\times 3=A_5^3$ 种坐法。一般的，

$$A_n^k=\underset{k项相乘}{\underbrace{n\times (n-1)\times \cdots \times (n-k+1)}}=\frac{n!}{(n-k)!}$$

特别的，称 $A_n^n=n!$ 为 $n$ 的全排列。

⁠2. 组合数

问题引入：有 $n$ 个同学，挑 $k$ 个去参加活动，请问有多少种挑法？

现在我们只是要挑选出来，不要求做排列。如果考虑挑出 $k$ 个同学按顺序落座，那么答案显然就是 $A_n^k$. 但我们其实不考虑顺序，想象一下，这件事我们其实分了两步，

1. 挑选 $k$ 个同学出来，
2. 给 $k$ 个同学落座（做排列）

其实我们想要的是第一步的答案，但我们额外做了 $k$ 个同学的全排列。因此，要在结果种去掉这些重复的。所以从 $n$ 选 $k$，不考虑顺序，共有，

$$\frac{A_n^k}{A_k^k}=\frac{n!}{(n-k)!\times k!}\triangleq C_n^k$$

种选法，我们把这个数叫做组合数。有些教材也用下面的记号表示组合数，

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{(n-k)!\cdot k!}$$

⁠3. 组合数的计算

在C++中计算组合数时，由于阶乘增长很快，很容易发生整数溢出。从减少计算量的角度考量，组合数可以写成，

$$C_n^k=\frac{n\cdot (n-1)\cdot \cdots \cdot (n-k+1)}{k!}$$

在迭代计算时，按照一定的计算顺序，还可以做到边乘边除，不用担心除不尽的问题。

long long comb(int n, int k) {
    if (k < 0 || k > n) return 0;
    if (k == 0 || k == n) return 1;
    if (k > n - k) {
        // 利用组合数的对称性 C(n, k) = C(n, n-k) 减少计算量
        k = n - k;
    }
    long long res = 1;
    for (int i = 1; i <= k; ++i) {
        // 先乘后除，确保整除
        res = res * (n - k + i) / i;
    }
    return res;
}

如果我们查看每一步res的取值，

1. $(n-k+1)/1$ 显然是整数
2. $\frac{(n-k+1)\cdot (n-k+2)}{1\cdot 2}=C_{n-k+2}^2$ 这是一个组合数，显然也是整数
3. $\frac{(n-k+1)\cdot (n-k+2)\cdot (n-k+3)}{1\cdot 2\cdot 3}=C_{n-k+2}^2\cdot \frac{n-k+3}{3}=C_{n-k+3}^3$ 也是整数
4. 依此类推，一直是整数，没有除不尽的问题。

此外，中间计算结果最好用 long long 或者 unsigned long long 存储，防止整数相乘溢出。

⁠3.1. 逆元计算

摘自ref1.

引理

如果 $p$ 是一个质数，$a$ 是 $b$ 的倍数且 $b$ 和 $p$ 互质（$b$ 不是 $p$ 的倍数），那么有

$$\frac{a}{b}\mathrm{mod}p=(a\cdot b^{p-2})\mathrm{mod}p.$$

组合数分母有阶乘，所以需要处理阶乘及其逆元，然后利用公式

$$C_n^m=\frac{n!}{m!(n-m)!}=n!\cdot \frac{1}{m!}\cdot \frac{1}{(n-m)!}$$

计算。

对于阶乘 $n!$，可以用 $n!=(n-1)!\cdot n$ 递推计算。对于阶乘的倒数 $1/n!$，可以先计算 $N!$ 的逆元（其中 $N$ 是 $n$ 的最大值），然后用

$$\frac{1}{(n-1)!}=\frac{1}{n!}\cdot n$$

倒着递推计算。

const int MOD = 1'000'000'007; // 质数
const int MX = 100'001; // 根据题目数据范围修改
 
long long F[MX]; // F[i] = i!
long long INV_F[MX]; // INV_F[i] = i!^-1 = qpow(i!, MOD-2)
 
long long qpow(long long x, int n) {
    long long res = 1;
    for (; n; n /= 2) {
        if (n % 2) {
            res = res * x % MOD;
        }
        x = x * x % MOD;
    }
    return res;
}
 
auto init = [] {
    F[0] = 1;
    for (int i = 1; i < MX; i++) {
        F[i] = F[i - 1] * i % MOD;
    }
 
    INV_F[MX - 1] = qpow(F[MX - 1], MOD - 2);
    for (int i = MX - 1; i; i--) {
        INV_F[i - 1] = INV_F[i] * i % MOD;
    }
    return 0;
}();
 
// 从 n 个数中选 m 个数的方案数
long long comb(int n, int m) {
    return m < 0 || m > n ? 0 : F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD;
}
 
class Solution {
public:
    int solve(vector<int>& nums) {
        // 预处理的逻辑写在 class 外面，这样只会初始化一次
    }
};

⁠4. 参考资料

1. 模运算的世界：当加减乘除遇上取模（模运算恒等式/费马小定理/组合数）