加法原理

假设完成一件事的方法有 $N$ 类，其中第 $i$ 类又有 $a_i$ 种不同的方法（这些方法之间不存在重合关系），则完成这件事的方法总数为：

$$\sum _{i=1}^N{a}_i$$

乘法原理

假设完成一件事需要 $N$ 个步骤，其中第 $i$ 步有 $a_i$ 个不同的方法（这些步骤之间互不干扰），则完成这件事的方法总数为：

$$\prod _{i=1}^N{a}_i$$

排列组合

排列

从 $n$ 个不同的元素中依次取出 $m$ 个元素排成一列，求产生的不同排列的个数。记为 $A_n^m$。求解公式为：

$$A_n^m=\frac{n!}{(n-m)!}$$

如何理解这个公式呢？

逐一考虑每个位置放置哪种元素，对于第一个位置，有 $n$ 种选择，对于第二个位置，有 $n-1$ 种选择，依次类推，直到最后一个位置（第 $m$ 个位置），有 $n-m+1$ 种选择。乘法原理可得总共有 $n\times (n-1)\times \cdots \times (n-m+1)$ 种选择。

组合

从 $n$ 个不同的元素中取出 $m$ 个元素组成一组，不考虑组内顺序，求产生的不同组合的个数。记为 $C_n^m$。求解公式为：

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

如何理解这个公式呢？

如果从 $n$ 个元素中取出 $m$ 个元素，排成一列（在乎顺序），则为 $A_n^m$；如果不考虑顺序，则需要去除重复的部分，重复了多少？对于这 $m$ 个元素，它们还需要全排，即为 $m!$。因此:

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

组合数的一些性质：

• $C_n^m=C_n^{n-m}$
• $C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$
• $2^n=C_n^0+C_n^1+\cdots +C_n^n$

组合数的求解方法：

方法一：根据公式直接计算。为了避免除法取模，可以通过计算分母的乘法逆元来计算。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, MOD = 1e9 + 7;
int fact[N], infact[N];

int qmi(int a, int b, int p) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = (long long)ans * a % p;
        a = (long long)a * a % p;
        b >>= 1;
    }
    
    return ans;
}

int main() {
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i++) {
        fact[i] = (long long)fact[i - 1] * i % MOD;
        infact[i] = (long long)infact[i - 1] * qmi(i, MOD - 2, MOD) % MOD;
    }
    
    int T; cin >> T;
    while (T--) {
        int a, b; cin >> a >> b;
        cout << (long long)fact[a] * infact[a - b] % MOD * infact[b] % MOD << endl;
    }
    
    return 0;
}

方法二：根据性质 $C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$ 递归计算。

#include <bits/stdc++.h>
using namespace std;

const int N = 2010, MOD = 1e9 + 7;
int c[N][N];

int main() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) {
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
        }
    }
    
    int T; cin >> T;
    while (T--) {
        int a, b; cin >> a >> b;
        cout << c[a][b] << endl;
    }
    
    return 0;
}

方法三：若题目中的 $m,n$ 都比较大，常规解法需要用到高精度乘法除法，为了绕过高精度除法，我们可以将分子、分母分解质因数，消去相同的质因数之后，再将剩余部分乘起来。

方法四：若题目中 $m,n$ 都比较大，且最终结果需要模一个质数 $p$，考虑使用 $Lucas$ 公式计算：$C_n^m=C_{n\mathrm{mod}p}^{m\mathrm{mod}p}\times C_{n/p}^{m/p}(\mathrm{mod}p)$。

组合与排列的关系

我们先从 $n$ 个元素中取出 $m$ 个元素，记为 $C_n^m$，然后对这 $m$ 个元素进行全排列，记为 $A_m^m$，乘法原理可得：

$$A_n^m=C_n^m\ast A_m^m=\frac{n!}{m!(n-m)!}m!=\frac{n!}{(n-m)!}$$

特别的，当 $m>n$ 时，$A_n^m=C_n^m=0$。

排列组合的经典模型

1. 捆绑法

假设有 $n+m$ 个人站成一排拍照，其中特定的 $m$ 个人必须站在连续的 $m$ 个位置上，求总共有多少种排法？($A_{n+1}^{n+1}\times A_m^m$)

2. 隔板法

假设有 $m$ 个人分 $n$ 个苹果（忽略苹果之间的差异），每人至少分得一个苹果，共有多少种分法？（$C_{n-1}^{m-1}$)

3. 插空法

假设有 $n+m$ 个人站成一排拍照，其中特定的 $m$ 个人关系很差，这 $m$ 个人中不能有任何两个人的位置相邻，共有多少种排法？($A_n^n\times A_{n+1}^m$)

二项式定理

$$(x+y{)}^n=\sum _{k=0}^n{C}_n^k{x}^k{y}^{n-k}$$