风灵无畏OI
此站用来记录个人的OI成长史，以后会将个人做的每道题的解题报告发到此站上来，希望大家喜欢！（如有讲得不好的地方请大家指出，我会加以改进。当然也有可能传上来一点乱七八糟的东西）
注：转载文章请标上原址，毕竟码字很辛苦！谢谢！
高斯消元法（不完整版）
【概念】
（大家也可以先不看这一部分，可以后先跳过这一部分，但本人建议还是先看一下为好）
线性方程组：https://tzdyy.lofter.com/post/1e3cd119_e2bdf1b
增广矩阵： https://tzdyy.lofter.com/post/1e3cd119_e2bdefc
矩阵的秩： https://tzdyy.lofter.com/post/1e3cd119_e2bdf0e
友情链接： https://liaoy148.lofter.com/post/1da8a74e_bab1d62
【高斯消元】
我们知道解一元一次方程，二元一次方程，一元二次方程甚至三元一次方程，但是更多元或者更高次的方程，我们可能就不会了，或者用脑子搞出来就会很繁琐。而对于四元及以上的多元一次方程便可以用计算机来解决。
我们首先定义一个增广矩阵，有系数及右边的常数组成。（具体可见上面的链接）
现在假设有这么一个方程组：
2x + 3y + 11z + 5w = 2
x + y + 5z + 2w = 1
2x + y + 3z + 2w = -3
x + y + 3z + 4w = -3
现在我们把它编一个号：
2x + 3y + 11z + 5w = 2 （1）
x + y + 5z + 2w = 1 （2）
2x + y + 3z + 2w = -3 （3）
x + y + 3z + 4w = -3 （4）
我们把它转成一个增广矩阵：
2 3 11 5 2
1 1 5 2 1
2 1 3 2 -3
1 1 3 4 -3
第一步：我们把第（1）行的都乘以1/2，于是就变成了这样
1 3/2 11/2 5/2 1
1 1 5 2 1
2 1 3 2 -3
1 1 3 4 -3
然后再把（1）* -1 + （2）去更新（2）
把（1）* -2 +（3）去更新（3）
把（1）* -1 +（4） 去更新（4）
于是我们便得到一个新的矩阵：
1 3/2 11/2 5/2 1
0 -1/2 -1/2 -1/2 0
0 -2 -8 -3 -5
0 -1/2 -5/2 3/2 -4
第二步：我们再把（2）*-2于是就变成了这样
1 3/2 11/2 5/2 1
0 1 1 1 0
0 -2 -8 -3 -5
0 -1/2 -5/2 3/2 -4
然后再把（2）*2+（3）去更新（3）
把（2）*1/2+（4）去更新（4）
于是我们便得到一个新的矩阵：
1 3/2 11/2 5/2 1
0 1 1 1 0
0 0 -6 -1 -5
0 0 -2 2 -4
第三步：我们再把（3）*-1/6于是就变成了这样
1 3/2 11/2 5/2 1
0 1 1 1 0
0 0 1 1/6 5/6
0 0 -2 2 -4
然后再把（3）*2+（4）去更新（4）
1 3/2 11/2 5/2 1
0 1 1 1 0
0 0 1 1/6 5/6
0 0 0 7/3 -7/3
第四步：我们再把（4）*3/7于是就变成这样
1 3/2 11/2 5/2 1
0 1 1 1 0
0 0 1 1/6 5/6
0 0 0 1 -1
当然，如果消元消到最后发现a[n,0]<>0而a[n,n]=0，那么证明无解了（一定是无解，否则在之前就已经因为上述理由而结束程序）。而我们要知道这个方程组它是无解还是有无穷解，则可以用上面提到的去看矩阵的秩来判断。
第五步：回代
当我们做完第四部之后，我们便可以解出w了，因为此时的方程（4）可以表示为1*w=-1，于是我们可以得到w=-1，接着方程三便可以表示为1*z+1/6*w=5/6，得到z=1，继续往上做，便可得到y=0，x=-2。
例题链接：https://www.luogu.org/problem/show?pid=3389
【程序代码】（由于现在还没写，所以就先把学长的代码给放上来了QWQ）
pascal版：（liaoy大师的，大家可以自行理解一下）
type
func=array[0..1000] of double;//方程
var
a:array[1..1000] of func;//增广矩阵
x:array[1..1000] of double;//解
n,i,j:longint;
function count(i:longint):double;//求x[i]
var
vi:longint;
t:double;
begin
t:=0;
for vi:=i+1 to n do
t:=t+x[vi]*a[i,vi];//计算除了当前要求的x以外其他的数之和
t:=a[i,0]-t;
x[i]:=t/a[i,i];
exit(x[i]);
end;
function minus(x,y:func):func;//方程相减
var
vi:longint;
begin
fillchar(minus,sizeof(minus),0);
for vi:=0 to n do
minus[vi]:=x[vi]-y[vi];
end;
function multiply(x:func;y:double):func;//方程乘上一个数
var
vi:longint;
begin
fillchar(multiply,sizeof(multiply),0);
for vi:=0 to n do
multiply[vi]:=x[vi]*y;
end;
procedure gaosi(i,j:longint);//一个方程i消i+1到n的一个元
var
l1,l2:double;
vi:longint;
t:func;
begin
t:=a[i];//之后要把这个玩意还原到原来的数，否则会越来越大更加容易溢出
l1:=a[i,i];
l2:=a[j,i];
a[j]:=multiply(a[j],l1);
a[i]:=multiply(a[i],l2);
a[j]:=minus(a[i],a[j]);
a[i]:=t;
end;
procedure aswap(var a,b:func);//交换方程
var
c:func;
begin
c:=a;
a:=b;
b:=c;
end;
procedure not0(i:longint);//若当前方程要消的元的系数为0，就找一个去换
var
vi:longint;
begin
for vi:=i+1 to n do
if a[vi,i]<>0 then
begin
aswap(a[i],a[vi]);
exit;
end;
writeln('No check answer');//找不到去换
halt;
end;
begin
read(n);
for i:=1 to n do
begin
for j:=1 to n do//读入
read(a[i,j]);
read(a[i,0]);
end;
for i:=1 to n-1 do//高斯消元
begin
if a[i,i]=0 then not0(i);//判断是否需要换方程
for j:=i+1 to n do
if a[j,i]<>0 then gaosi(i,j);//把i+1到n的方程全部消一个元
end;
if (a[n,0]<>0) and (a[n,n]=0) then//判断是否无解
begin
writeln('No check answer');
halt;
end;
for i:=n downto 1 do//计算x
count(i);
for i:=1 to n do
writeln('x',i,'=',x[i]:0:6);//输出
end.