目录
原文链接
0x00 行列式
0x01 定义
关于数学定义式：$$\sum_{p}(-1)^{\tau(p)} \prod_{i=1}^{n}A_{i,p_i}$$
以简单的\(3\times 3\)行列式举例子。
在第二行中的正负1部分表示的就是行列式计算中正负号的选择。后面跟的求积就是行列式展开的乘积关系。
为什么行列式与逆序数有关？
逆序数就是n个数的一个任意排列经过多少次对调变成自然数列的次数，这两个数可能不一样，但是奇偶性一样，而行列式每项的符号只和奇偶性有关。
0x02 基本性质
\(\centerdot\) Lemma 1 根据定义易证。注意\(a_{i,p_i}\)不能为零。
\(\centerdot\) Lemma 2 同 Lemma 1
\(\centerdot\) Lemma 3 交换行会改变奇偶性，产生或减少逆序对个数。注意横行数列（针对\(A_{i,j}\)而言）
\(\centerdot\) Lemma 4 公式后半部分可以使用乘法分配律。
\(\centerdot\) Lemma 5 乘以0，你说呢？
\(\centerdot\) Lemma 6 略。
\(\centerdot\) Lemma 7 感性理解
\(\centerdot\) Lemma 8 希望轻松的证明？
0x10 高斯消元法
0x11 算法介绍
注意关于有无解、有无数解方法。
0x12 矩阵求逆
时间复杂度：\(O(n^3)\)。
感觉介绍的不是很详细，而且看code好像也不是直接带入高斯板子，有不少细节处理：
1. 通过求解逆元的方式可以有效的避免精度误差，因此可以不必关心eps问题
2. \(b[][]\)数组中的情况和\(a[][]\)可能完全不同，部分for循环的起点要从1开始
3. 由于2的情况出现 我们在取值时候要小心 可能会发生改变 所以取出来命名变量是较好的选择。
0x13 求行列式
本质：将矩阵\(A\)转化为上三角矩阵，利用行列式性质直接求出行列式 (Lemma 1 3 4 8)
这篇题解感觉讲的很好，还提及了有关排序奇偶性相关的知识。
0x20 矩阵树定理
0x21 算法介绍
- 主子式：对于一个矩阵 删除掉k行k列（不一定连续）之后剩下的矩阵（可以是单个元素，视为\(1\times 1\)矩阵）就是主子阵，其行列式称为主子式。
- 注意是无向图。
- 自环和重边对\(D\)和\(E\)矩阵的影响会相互抵消：感性理解,自于\(K=D-E\)
0x22 有向图生成树个数
只关注入度，其他与无向图相同，只不过根节点被固定。（截取主子阵时候的r被固定）。
分为外向生成树和内向生成树。外向生成树使用入度矩阵，内向生成树使用出度矩阵。
0x23 边权积的和
相当于有\(w\)条\((u , v)\)边。
0x24 边权和的和【咕咕咕】
？没太看懂。
0x25 例题
P6178 【模板】Matrix-Tree 定理
链接注意其与高斯消元的关系仅限于求行列式的值。但是和板题不同的是，板题模数不一定是质数，所以只能用辗转相除法；而此题可以直接使用逆元求解。
P3317 [SDOI2014] 重建
链接woc有点牛逼啊！考虑矩阵树定理只能求解：$$\sum_{T} \prod_{e\in T}p_e$$
其中\(p_e\)可以被替换成边的个数（边权）来计算生成树个数。
也就是说是边的性质。
考虑对式子化简 可以提取公因式构造出来单独的一部分（与其他的独立）使用矩阵树定理解决。