又是一个学一遍忘一遍的算法···

引入

高斯消元，是一个用来求解线性方程组的算法。

线性方程组是形如这样的方程组

$$\begin{cases} a_{1,1}x_1+a_{2,1}x_2+\cdots+a_{n,1}x_n\ \ = b_1 \\ a_{1,2}x_1+a_{2,2}x_2+\cdots+a_{n,2}x_n\ \ = b_2 \\ \cdots \\ a_{1,n}x_1+a_{2,n}x_2+\cdots+a_{n,n}x_n\ \ = b_n \end{cases}$$

实现

思路很简单，我们先把系数矩阵消成对角线形式，然后就可以得到解了。

但是会涉及到除法，所以我们要尽量减少精度误差。

解决方法是：对于每一个未知量，我们都找到系数的绝对值最大的那一项，让它去把别人消掉。

然后代码就不难得出了。

复杂度 $O(n^3)$

inline void Gauss(){
    for(re int i=1,pos;i<=n;++i){//当前在消哪一个未知量
        pos=0;
        for(re int j=i;j<=n;++j){
            //找到系数最大的那一行
            if(fabs(a[j][i])>fabs(a[pos][i])) pos=j;
        }
        //如果不存在就跳过
        if(fabs(a[pos][i])<eps) continue;
        //把这一行换到第i行
        swap(a[i],a[pos]);
        for(re int j=1;j<=n;++j){
            //把其他行的第i个未知量的系数消掉
            if(j==i) continue;
            double bs=a[j][i]/a[i][i];
            //枚举列，把第j行的所有系数都减去对应的值
            for(re int k=i;k<=n+1;++k) a[j][k]-=bs*a[i][k];
        }
    }
    for(re int i=1;i<=n;++i){
        if(fabs(a[i][i])<eps){//第i个未知数的系数为0（小于eps可以视为0）
            if(fabs(a[i][n+1])>eps){//但对应的值却不是0，说明无解
                cout<<"No Solution";
                return;
            }
            else{//对应值也为0，则该未知数可以随意取值，说明有无数解
                //这种未知数称为自由元
                cout<<"Numerous Solutions";
                return;
            }
        }
    }
}

upd：上面这份代码有锅···

在判断无解和无数解时会出问题，这是因为我们的答案受到消元顺序影响。

详见这篇题解。

下面是一份正确的代码：

inline void gauss(){
    for(re int i=1;i<=n;++i){
        int id=i;
        for(re int j=1;j<=n;++j){
            if(fabs(a[j][j])>eps&&j<i) continue;
            if(fabs(a[j][i])>fabs(a[id][i])) id=j;
        }
        if(fabs(a[id][i])<=eps) continue;
        swap(a[i],a[id]);
        for(re int j=1;j<=n;++j){
            if(i==j) continue;
            double delta=a[j][i]/a[i][i];
            for(re int k=i;k<=n+1;++k) a[j][k]-=delta*a[i][k];
        }
    }
    int flag=1;
    for(re int i=1;i<=n;++i){
        if(fabs(a[i][i])<=eps){
            if(fabs(a[i][n+1])>eps) flag=-1;
            else if(~flag) flag=0;
        }
    }
    if(flag!=1){
        if(flag==-1) cout<<"No Solution";
        else cout<<"Numerous Solutions";
        return;
    }
    for(int i=1;i<=n;i++) a[i][n+1]/=a[i][i];
}

拓展

异或方程组

因为异或满足交换律和结合律，所以可以像普通高斯消元那样进行消元。

只不过把加减消元换成了异或消元。

因为涉及位运算，所以可以 bitset 优化。

复杂度 $O(\frac {n^3}{\omega})$

bitset<maxn> a[maxn];
inline void Gauss(){
    for(re int i=1;i<=n;++i){
        int pos=i;
        while(pos<=m&&!a[pos][i]) ++pos;
        if(pos>m){cout<<"No Solution";return;}
        if(pos!=i) swap(a[pos],a[i]);
        for(re int j=1;j<=m;++j) if(i!=j&&a[j][i]) a[j]^=a[i];
    }
    for(re int i=1;i<=n;++i) cout<<a[i][0]<<'\n';
}