数学是毒瘤
组合数学总结。
如果说数论是数学的基础，那么组合数学往后就是高阶了。这之后的数学不再像数论那么板子，而是变得需要更多的推理和组合了。知识很简单，难的是应用。
本来还有什么容斥原理，看不懂，于是没放
初始化
为了方便快速求排列组合，我们需提前预处理阶乘和阶乘的乘法逆元。
令 \(\textit{fac}[i]\) 表示 \(i\) 的阶乘，\(\textit{inv}[i]\) 表示 \(\boldsymbol i\) 的阶乘 的乘法逆元。
\(\textit{inv}[i]\) 是 \(\boldsymbol i\) 的阶乘 的乘法逆元，不是 \(i\) 的乘法逆元！
2024/3/17 upd.
注意：若 \(\boldsymbol n\) 的规模超过 \(\boldsymbol{10^6}\) 级别，请勿预处理 \(\boldsymbol{\boldsymbol{inv}[i]}\)，而是即时计算！
注意：若 \(\boldsymbol n\) 的规模超过 \(\boldsymbol{10^7}\) 级别，请线性求逆元！公式：\(\boldsymbol{\boldsymbol{inv}[i]=\boldsymbol{inv}[i+1]\times(i+1)~\mathbf{mod~MOD}}\)。——2024/5/19 upd.
void init() {
fac[0] = inv[0] = 1;
for (int i = 1; i < MAXN; i++) {
fac[i] = fac[i - 1] * i % MOD;
inv[i] = power(fac[i], MOD - 2, MOD);
}
}
一般情况下，数论题都有一个 \(\mathrm{MOD}\) 值，否则可以传参 \(p\) 表示模数。
排列数 \(\boldsymbol{\mathbf A_n^m}\)
排列数的计算公式如下：
\[\mathrm A_n^m=\frac{n!}{(n-m)!} \]inline int A(int n, int m, int p) {
if (n < m) return 0;
return fac[n] * inv[n - m] % p;
}
组合数 \(\boldsymbol{\dbinom nm}\)
组合数的计算公式如下：
\[\binom nm=\frac{n!}{m!(n-m)!} \]inline int C(int n, int m, int p) {
if (n < m) return 0;
return fac[n] * inv[m] % p * inv[n - m] % p;
}
排列数和组合数都只需 \(O(n)\) 的预处理便可 \(O(1)\) 查询。
若需要即时求组合数，可以根据公式直接记忆化搜索：
int C(int n, int m) {
if (m == 0 || m == n) return 1;
if (cc[n][m] != 0) return cc[n][m];
return cc[n][m] = C(n - 1, m) + C(n - 1, m - 1);
}
组合数性质
\[\binom{n}{m}=\binom{n}{n-m}\tag{1} \]相当于将选出的集合对全集取补集，故数值不变。（对称性）
\[\binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}\tag{2} \]由定义导出的递推式。
\[\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}\tag{3} \]组合数的递推式（杨辉三角的公式表达）。我们可以利用这个式子，在 \(O(n^2)\) 的复杂度下推导组合数。
\[\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=\sum_{i=0}^n\binom{n}{i}=2^n\tag{4} \]这是二项式定理的特殊情况。取 \(a=b=1\) 就得到上式。
\[\sum_{i=0}^n(-1)^i\binom{n}{i}=[n=0]\tag{5} \]二项式定理的另一种特殊情况，可取 \(a=1, b=-1\)。式子的特殊情况是取 \(n=0\) 时答案为 \(1\)。
\[\sum_{i=0}^m \binom{n}{i}\binom{m}{m-i} = \binom{m+n}{m}\ \ \ (n \geq m)\tag{6} \]拆组合数的式子，在处理某些数据结构题时会用到。
\[\sum_{i=0}^n\binom{n}{i}^2=\binom{2n}{n}\tag{7} \]这是 \((6)\) 的特殊情况，取 \(n=m\) 即可。
\[\sum_{i=0}^ni\binom{n}{i}=n2^{n-1}\tag{8} \]带权和的一个式子，通过对 \((3)\) 对应的多项式函数求导可以得证。
\[\sum_{i=0}^ni^2\binom{n}{i}=n(n+1)2^{n-2}\tag{9} \]与上式类似，可以通过对多项式函数求导证明。
\[\sum_{l=0}^n\binom{l}{k} = \binom{n+1}{k+1}\tag{10} \]通过组合分析一一考虑 \(S={a_1, a_2, \cdots, a_{n+1}}\) 的 \(k+1\) 子集数可以得证，在恒等式证明中比较常用。
\[\binom{n}{r}\binom{r}{k} = \binom{n}{k}\binom{n-k}{r-k}\tag{11} \]通过定义可以证明。
\[\sum_{i=0}^n\binom{n-i}{i}=F_{n+1}\tag{12} \]Lucas 定理
当 \(n,m\) 过大、超出数组的范围时，我们需要用 Lucas 定理求组合数。模数必须为质数。即对于质数 \(p\)，有：
\[{n\choose m}\bmod p={n\bmod p\choose m\bmod p}{\left\lfloor n/p \right\rfloor\choose\left\lfloor m/p \right\rfloor}\bmod p \]易知，\({n\bmod p\choose m\bmod p}\) 的 \(n,m\) 范围一定小于等于 \(p\)，可以直接求解；\({\left\lfloor n/p \right\rfloor\choose\left\lfloor m/p \right\rfloor}\) 可以继续递归求解。当 \(m=0\) 时，返回 \(1\)，递归结束。
int lucas(int n, int m, int p) {
if (m == 0) return 1;
return C(n % p, m % p, p) * lucas(n / p, m / p, p) % p;
}
二项式反演
二项式反演用于解决“某个物品恰好若干个”这类计数问题。
直接摆公式。证明需要用到前文提到的组合数定理。
形式 1
\(f_n\) 表示恰好 \(n\) 个的方案数量，\(g_n\) 表示至多 \(n\) 个的方案数量，则：
\[g_n=\sum_{i=0}^n{n\choose i}f_i\iff f_n=\sum_{i=0}^n\left(-1\right)^{n-i}{n\choose i}g_i \]形式 2
\(f_k\) 表示恰好 \(k\) 个的方案数量，\(g_k\) 表示至少 \(k\) 个的方案数量，则：
\[g_k=\sum_{i=k}^n{i\choose k}f_i\iff f_k=\sum_{i=k}^n\left(-1\right)^{i-k}{i\choose k}g_i \]