从老贾给我看去年山东省选的材料我才接触的这个东西。貌似是Day 1的第二题那个火星虫（资料都放学校电脑里了囧……），感觉高斯消元真是一个好深奥的东西啊……Orz……

高斯消元主要是用来解线性方程组，或求矩阵的秩，以及求出可逆方阵的逆矩阵。后两个我没大见过，其用途应该主要就是解线性方程组。

“想必高斯消元解线性方程组一定很复杂且很高效吧？”

先声明：高斯消元的程序也就20行，复杂度是O(n^3)的。

那么怎么消元呢？举个例子 x+3y=11 ①

2x+2y=10 ② (因为没法插入公式，所以就这样代表方程组了)

这个方程组可以很轻易得解得x=2,y=3.解的方法就是把②-①×2消去未知数x，得到y=3，然后将y代入①得到x。

这就是高斯消元。（简单吧？小学就会了）

那么再举一个复杂一点的例子 2x + y - z = 8 ①

-3x - y + 2z = -11 ②

-2x + y + 2z = -3 ③

将①×3/2+②消去②中的x，①+③消去③中的x，得到

2x + y - z = 8 ④

1/2 y + 1/2 z = 1⑤

-z = 1 ⑥

将⑤×（-4）+⑥消去⑥中的y，就得到了z=-1 . 然后将z代入⑤得到y=3 ，再代入①得到x=2 。

但是数学中的高斯消元这样就可以了，但是信息学奥赛里面肯定还不行。总不能开一个string数组把方程一个一个存进去……所以需要使用另一种方程的表达方式：行梯阵式。

行梯阵式的表达方法。在刚才的例子里面，原方程组可以表示为系数矩阵

2 1 -1 8

-3 -1 2 -11

-2 1 2 -3

经过第一步消去x之后，矩阵变为

2 1 -1 8

0 1/2 1/2 1

0 0 -1 1

这就是一个行梯阵式。

行梯阵式的条件：1、第一个不是全为0的行的第一个非0项是1 。

2、在这个非0项的下方全是0 。

3、第k行比k+1行的第一个非零项之前的0少，全为0的行放在非0行的下方。