高斯消元总结（个人笔记）
柒葉灬
2018-12-23 22:00:37
# 高斯消元
-----
高斯消元的复杂度: $O(n^3)$
给定$n$未知数和$m$个 ** $n$元$1$次方程
**，在$O(n^3)$的时间内求出解。
例如：
$$\begin{cases}a_{11}x_1+a_{12}x_2+a_{13}x_3=y_1\\a_{21}x_1+a_{22}x_2+a_{23}x_3=y_2\\a_{31}x_1+a_{32}x_2+a_{33}x_3=y_3\end{cases}$$
-------
模板：
```cpp
int Gauss(){
int col=1,k=1;//col表示第几个未知数，k表示第几个方程
for(;col<=n && k<=m;col++,k++){
int r=k;
for(int i=k+1;i<=m;i++)
if(fabs(a[i][col])>fabs(a[r][col]))r=i;
if(r!=k){
for(int i=col;i<=n+1;i++)
swap(a[r][i],a[k][i]);
}
if(fabs(a[k][col])<eps){
k--;
continue;
}
for(int i=k+1;i<=m;i++){
if(fabs(a[i][col])<eps)continue;
double p=a[i][col]/a[k][col];
for(int j=col;j<=n+1;j++)
a[i][j]-=a[k][j]*p;
}
}
for(int i=k;i<=m;i++)
if(fabs(a[i][n+1])>eps)return -1;
//方程左边为0 但方程右边不是0 所以无解
if(k<=n)return n-k+1;
//返回自由元的个数，注意是用了k-1个方程
for(int i=n;i>=1;i--){
double tmp=a[i][n+1];
for(int j=i+1;j<=n;j++)
tmp-=a[i][j]*x[j];
x[i]=tmp/a[i][i];
}
return 0;
//表示有解
}
```
-------
## 高斯消元——异或方程组
本质上和上面的方程组没什么区别，就是稍微改一下就可以了。
形如：
$$\begin{cases}(a_{11}*x_1) \bigoplus (a_{12}*x_2) \bigoplus (a_{13}*x_3)=y_1\\(a_{21}*x_1) \bigoplus (a_{22}*x_2) \bigoplus (a_{23}*x_3)=y_2\\(a_{31}*x_1) \bigoplus (a_{32}*x_2) \bigoplus (a_{33}*x_3)=y_3\end{cases}$$
需要注意的是，系数 $a$ , 未知数 $x$ , 结果 $y$ 必须都是$0$或者$1$.
-------
模板：
```cpp
int Gauss(){
int col=1,k=1;
for(;col<=n && k<=m;col++,k++){
int r;
for(int i=k;i<=m;i++)
if(a[i][col]==1){
r=i;
break;
}
if(r!=k){
for(int i=col;i<=n+1;i++)
swap(a[k][i],a[r][i]);
}
if(a[k][col]==0){
k--;
continue;
}
for(int i=k+1;i<=m;i++){
if(a[i][col]==0)continue;
for(int j=col;j<=n+1;j++)
a[i][j]^=a[k][j];
}
}
for(int i=k;i<=m;i++)
if(a[i][n+1]!=0)return -1;
if(k<=n)return n-k+1;
for(int i=k-1;i>=1;i--){
int p=a[i][n+1];
for(int j=i+1;j<=n;j++)
p^=a[i][j]*x[j];
x[i]=p;
}
return 0;
```
-------
顺便写一道题解：[HDU3915](http://acm.hdu.edu.cn/showproblem.php?pid=3915)
题目大意：给 $n$ 个数字，去掉其中的一些数字（也可以不去），使得剩下的数异或和为0，问总的方案数？
我们可以列出一条方程：
$$ (a_1*A_1) \bigoplus (a_2*A_2) \bigoplus ... \bigoplus (a_n*An)=0$$
但显然这样是不行的，因为 $A_i$ 不一定是 $0$ 或 $1$。所以需要拆分，考虑拆成$31$位，这样我们就能得到$31$条方程，满足了异或方程解出来的条件（未知数只能是$01$）。
接下来考虑答案，显然如果方程有唯一解的话，那么 $ans=1$ ，
如果不是唯一解，说明就有多个自由元，
如果自由元的个数是 $K$ 个的话，那么 $ans=2^K$
-----
>补充一下自由元与主元的关系：
>
>$$\begin{cases} x_1=a_1x_3+a_2x_4+a_3x_5\\x_2=b_1x_3+b_2x_4+b_3x_5 \end{cases}$$
>
>如果自由元每一个都确定了，那么主元也就全部确定了，因为自由元的方案数总共是$2^K$，所以所有解的个数也就是$2^K$
-----