组合数学和线性代数
目录组合数学
组合数
\(\binom{m}{n}\)表示\(m\)个物品选出\(n\)个的方案数，也可记作\(C^n_m\)：
\[\binom{m}{n}=\frac{m!}{n!(m-n)!} \]特别地，当\(n<0\)或者\(n>m\)时，\(\binom{m}{n}=0\)。
\(\binom{m}{n_1,n_2,...,n_k}\)表示将\(m\)个物品分成\(k\)组，第\(i\)组恰有\(n_i\)个的方案数：
\[\binom{m}{n_1,n_2,...,n_k}=\frac{m!}{n_1!n_2!...n_k!} \]特别地，\(\binom{m}{n}=\binom{m}{n, m-n}\)。
一些结论：
- 当\(m>0\)、\(n=m\)或者\(n=0\Lrarr\binom{m}{n}=1\)；
- \(\binom{m}{n}=\binom{m}{m-n}\)；
- \(\binom mn=\binom{m-1}{n}+\binom{m-1}{n-1}\)（杨辉三角）；
- \((1+x)^n=\sum_{i=0}^{n}\binom nix^i\)（二项式定理）；
- \(\sum^k_{i=0}\binom ni \binom m{k-i}=\binom{n+m}k\)；
- \(\sum_{i=n}^m\binom in=\binom{m+1}{n+1}\)。
例题：
Luogu P2822 杨辉三角
Luogu P1313 二项式定理
求证：\(\sum_{i=0}^n\binom ni^2=\binom{2n}{n}\)（\(\binom ni^2=\binom ni \binom n{n-i}\)）
求证：\(\sum_{i=0}^{\lfloor\frac{n}{2}\rfloor}\binom n{2i}=2^{n-1}\)（\(2^n+0^n=\sum_{i=0}^n\binom ni (1+(-1)^i)=2\sum_{i=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n}{2i}\)）
Twelvefold Way
Twelvefold Way（组合计数全家桶）：\(n\)个球放进\(m\)个桶，球和桶可能有标号也能无标号，每个桶中球的数量可能有限制也可能限制之多或至少一个，每个球必须放进一个桶球所有情况下的方案数。答案如表：
| 数量限制 | 没有限制 | 至多一个 | 至少一个 |
|---|---|---|---|
| 球有标号，桶有标号 | \(m^n\) | \(\binom mn n!\) | \(m!{n\brace m}\) |
| 球无标号，桶有标号 | \(\binom {n+m-1}{m-1}\) | \(\binom mn\) | \(\binom {n-1}{m-1}\) |
| 球有标号，桶无标号 | \(\sum^m_{k=1}\) | \([n\le m]\) | \({n\brace m}\) |
| 球无标号，桶无标号 | \(p_m(n)\) | \([n\le m]\) | \(p_m(n)\) |
基础计数
Q1、Q2、Q5、Q8、Q11
隔板法
Q6（将 \(n\)个球排成一行切成\(m\)段）、Q4（加入\(m\)个球每段至少一个）
整数划分
Q12（不关心桶的数量就可以假设每个桶球的数量不增）、Q10（Q12再加\(m\)个球，每个桶至少一个球，最后将\(m\)个球拿出）
整数划分：将\(n\)拆成\(m\)个不增数相加的方案数，记作\(p_m(n)\)。
- 边界：\(p_0(0)=1\)；
- 转移：\(p_m(n)=p_{m-1}+p_m(n-m)\)
若直接转移，其时间复杂度为\(O(n^2)\)。利用生成函数转移可以优化到\(O(n\log n)\)。
第二类斯特林数
Q9（相当于将\(n\)个元素划分成\(m\)个等价类）、Q3（将\(n\)个球划分成\(m\)个等价类，对于每种划分，将同一个等价类放入一个桶。等价类和桶对应方法有\(m!\)种）、Q7（桶空了就是少一种等价类，枚举等价类数目）
第二类斯特林数：记作\({n\brace m}\)：
- \({0\brace 0}=1\)，当\(n\ge 1\)时，\({n\brace 0}=0,{n\brace 1}={n\brace n}=1\)；
- \({n\brace m}=m{n-1\brace m}+{n-1\brace m-1}\)：将第\(n\)个元素单独作为一个等价类；或在现有的\(m\)个等价类中选择一个加入，有\(m\)中可能。
对于Q3，我们不好求某些桶中存在空桶的方案数，但很容易求出某些桶必须同时为空的方案。我们按照\(1—m\)给桶编号。假设空桶的编号集合为\(S\)，则使得\(S\)内所有桶为空（但不一定所有空桶都在\(S\)内）的方案数为\((m-|S|^n)\)。
例题：
Luogu P5824 Twelvefold Way
容斥原理
容斥原理：对于\(n\)个集合\(A_1,A_2,...,A_n\subseteq U\)，有
\[|\bigcap_{i=1}^{n}\overline{A_i}|=\sum_{I\subseteq \set{1,2,...,n}}(-1)^{|I|}(\bigcap_{i\in I}|A_i|) \]用\(A_I\)表示所有\(A_i(i\in I)\)的交集，\(A_\empty=U\)，则上述表达式右侧可以化为
\[\sum_{I\subseteq \set{1,2,...,n}}(-1)^{|I|}|A_I| \]适用于求并集（至少满足某个条件）很难但是交集（同时满足某些条件）很好求的问题。
利用容斥我们可以求斯特林数的通项。
令\(A_i(1\le i\le m)\)表示第\(i\)个桶为空。
则\(A_S\)表示\(S\)内的所有桶都为空，\(\bigcup_{i=1}^nA_i\)表示至少有一个桶为空。
因此所有桶非空的方案数为
\[|\bigcap_{i=1}^{n}\overline{A_i}|\\ =\sum_{S\subseteq \set{1,2,3,...,m}}(-1)^{|S|}|A_S|\\ =\sum_{S\subseteq \set{1,2,3,...,m}}(-1)^{|S|}(m-|S|)^n\\ =\sum_{k=0}^m\binom mk (-1)^k(m-k)^n \]因此第二类斯特林数有以下公式：
\[{n\brace m}=\frac{1}{m}\sum_{k=0}^m\binom mk(-1)^{m-k}k^n \]例题：
错排问题：求满足\(\pi_i\not=i\)的长为\(n\)的排列\(\pi\)的数量
可重集选择问题：给一个包含\(n\)种元素的可重集，第\(i\)个元素出现了\(a_i\)次，求取出\(k\)个元素的方案数
JSOI 2011 分特产
反演
反演：已知\(f\)关于\(g\)的表达式，求\(g\)关于\(f\)的表达式的过程称为反演。
例题：
前缀和和差分：若\(f(n)=\sum_{i\le n}g(i)\)，则差分\(f\)可得\(g(n)=f(n)-f(n-1)\)。
二项式反演
容斥中有时候每个子集是等价的。、
记\(f(n)\)为至多选\(n\)个的方案数，\(g(n)\)为恰好选\(n\)个的方案数，则
\[f(n)=\sum_{i\le n}\binom mi g(i) \Rarr g(n)=\sum_{i\le n}\binom ni (-1)^{n-i}f(i) \]对于错排问题：
- \(g(n)\)：所有\(i\)都满足\(\pi_i\not=i\)，\(f(n)\)：至多\(n\)个\(i\)满足\(\pi_i\not= i\)
- \(f(n)=n!\)（任意一种排列都至多只有\(n\)个\(\pi_i\not=i\)。
莫比乌斯反演
-
\(f(n)\)：\(n\)的因子的答案之和；\(g(n)\)：\(n\)的答案。
\(f(n)=\sum_{d|n}g(d)\Rarr g(n)=\sum_{d|n}\mu(d)f(\frac nd)\)
-
\(f(n)\)：\(n\)的倍数的答案之和；\(g(n)=\sum_{d|n}\mu(\frac dn)f(d)\)
\(f(n)=\sum_{n|d}g(d)\Rarr g(n)=\sum_{n|d}\mu(\frac dn)f(d)\)
比如题目限制\(\gcd(i,j)=k\)，那么就可以转化为求\(k|\gcd(i,j)\)的答案，即\(k|i\land k|j\)。
莫比乌斯函数：
- 是积性函数：\(\mu(1)=1,\mu(p)=-1,\mu(p^e)=0(e\ge 2)\)
- \(\sum_{d|n}\mu(d)=[n=1]\)
高维前缀和
定义\(f(S)\)为\(S\)的子集的答案之和，\(g(S)\)为\(S\)的答案，则
\[f(s)=\sum_{T\subseteq S}g(T)\Rarr \sum_{T\subseteq S}(-1)^{(|S|-|T|)}f(T) \]二维前缀和：
- \(S(x,y)=\sum_{i\leq x}\sum_{j\leq y}a(i,j)\)；
- \(a(x,y)=S(x,y)-S(x-1,y)-S(x,y-1)-S(x,y-1)+S(x-1,y-1)\)。
鸽巢原理
鸽巢原理：\(n+1\)个球放进\(n\)个桶，一定存在一个桶有不少于\(2\)个球。
推广：\(kn+1\)个球放进\(n\)个桶，存在一个桶有不少于\(k+1\)个球
Q8、Q11：\(n\)个球放进\(m\)个桶，每个桶至多有一个球。
例题：
证明：任意一个大小为\(10\)个集合\(S\subseteq \set{1,...,100}\)存在两个不相交的非空子集\(A,B\subseteq S\)，满足\(A\)和\(B\)的所有元素之和相等。
给一个长为\(n\)的序列\(a\)，找到一个子序列，使得所有元素之和\(\mod n=0\)。
CF 618F Double Knapsack
线性代数
向量和矩阵
向量
一个长为\(n\)的数组，代表一个高维空间中的一个点。
向量运算：
- 加法：\((x+y)_i=x_i+y_i\)。
- 数乘：\((kx)_i=k(x_i)\)。
- 点乘：\(xy=\sum x_iy_i\)（\(xy=yx\)，前者为行向量，后者为列向量）。
矩阵
一个\(n\)行\(m\)列的二位数组。
矩阵运算：
- 加法：\((A+B)_{i,j}=A_{i,j}+B_{i,j}\)。
- 数乘：\((kA)_{i,j}=k(A_{i,j})\)。
- 向量乘：\(m\)和纬度相同。
- 矩阵乘法：前者列数和后者行数相同。满足结合律和分配率，但不满足交换律。
- 矩阵转置：\(A\top_{i,j}=A_{j,i},(AB)\top=B\top A\top\)。
单位矩阵：只有主对角线为\(1\)，其余位置都是\(0\)的方阵，记作\(I\)。
性质：
- \(Ix=x\)；
- \(IA=AI=A\)。
对称矩阵：满足\(A\top=A\)的矩阵。
矩阵快速幂：利用矩阵分配率进行快速幂。可用于多项式快速DP。
例题：
斐波那契数列
Luogu P5059 中国象棋
高斯消元
高斯消元：选择一个方程中的某个变量，将其它方程中的这个变量消掉。
对于\(n\)行\(m\)列的矩阵\(A\)：
- 从\(1\)到\(n\)枚举\(i\)。对于每个\(i\)，找一个最小的\(j\)，使得存在\(i'\ge i\)，\(A_{i',j}\not=0\)；
- 若找到\(j\)，将第\(i'\)行和第\(i\)行交换，这样就可以保证\(A_{i,j}\not=0\)。然后用第\(i\)行对其他行进行消元；
- 否则找不到\(j\)，直接返回，此时只有前\(j-1\)行非零，我们称非零行数为矩阵的秩，记作\(\text{rank}(A)\)；最后得到的矩阵为行标准型矩阵。
时间复杂度为\(O(n^2m)\)。
对于有\(n\)个方程\(m\)个未知数的方程组\(Ax-b=0\)，将\(A\)和\(b\)拼成一个\(n\)行\(m+1\)列的新矩阵\(A'=[A\ \ \ b]\)。对\(A'\)进行高斯消元：
- 若\(\text{rank}(A)=\text{rank}(A')=m\)，则方程有唯一解，解为\(x_i=A'_{i,m+1}\)；
- 若\(\text{rank}(A)=\text{rank}(A')<m\)，则方程有无穷多解；
- 若\(\text{rank}(A)<\text{rank}(A')\)，则方程无解。
int Gauss(vector<vector<int>> &A, int n, int m)
{
for (int i = 0, j = -1; i < n; i++)
{
int r = i;
do
{
if (++j > m)
return i;
for (int k = i; k < n; k++)
if (abs(A[k][j]) > abs(A[r][j]))
r = k;
} while (abs(A[r][j]) <= eps);
if (j >= m)
break;
swap(A[i], A[r]);
for (int l = j + 1; l < m; l++)
A[i][l] /= A[i][j];
A[i][j] = 1;
for (int k = 0; k < n; k++)
{
if (k == i)
continue;
for (int l = j + 1; l < m; l++)
A[k][l] -= A[k][j] * A[i][l];
A[k][j] = 0;
}
}
return n;
}
例题：
Luogu P2455
\(n\)个开关\(m\)个灯，每个开关可以同时控制两个指定的灯。给定灯的初始状态和终末状态，求按开关的方案。
Luogu P10499 开关问题
线性基
线性基：就是模\(2\)意义的高消，支持动态插入行向量。
维护高消后的矩阵的行向量。用\(A_i\)存放最高位为i的行向量，如果不存在这样的向量则\(A_i=0\)。
一开始所有\(A_i=0\)。当插入一个行向量\(x\)，从\(A_n\)到\(A_1\)遍历\(A\)，并检查\(x\)的第\(i\)位：
- 若\(x=0\)则无事发生；
- 若\(x=1\)且\(A_i≠0\)，则令\(x←x⊕A\)；
- 若\(x=1\)且\(A_i=0\)，则令\(A←x\)，并退出循环。
一般用bitset存放\(A_i\),如果维数较低可以用long long。一次插入复杂度\(O(n^2/w)\)。