组合数学：
概念与计数：
基本计数原理：
分类计算加法原理，分布计算乘法原理。
简单容斥与摩根定理：
- \(\begin{vmatrix}A\cup B\end{vmatrix}=\begin{vmatrix}A\end{vmatrix}+\begin{vmatrix}B\end{vmatrix}-\begin{vmatrix}A\cap B\end{vmatrix}\)
- \(\begin{vmatrix}A\cup B\cup C\end{vmatrix}=\begin{vmatrix}A\end{vmatrix}+\begin{vmatrix}B\end{vmatrix}+\begin{vmatrix}C\end{vmatrix}-\begin{vmatrix}A\cap B\end{vmatrix}-\begin{vmatrix}A\cap C\end{vmatrix}-\begin{vmatrix}C\cap B\end{vmatrix}+\begin{vmatrix}A\cap B\cap C\end{vmatrix}\)
摩根定理： 交集的补等于补集的并，并集的补等于补集的交。
即 \(\overline{A\cup B}=\overline{A}\cap\overline{B}\) \(\overline{A\cap B}=\overline{A}\cup\overline{B}\)
\[\left| \bigcup_{i=1}^n A_i\right|=\sum_{\varnothing\not={\rm J}\subseteq\{1,\cdots,n\}}(-1)^{\begin{vmatrix}{\rm J}\end{vmatrix}+1}\left| \bigcap_{{\rm j}\in{\rm J}} A_j\right|\\ \left| \bigcap_{i=1}^n \overline{A_i}\right|=\sum_{{\rm J}\subseteq\{1,\cdots,n\}}(-1)^{\begin{vmatrix}{\rm J}\end{vmatrix}}\left| \bigcap_{{\rm j}\in{\rm J}} A_j\right|\\ \left| \bigcap_{i=1}^n A_i\right|=\sum_{{\rm J}\subseteq\{1,\cdots,n\}}(-1)^{\begin{vmatrix}{\rm J}\end{vmatrix}}\left| \bigcap_{{\rm j}\in{\rm J}} \overline{A_j}\right|\\ \]
组合计数：
排列数：
从 \(n\) 个不同元素中依次取出 \(m\) 个元素排成一列，产生的不同排列的数量为：(取 \(m\) 个，将 \(m\) 个排序)
\[A_n^m(P_n^m)=\frac{n!}{(n-m)!} \]组合数：
从 \(n\) 个不同元素中取出 \(m\) 个组成一个集合（不考虑顺序），产生的不同集合的数量为：
\[C_n^m= \begin{pmatrix} n\\m \end{pmatrix} =\frac{n!}{m!(n-m)!} \]性质：
- \(A_n^k=C_n^k\times k!\)
- \(C_n^m=C_n^{n-m}\)
- \(C_n^m=C_{n-1}^m+C_{n-1}^{m-1}\) （杨辉三角）
- \(\frac{k}{n}\times C_n^k=C_{n-1}^{k-1}\)
- \(\sum_{i=0}^nC_n^i=2^n\)
- \(\sum_{i=0}^n(-1)^iC_n^i=0\)
组合数求解：
单个组合数 \(O(n)\)
int C(int n, int k) {
int p = 1, q = 1;
for (int i = n - k + 1; i <= n; ++i)
p *= i;
for (int i = 1; i <= k; ++i)
q *= i;
return p / q;
}
求 \(C_i^j(i\in[0,n-1],j\in[1,i])\) 递推 \(O(n^2)\)
for (int i = 0; i < n; ++i) {
C[i][0] = 1;
for (int j = 1; j <= i; ++j) {
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}