高斯消元
很普及组，不讲了
当主元没有逆的时候可以辗转相除。
如果也没有带余数除法……没救了
逆矩阵
我们定义矩阵 \(A\) 的逆矩阵为 \(A^{-1}\)，满足 \(AA^{-1}=A^{-1}A=I\)。
有些矩阵可逆，有些不可逆。
求逆矩阵可以用类似高斯消元的方式。就是想象 \(A\) 矩阵的右边是个逆矩阵，等式右边是个单位矩阵，我们就是要解出这个逆矩阵。
具体可以把 \(A\) 消成单位矩阵，那么右边的逆矩阵应该和等式右边的矩阵一样，就求完了。
CF446D
\(n\) 个点的图，\(k\) 个是关键点，要求出从第 \(i(1\le i\le n)\) 个点开始随机游走，第一个碰到的关键点是 \(j(1\le j\le n)\) 的概率。
\(n\le 500\)
（欸，题意真的是这样？）
\(g_i\) 表示期望经过多少次 \(i\) 点。
\[g_i=\sum_{j=1}^np_{j\rightarrow i}g_j+[i=s]\]
把 \(g\) 和 \(p\) 写成矩阵 \(g\) 和 \(P\)（注意 \(g\) 其实是个向量）
\[g=P\times g+\begin{bmatrix}0\\0\\\dots\\1\\0\\\dots\end{bmatrix}\]
\[(I-P)\times g=\dots\]
求逆即可。
矩阵快速幂
更普及组，不讲了
不过有个有趣的东西：
给定 \(n\times n\) 矩阵 \(A\)，\(T\) 组询问，每次给定正整数 \(m\) 和向量 \(b\)，求 \(A^m\times b\)。
大家应该都会 \(O(Tn^3\log m)\)。
但是有更快的做法：
预处理出 \(A^{2^i}\)。这一部分 \(O(n^3\log m)\)。
每次询问发现就是 \(A^{2^{i_1}}\times A^{2^{i_2}}\cdots\times b\)。
从右往左乘可以做到 \(O(Tn^2\log m)\)。
行列式
定义：一个 \(n\times n\) 矩阵 \(A\) 的行列式是：
\[\sum\limits_{G\in S_n}(-1)^{\mathrm{sgn}(G)}\prod A_{i,G_i}\]
\(G\) 是 \(1\) 到 \(n\) 的排列（或者说置换），\(\mathrm{sgn}(G)\) 表示 \(G\) 是偶置换则是 \(0\) 否则是 \(1\)。
有性质：\(\det(AB)=\det(A)\det(B)\)，其中 \(A,B\) 都是 \(n\times n\) 矩阵。
行列式的代数余子式：\(C_{i,j}=(-1)^{i+j}M_{i,j}\)
余子式：\(M_{i,j}\) 表示去掉第 \(i\) 行和第 \(j\) 列后剩下的 \((n-1)\times (n-1)\) 矩阵的行列式。
行列式可以按行展开 \(\det(A)=\sum\limits_{j=1}^na_{i,j}C_{i,j}\)。
有什么用？可以用来求 \(n\) 维?()&)!$()#@>的体积。
比如，以二维为例，一个平行四边形的邻边向量 \(a,b\)，那么它的面积是 \(\det\begin{bmatrix}a.x&a.y\\b.x&b.y\end{bmatrix}\)。
三维同理，一个立方体的？？？向量 \(a,b,c\)，体积是 \(\det\begin{bmatrix}a\\b\\c\\\end{bmatrix}\)。
发现一个三角形的面积是对应的平行四边形的 \(\frac{1}{2}=\frac{1}{2!}\)，一个三棱锥的面积是对应的四棱柱的 \(\frac{1}{6}=\frac{1}{3!}\)。
那么有推论：\(x_i\ge 0,\sum\limits_{i=1}^{d}x_d\le s\) 在 \(d\) 维坐标系上的体积是 \(\dfrac{s^d}{d!}\)。因为 \(\begin{bmatrix}s&0&0&\dots&0\\0&s&0&\dots&0\\\dots\\0&0&0&\dots&s\end{bmatrix}\) 的行列式是 \(s^d\)。
行列式怎么求？对于一个上三角矩阵，行列式是对角线所有数的乘积。
交换两行，行列式不变。一行加上另一行的若干倍，行列式不变。交换两行，行列式变成相反数。
高斯消元即可。
THUPC 2017 E
给 \(n-1\) 维空间中的 \(n+1\) 个点，求他们凸包的体积。
\(n\le 35\)，点的每一维坐标都是 \(0\) 或 \(1\)。
如果是 \(n\) 个点，那就是上面的问题，求个行列式走人。
但是是 \(n+1\) 个点。
有个结论：随便选 \(n\) 个点（\(n+1\) 种选法），求出凸包的体积，它们的和再除以 \(2\) 就是答案。
感受一下发现很对，交了一发也过了（？？？），那就这样了。
矩阵树定理
一个图的生成树个数是度数矩阵减去邻接矩阵，然后去掉一行一列（哪行哪列随便选，但是必须得是第 \(i\) 行第 $i $ 列）的行列式。
推论：完全图的生成树个数是 \(n^{n-2}\)。
对于以 \(i\) 为根的向外树形图个数，变成入度矩阵减去邻接矩阵，去掉第 \(i\) 行第 \(i\) 列的行列式。向内的树形图就变成出度矩阵减邻接矩阵。
Best Theorem
\(n\) 个点的有向图的欧拉回路条数为任意一个点的树形图个数*(所有点出度-1)!的乘积。
UOJ226
\(n\) 个点，边不超过 \(n\) 条的无向连通图，每条边重复 \(t_i\) 次，问欧拉回路个数。
\(n,t\le 1000\)。
对于树的情况，先定向，因为欧拉回路，所以出去的边和回来的边数量相等，那么方案数就是 \(\prod\binom{t_i}{t_i/2}\)。
用上面的定理，随便指定一个根，就是 \(\prod\binom{t_i}{t_i/2}t_i/2\prod(deg_u-1)!\)。
如果有一个环，那么不在环上的边很简单，然后随便选环上一条边，枚举这条边有多少往左多少往右，就能推出来环上所有的边多少向左，多少向右。
\(O(nt)\)。
Band 矩阵
主对角线和左右 \(d\) 条对角线有数，其他都是 \(0\) 的矩阵。
消元可以做到 \(O(nd^2)\)。
例题
\(n\times m\) 的矩阵，求生成树个数。
直接做复杂度太高。发现矩阵实际上是类似 Band 矩阵的，可以稍微优化一下。
CF963E
在平面上走，一开始在原点，每次随机一个方向走 \(1\)（上下左右的概率给定），问走到离原点距离超过 \(r\) 的步数期望。
\(r\le 50\)
弄个矩阵，发现和 Band 矩阵也很像，直接上即可。\(O(r^4)\)。
还有一种更快的方式，给在左半圆周上的每个期望都设个元，那么往右推能用这些元表示每个点的期望。
那么在最右半周上，就可以有一些等式，消元就好了。复杂度变成 \(O(n^3)\)。
线性空间
在一个数域上，关于加减法和数乘的一个封闭空间。
生成空间：对于一个向量组 \(x_i\)，那么其生成空间是 \(\sum a_ix_i(a_i\in \text{向量组定义在的数域})\)。
线性无关：不存在 \(a_i\)（不全为 \(0\)），使得 \(\sum a_ix_i=0\)。
基：极大线性无关组。
维数：基的大小。
秩：生成的线性空间的维数（不就是维数？）（dls：当成一样的应该问题不大）
小结论：\(\bmod p\) 意义下，如果维数是 \(d\)，那么有 \(p^d\) 个元素。
定理：矩阵的行向量的秩（称为行秩）等于列向量的秩（称为列秩）。
求一个矩阵的秩：直接高斯消元，消完后非零向量的个数就是秩。
线性基
数域是 \(F_2\)，每个元素是 \(d\) 维向量的线性空间的基。
以类似高斯消元的方式构造。
那么秩不会超过 \(d\)。
拟阵
md 不想管了……咕了。
看洛咕日报去。
拟阵是二元组 \((V,I)\)，\(V\) 是元素集合，\(I\) 是 \(V\) 的一些子集的集合。
[WC2011]XOR
相信大家都会。
HDU多校1B
……
肯定线性基。对于每个终点都维护一个。
线性基的元素改一改，二元组 \((val,pos)\)，\(val\) 就是值，\(pos\) 是异或出 \(val\) 所用到的数的位置的最小值的最大值。
每次插入一个数，当一位上没有数时，随便搞；当一位上有数时，比较，如果更优就替代，把没那么优的往下继续消。
SRM 620 Hard
……
设一堆变量表示 \((i,j)\) 选不选，然后可以每行列个方程，每列列个方程，每个质因子列个方程。
答案是 \(2^{\text{阶}-\text{秩}}\)。
Cramer 法则
方程组的解 \(x_i=\dfrac{\det(A\text{的第}i\text{列都换成等号右边的东西})}{\det(A)}\)。
伴随矩阵
\(A\) 的余子矩阵……字面意思，\(C\)
\(A\) 的伴随矩阵 \(\mathrm{adj}(A)=C^{T}\)
性质：\(A\mathrm{adj}(A)=\mathrm{adj}(A)A=\det(A)I\)
实际上 \((A\mathrm{adj}(A))_{i,i}=\sum\limits_{j=1}^na_{i,j}C_{i,j}=\det(A),(A\mathrm{adj}(A))_{i,j}=\sum\limits_{k=1}^na_{i,k}C_{j,k}=0(i\ne j)\)。
（前面是上面的推论，后面相当于把第 \(j\) 行变得和第 \(i\) 行一样，此时行列式一定为 \(0\)）
所以，一个矩阵可逆当且仅当其行列式在该数域中可逆。
因为如果 \(A\) 可逆，那么 \(1=\det(I)=\det(AA^{-1})=\det(A)\det(A^{-1})\)，那么 \(A^{-1}=\det(A)^{-1}\mathrm{adj}(A)\)。
……（以后来补）
Schwartz–Zippel 引理
一个多项式在模 \(p\) 意义下，如果每个值都是随机的，那么整个 \(=0\) 的概率不超过次数 \(/p\)
二分图是否存在完备匹配？
（一个矩阵的积和式 \(\mathrm{perm}(A)=\sum\limits_{G\in S_n}\prod\limits_{i=1}^nA_{i,G_i}\)，和行列式相比少乘了符号）
如果把每条边看成一个变量，边 \((u,v)\) 在矩阵第 \(u\) 行第 \(v\) 列加一个 \(x_i\)，那么有完备匹配当且仅当积和式不是 \(0\)。
很好理解，积和式是枚举了每个排列。
如果可以快速算积和式，那么不停给每个变量随机赋值，随机若干次之后若积和式始终为 \(0\)，就没有，否则有。
但是积和式没法快速算。
可以改一下，求行列式。随机交换行列，再计算，抵消成 \(0\) 的概率不大。（是这样吗？？？没听清……）
（这东西和这引理有半毛钱关系吗……）
Tutte 矩阵
定义一个图的 Tutte 矩阵（那个符号不会写，不管了） \((\widetilde{A}(G))_{i,j}=\begin{cases}x_{i,j}&e_{i,j}=1,i<j\\-x_{j,i}&e_{j,i}=1,i>j\\0&other\end{cases}\)。
图 \(G\) 有完备匹配当且仅当 \(\det \widetilde{A}(G)\ne 0\)。
设 \(G\) 是个有完备匹配的图，那么将点 \(i,j\) 从 \(G\) 删掉后仍有完备匹配当且仅当 \((\widetilde{A}(G)^{-1})_{i,j}\ne 0\)。
图 \(G\) 的最大匹配大小是 \(\frac{1}{2}\mathrm{rank}(\widetilde{A}(G))\)。
Sherman–Morrison 公式
\(A\) 是 \(n\times n\) 矩阵，\(u,v\) 是 \(n\) 维列向量。那么 \(A+uv^{T}\) 可逆当且仅当 \(1+v^{T}A^{-1}u\ne 0\)。此时 \((A+uv^{T})^{-1}=A^{-1}-\frac{A^{-1}uv^{T}A^{-1}}{1+v^{T}A^{-1}u}\)。
\(A\) 是 \(n\times n\) 矩阵，\(U\) 是 \(n\times k\) 矩阵，\(V\) 是 \(k\times n\) 矩阵，\(B=A+UV\)，那么，当 \((I_k+VA^{-1}U)\) 可逆时，\(B^{-1}=A^{-1}-A^{-1}U(I_k+VA^{-1}U)^{-1}VA^{-1}\)。
所以可以在 \(O(n^2k)\) 复杂度内将原矩阵加上一个秩为 \(k\) 的矩阵，动态维护逆矩阵。（蛤？咋搞？）
（这种东西毒瘤都不一定会考……）
（咕了）
动态图传递闭包
支持加边删边，和问一点是否可达另一点（就是传递闭包）
设邻接矩阵为 \(A\)，那么传递闭包后邻接矩阵是 \(I+A+A^2+A^3+\dots=\frac{1}{1-A}\)，所以就是动态逆，用上面的方法解决。
ICPC2018 Nanjing F
有向图，随机游走，每条边有概率，对每对点求出期望步数。
\(n\le 500\)
\(f_{i,j}\) 表示从 \(i\) 走到 \(j\) 的期望步数。特别的，\(f_{i,i}=0\)，这样可以避免重复走来走去的问题。
\(f_{i,j}=1+\sum\limits_{k=1}^np_{i,k}f_{k,j}\)
\(g_i\) 表示从 \(i\) 走回 \(i\) 的期望步数。
\(g_i=1+\sum\limits_{k=1}^np_{i,k}f_{k,i}\)
写成矩阵的形式：（\(J\) 是全 \(1\) 矩阵）
\(F=J-G+PF\)
\((I-P)F=J-G\)
现在就是要求 \(G\)。
令 \(q_{k,i}\) 表示从 \(i\) 走 \(k\) 步后停在 \(i\) 的概率。
令 \(\Pi_i=\lim\limits_{k\rightarrow+\infty}q_{k,i}\)。（稳定分布）
此时从 \(i\) 走再走回 \(i\) 期望已经趋于稳定（emmm...dls：不够严谨但的确是对的），所以 \(\lim\limits_{k\rightarrow+\infty}q_{k,i}g_i=1\)。
所以 \(g_i=\frac{1}{\Pi_i}\)。
但是 \(\mathrm{rank}(I-P)=n-1\)，不可逆。
没事，继续消元，那么消出来前 \(n-1\) 行前 \(n-1\) 列，
（不管了不管了…………………………………………………………………………………………）
咕了。
特征值和特征向量
对于 \(n\times n\) 的矩阵 \(A\)，如果存在数 \(\lambda\) 和非零列向量 \(x\) 满足 \(Ax=\lambda x\)，那么 \(\lambda\) 是 \(A\) 的特征值，\(x\) 是 \(A\) 的特征向量。
那么 \(Ax=\lambda I x\)。\((\lambda I-A)x=0\)。因为 \(x\) 不为零向量，所以 \(\det(\lambda I-A)=0\)，也就是 \(\lambda I-A\) 不满秩。
我们称 \(\det(\lambda I-A)=0\) 为 \(A\) 的特征多项式，元是 \(\lambda\)。特征多项式是 \(n\) 次的，他的 \(n\) 个根就是 \(A\) 的所有特征值。（可能有相等的根）
对于上三角矩阵，所有的特征值就是主对角线上的所有值。
如果有 \(n\) 个线性无关的特征向量 \(x_i\)（当且仅当 \(A\) 满秩），那么有 \(A\begin{bmatrix}x_1&x_2&\cdots&x_n\end{bmatrix}=\begin{bmatrix}x_1&x_2&\cdots&x_n\end{bmatrix}\begin{bmatrix}\lambda_1&0&0&\cdots&0\\0&\lambda_2&0&\cdots&0\\\cdots\\0&0&0&\cdots&\lambda_n\end{bmatrix}\)。
相似与对角化
令 \(P=\begin{bmatrix}x_1&x_2&\cdots&x_n\end{bmatrix}\)，（特征向量的矩阵），那么有 \(P^{-1}AP=D\)，其中 \(D\) 是 \(A\) 的特征值对角矩阵。从上面也可以看出来，两边同时左乘 \(P^{-1}\)。
所以有 \(A=PDP^{-1},A^k=\underbrace{PDP^{-1}PDP^{-1}\dots PDP^{-1}}_k=PD^kP^{-1}\)。其实相当于再上面右乘 \(P^{-1}\)。
CF923E
知道要用相似对角化后就是个无脑推式子，没什么技术含量。
Hamilton-Cayley 定理
对于矩阵 \(A\) 的特征多项式 \(f(\lambda)=\sum\limits_{i=0}^nc_i\lambda^i\)，有 \(f(A)=0\)，即 \(\sum\limits_{i=0}^nc_iA^i=0\)。
常系数齐次线性递推
给定数列 \(f\) 的 \(f_0\) 到 \(f_{k-1}\)，有递推公式 \(f_n=\sum\limits_{i=1}^ka_if_{n-i}\)，求第 \(n\) 项。
\(n\le 10^9,k\le 3\times 10^4\)。
Berlekamp-Massey 算法
\(O(n^2)\) 求解一个序列的最短递推式。
至于怎么求解>@!&#(*!%)多项式，咕了。