高斯消元相关知识

一、高斯消元求解线性方程组

Description

　　贾老二是个品学兼优的好学生，但由于智商问题，算术学得不是很好，尤其是在解方程这个方面。虽然他解决 2x=2 这样的方程游刃有余，但是对于 {x+y=3 x-y=1} 这样的方程组就束手无策了。于是他要你来帮忙。前提是一次方程组且保证在integer的范围内可以处理所有问题。

Input

　　第一行一个数字N（1≤N≤100）表示要求的未知数的个数，同时也是所给的方程个数。
　　第2到N+1行，每行N+1个数。前N个表示第1到N个未知数的系数。第N+1个数表示N个未知数乘以各自系数后的加和。（保证有唯一整数解）

Output

　　一行N个数，表示第1到N个未知数的值(四舍五入保留整数)。

Sample Input

2

1 1 3

1 -1 1

Sample Output

2 1

将方阵（显然方阵才有可能有唯一解）消成上三角，例如：

a1 a2 a3 a4 | k1

b1 b2 b3 b4| k2

c1 c2 c3 c4  | k3

d1 d2 d3 d4|k4

消元后，成为如下形式：

 

a1' a2' a3' a4'  | k1'

0   b2' b3' b4'  | k2'

0    0   c3' c4'   | k3'

0    0    0   d4   | k4'

大致步骤：

1）选主元（为了减小误差选取绝对值最大的）

2）消元（对于a[i][i]，使得a[i+1……n][i]=0）

3）回代答案求解

#include<bits/stdc++.h>
using namespace std;
#define Inc(i,L,r) for(register int i=(L);i<=(r);++i)
#define Red(i,r,L) for(register int i=(r);i>=(L);--i)
int n;
double a[110][110];
inline void Xiaoyuan(int x){//第x行 
	int Loc=x,Max=abs(a[x][x]);
	Inc(i,x+1,n)if(abs(a[i][x])>Max)Max=abs(a[i][x]),Loc=i;
	if(Loc^x)Inc(j,x,n+1)swap(a[x][j],a[Loc][j]);
	Inc(i,x+1,n){
		double eph=a[i][x]/a[x][x];
		Inc(j,x,n+1)a[i][j]-=eph*a[x][j];
	}
}
double ans[110];//求解x 
inline void solv(){
	Red(i,n,1){//消成上三角 
		Red(j,n,i+1)a[i][n+1]-=a[i][j]*ans[j];
		ans[i]=a[i][n+1]/a[i][i];
	}
	for(int i=1;i<=n;i++)printf("%.0lf ",abs(ans[i]));// 加绝对值是因为防止-0毒瘤 
}
int main(){
	scanf("%d",&n);
	Inc(i,1,n)Inc(j,1,n+1)scanf("%lf",&a[i][j]);
	Inc(i,1,n-1)Xiaoyuan(i);
	solv();
	return 0;
}

二、高斯消元求逆矩阵

前置知识：

单位方阵E：满足a[i][i]=1其余元素均为0的特殊方阵，如：

100

010

001

依据单位方阵特点：AE=A=EA，在群论中等同幺元

逆矩阵定义：AB=BA=E，称B为A的逆矩阵且可逆矩阵唯一

证明：若B与C同时为A的逆矩阵，则有AB=BA=E，AC=BC=E，则ABC=EC=BAC=BE=B=E

求解过程：

我们在对原矩阵操作的同时，对单位矩阵进行一致的操作（改改变量名，格式不变），操作1将原矩阵消成上三角矩阵，操作2将原矩阵化为单位矩阵，此时，原单位矩阵对应原矩阵的逆矩阵。

代码网上可以找到，因为这个不怎么重要所以就没写

 

三、高斯消元解xor方程组

本代码由DavidLei大佬提供，可以发现与解线性方程组只有符号换成了xor，其余都是一个套路