腾飞计划寒假第四课——高斯消元 2025/2/5
Lovely_yhb
·
·
个人记录
高斯消元
系数矩阵做三种变化：
- 将某一行乘上 k。
- 将某一行加到另一行。
- 交换两行。
最后消成主对角线是 1，最后一列是答案，剩下的是 0。
结果：
- 如果仅最后一列非 0，则方程无解。
- 如果某一行全都是 0。
- 否则有唯一的解。
例子看蓝书。
一开始尽可能选最大的，防止乘上一个超级大的数爆 double。
P2447 [SDOI2010] 外星千足虫
用异或来判断奇偶性是否相同。
把高斯消元的过程改成异或。
异或高斯消元。
P3164 [CQOI2014] 和谐矩阵
上下左右和它本身的异或和是 0，可以列出很多方程。异或压位一下就过了。
P2962 [USACO09NOV] Lights G
根据邻接矩阵列出高斯消元矩阵，异或消元消完之后得到这个点操作还是不操作。
如果存在某行全 0，说明这是个自由元，需要搜一下统计最少操作次数。
P5027 Barracuda
枚举哪一遍称重是错的，然后正常做就行。
P2973 [USACO10HOL] Driving Out the Piggies G
$f_1=\displaystyle\frac{p}{q}+\displaystyle\sum_y^{y\rarr1}f_y\times(1-\displaystyle\frac{p}{q})\times\displaystyle\frac{1}{d_y}$。
对于除 $1$ 以外的点 $x$，$f_x=\displaystyle\sum_y^{y\rarr x}f_y\times(1-\displaystyle\frac{p}{q})\times\displaystyle\frac{1}{d_y}$。
每个点和与它连边的点列出方程，高斯消元去做。
## 矩阵求逆
求对矩阵做什么操作可以将 $A$ 变成 $I$，对 $I$ 作同样操作就是 $A^{-1}$。
将 $A$ 和 $I$ 拼在一起，变成 $n$ 行，$n\times2$ 列的矩阵。
把左边 $n$ 列消成主对角线是 $1$，其余是 $0$ 的形式，右边也做相同操作，右边 $n$ 列就是逆矩阵。
如果无法消出左边主对角线全是 $1$，说明有无限个解，说明矩阵没有逆。
## 高斯消元计算行列式
行列式是根据 $n\times n$ 的矩阵 $A$ 算出来的一个数
是这么算的：
枚举 $n$ 的全排列 $a_1,a_2,a_3,\dots,a_n$，设 $k$ 表示这个排列中的逆序对个数。
累加 $(-1)^k\times A_{1,a_1}\times A_{2,a_2}\times A_{3,a_3}\times\dots\times A_{n,a_n}
行列式的性质
- 对于一个上三角矩阵，行列式的值就是主对角线的数乘积。
- 单位矩阵的行列式为 1。
- 交换两行，行列式变号。
- 将矩阵某一行乘上常数，行列式乘上常数。
- 若矩阵有相同的两行，则行列式为 0。
- 托矩阵有两行存在倍数关系，则行列式为 0。
- 若两个矩阵至多有一行不等，则将这不等的一行相加得到的新矩阵的行列式等于原行列式的和。
- 将矩阵的某一行加上另一行的倍数，行列式不变。
根据性质 3 和性质 8，可以用高斯消元做。
矩阵树定理
给出一个图，求生成树个数。
矩阵树定理：
令 D 为图的度数矩阵，A 为图的邻接矩阵，令 G=D-A。
设 G 的大小为 k\times k。
那么 G 的任一 (k-1) 次主子式 |G'| 为该无向图的生成树个数
可以证明任意一个 $(k-1)$ 次主子式是相等的。
有向图分为外向生成树和内向生产树，将 $D$ 换成出度矩阵和入度矩阵即可。
有向图因为是以 $1$ 为根，所以是删掉第 $1$ 行第 $1$ 列之后的子矩阵。
证明我显然是不会的，因为这需要会很多线性代数知识。
### [ABC366G XOR Neighbors](https://www.luogu.com.cn/problem/AT_abc366_g)
像 P2962 一样每个点与和它的相邻的点列方程。最后一列为 $0$，异或高斯消元。消完之后考虑，对于每一位，若其为自由元，则赋上一个从未赋过的二进制位的值，否则直接赋答案。
在赋值过程中判断是否无解。