专栏文章

腾飞计划寒假第四课——高斯消元 2025/2/5

LLovely_yhb
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqc4vv2
此快照首次捕获于
2025/12/04 02:23
3 个月前
此快照最后确认于
2025/12/04 02:23
3 个月前
查看原文

高斯消元

系数矩阵做三种变化：
  1. 将某一行乘上 kk。
  2. 将某一行加到另一行。
  3. 交换两行。
最后消成主对角线是 11，最后一列是答案，剩下的是 00。
结果：
  1. 如果仅最后一列非 00，则方程无解。
  2. 如果某一行全都是 00。
  3. 否则有唯一的解。
例子看蓝书。
一开始尽可能选最大的，防止乘上一个超级大的数爆 double。

P2447 [SDOI2010] 外星千足虫

用异或来判断奇偶性是否相同。
把高斯消元的过程改成异或。
异或高斯消元。

P3164 [CQOI2014] 和谐矩阵

上下左右和它本身的异或和是 00，可以列出很多方程。异或压位一下就过了。

P2962 [USACO09NOV] Lights G

根据邻接矩阵列出高斯消元矩阵，异或消元消完之后得到这个点操作还是不操作。
如果存在某行全 00，说明这是个自由元，需要搜一下统计最少操作次数。

P5027 Barracuda

枚举哪一遍称重是错的，然后正常做就行。

P2973 [USACO10HOL] Driving Out the Piggies G

fxf_x 表示在 xx 爆炸的概率，dxd_x 表示与 xx 相连的边数。
f1=pq+∑yy→1fy×(1−pq)×1dyf_1=\displaystyle\frac{p}{q}+\displaystyle\sum_y^{y\rarr1}f_y\times(1-\displaystyle\frac{p}{q})\times\displaystyle\frac{1}{d_y}。
对于除 11 以外的点 xx，fx=∑yy→xfy×(1−pq)×1dyf_x=\displaystyle\sum_y^{y\rarr x}f_y\times(1-\displaystyle\frac{p}{q})\times\displaystyle\frac{1}{d_y}。
每个点和与它连边的点列出方程，高斯消元去做。

矩阵求逆

求对矩阵做什么操作可以将 AA 变成 II，对 II 作同样操作就是 A−1A^{-1}。
将 AA 和 II 拼在一起，变成 nn 行，n×2n\times2 列的矩阵。
把左边 nn 列消成主对角线是 11，其余是 00 的形式，右边也做相同操作，右边 nn 列就是逆矩阵。
如果无法消出左边主对角线全是 11，说明有无限个解，说明矩阵没有逆。

高斯消元计算行列式

行列式是根据 n×nn\times n 的矩阵 AA 算出来的一个数
是这么算的：
枚举 nn 的全排列 a1,a2,a3,…,ana_1,a_2,a_3,\dots,a_n，设 kk 表示这个排列中的逆序对个数。
累加 (−1)k×A1,a1×A2,a2×A3,a3×⋯×An,an(-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. 对于一个上三角矩阵，行列式的值就是主对角线的数乘积。
  2. 单位矩阵的行列式为 11。
  3. 交换两行，行列式变号。
  4. 将矩阵某一行乘上常数，行列式乘上常数。
  5. 若矩阵有相同的两行，则行列式为 00。
  6. 托矩阵有两行存在倍数关系，则行列式为 00。
  7. 若两个矩阵至多有一行不等，则将这不等的一行相加得到的新矩阵的行列式等于原行列式的和。
  8. 将矩阵的某一行加上另一行的倍数，行列式不变。
根据性质 33 和性质 88，可以用高斯消元做。

矩阵树定理

给出一个图，求生成树个数。
矩阵树定理：
令 DD 为图的度数矩阵，AA 为图的邻接矩阵，令 G=D−AG=D-A。
设 GG 的大小为 k×kk\times k。
那么 GG 的任一 (k−1)(k-1) 次主子式 ∣G′∣|G'| 为该无向图的生成树个数
(k−1)(k-1) 次主子式 G′G' 就是 GG 的大小为 (k−1)×(k−1)(k-1)\times (k-1) 的子矩阵的行列式。
可以证明任意一个 (k−1)(k-1) 次主子式是相等的。
有向图分为外向生成树和内向生产树，将 DD 换成出度矩阵和入度矩阵即可。
有向图因为是以 11 为根，所以是删掉第 11 行第 11 列之后的子矩阵。
证明我显然是不会的，因为这需要会很多线性代数知识。

ABC366G XOR Neighbors

像 P2962 一样每个点与和它的相邻的点列方程。最后一列为 00，异或高斯消元。消完之后考虑，对于每一位，若其为自由元，则赋上一个从未赋过的二进制位的值，否则直接赋答案。
在赋值过程中判断是否无解。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...