组合数学：
前置芝士：
平方和公式： \(1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}\)
概念与计数：
基本计数原理：
分类计算加法原理，分布计算乘法原理。
简单容斥与摩根定理：
- \(\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];
}
}
二项式定理：
\[(a+b)^n=\sum_{k=0}^nC_n^ka^kb^{n-k}\\ (a-b)^n=\sum_{k=0}^n(-1)^kC_n^ka^kb^{n-k} \]计数技巧：
等价替代（映射）：
构造一个映射，将每一种原问题的方案映射为新问题的一种方案，并使答案更容易计算。
例如捆绑法，插空法，隔板法等。
捆绑法： 也成整体法，即若要求若干物品相邻，可以将他们视作一个整体来计数。
插空法： 如果要求若干物品两两不相邻，可以先将其他物品放好，然后将这些物品插入空挡当中进行计数。
隔板法： 将不可区分物品分配问题、不定方程整数解问题转化为插板组合问题。
例： 把 \(n\) 个相同的苹果分给 \(k\) 个人，要求每人至少分到一个的方案数。(求 \(x_1+x_2+x_3+\cdots+x_k=n\) 的整数解，满足 \(x_i\geq 1\))
把 \(n\) 个苹果排成一排，从左到右一次插入 \(k-1\) 块板子，共有 \(n-1\) 个位置可以插入，所以答案为 \(C_{n-1}^{k-1}\) 。
改变计数目标：
如果直接按照题意来计数比较困难，可以尝试通过减法、容斥原理等方法转换成容易求的目标。
改变枚举顺序：
很多时候，计数题要做的基本上是:在某个范围内枚举元素，计算它们的和。直接按照题意来做显然只能拿到暴力分(x), 我们往往需要安排一个合适的顺序来计算。
例： 求 \(\sum_{i=1}^n\sum_{j=1}^n\max(i,j)\)
\[\sum_{i=1}^n\sum_{j=1}^n\max(i,j)=\sum_{k=1}^nk\times\sum_{i=1}^n\sum_{j=1}^n[\max(i,j)==k]\ \ \ \ \ \ \ \\ =\sum_{k=1}^nk\times(2k-1)\ \ \ \ \\ =\sum_{k=1}^n(2n+1)k-k^2\\ =\frac{4n^3+3n^2-n}{6}\ \ \ \ \ \]
例题：
圆盘染色：
\(n\) 块组成一个圆盘，用 \(m\) 种颜色染色，使得相邻两块的颜色不同。求方案数。
考虑如果 \(n\) 的颜色与 \(n-2\) 相同，则将 \(n-2,n-1,n\) 看作一个整体。
那么 \(n-1\) 块有 \(m-1\) 种选择，则方案数为 \((m-1)\times f(n-2)\) ，（ \(f(i)\) 表示分成 \(i\) 块的方案数）
考虑如果 \(n\) 的颜色与 \(n-2\) 不同，将 \(n-2,n-1,n\) 看作一个整体。
那么 \(n-1\) 块有 \(m-2\) 种选择，则方案数为 \((m-2)\times f(n-1)\) 。
\(\therefore f(n)=(m-1)\times f(n-2)+(m-2)\times f(n-1)\)
( \(f(1)=0,f(2)=m\times(m-1),f(3)=m\times (m-2)\) )