组合数学与组合计数

计数原理

分类加法计数原理：做一件事，有多类方法，则总的方法数是所有类方法数之和。
分步乘法计数原理：做一件事，需要多步完成，则总的方法数是所有步方法的乘积。

例题：P3197 [HNOI2008] 越狱

排列与组合

排列数：从 $n$ 个数中选出 $m$ 个数排成一列，所有方案数根据乘法原理，有 $$P^m_n = n \times (n-1) \times (n-2) \times \dots \times (n-m+1) = \frac{n!}{(n-m)!}$$
全排列：$P_n^n = n!$
组合数：从 $n$ 个数中选出 $m$ 个数，不考虑相对顺序，则与排列数有以下关系：$$C^m_n = \frac{A^m_n}{m!} = \frac{n!}{(n-m)!m!}$$

组合数的性质：

$C^m_n = C^{n-m}_n$
$C^m_n = C^m_{n-1} + C^{m-1}_{n-1}$ （杨辉三角）
$\sum_{i=0}^n C_n^i = 2^n$

求组合数的代码实现

递推法。根据性质二，可以以 $n$ 为阶段递推出组合数，时间复杂度 $O(nm)$ 可以求出所有 $n$ 内的组合数。
逆元法。若计算 $C^n_m$ 在取模 $p$ 意义下的值，可以在 $n \log p$ 的时间复杂度内用费马小定理求逆元的方法同时预处理出阶乘在取模 $p$ 意义下的值和逆元，然后在模意义下运算即可。