高斯消元是解决一类线性多元方程组的利器。
举个例子，如果让你求解如下的方程，你该怎么办？
正常人的思路差不多就是加减消元/代入消元，最后解出来所有答案。
下面我们来模拟一下正常人的解题过程：
$(-3)\times①+②:0x - y - 2z = -4$
$①+③:0x + 3y + 2z = 8$
所以有
发现$x$消不了了，开始消$y$.
$②\times3+③:-4z = -4.$
于是解得：
这时候就可以把$z$带回去解别的。
代入$②:0x-y-2=-4$
解得
然后带回$①:x=-1.$
然后就解完了。
考虑把解题过程中的$x,y,z$项写成矩阵。
所以一开始的矩阵就是
$\begin{bmatrix}
x & y & z & val
\\ 2 & 1 & 1 & 1
\\ 6 & 2 & 1 & -1
\\ -2 & 2 & 1 & 7
\end{bmatrix}$
消完$x$之后：
$\begin{bmatrix}
x & y & z & val
\\ 2 & 1 & 1 & 1
\\ 0 & -1 & -2 & -4
\\ 0 & 3 & 2 & 8
\end{bmatrix}$
消完$y$之后：
$\begin{bmatrix}
x & y & z & val
\\ 2 & 1 & 1 & 1
\\ 0 & -1 & -2 & -4
\\ 0 & 0 & -4 & -4
\end{bmatrix}$
发现矩阵中的0元素构成了一个上三角，我们称这玩意为”上三角矩阵”。
显然，最理想情况一定是构成这玩意，直接一直回代就可以了。
那么我们来分析一下多个解或无解的情况：
无解：一行系数全0，但$val ≠ 0$.
多个解：好几行系数和$val$全是0.
分析完了。如何实现？
算法流程：一项一项消。
消到第i项的时候，找系数绝对值最大的（好判断无解）来作为主式子。
然后硬消就行了。
附$Luogu$模板题代码：
1 | /** |