高斯消元 AcWing 884. 高斯消元解异或线性方程组

墨蓝 2023-09-28 13:38 16阅读 0赞

## 高斯消元 AcWing 884. 高斯消元解异或线性方程组 ##

### 原题链接 ###

[AcWing 884. 高斯消元解异或线性方程组][AcWing 884.]

### 算法标签 ###

线性空间 高斯消元 异或

### 思路 ###

![在这里插入图片描述][b0bc575bfb46462d93d99977f8b5fe76.png]

### 代码 ###

#include<bits/stdc++.h>
    #define int long long
    #define abs fabs
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>=b;--i)
    using namespace std;
    const int N = 105;
    int a[N][N], eps = 1e-8;
    int n;
    inline int read(){
       int s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
       while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
       return s*w;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    int gu(){// 高斯消元，答案存于a[i][n]中，0 <= i < n
        // c代表列 r代表行
        int c, r;
        // 按列枚举
        for(c=0, r=0; c<n; ++c){
            int t=r;
            rep(i, r, n){
                if(a[i][c]){// 找非零行
                    t=i;
                    break;
                }
            }
            if(!a[t][c]){
                continue;
            }
            rep(i, c, n+1){// 将非零行换到最顶端
                swap(a[r][i], a[t][i]);
            }
            rep(i, r+1, n){// 用非零行与下面列进行运算消除为0
                if(a[i][c]){
                    Rep(j, n, c){
                        a[i][j]^=a[r][j];
                    }
                }
            }
            ++r;
        }
        if(r<n){
            rep(i, r, n){
                if(abs(a[i][n])>eps){
                    return 2;// 无解
                }
            }
            return 1;// 有无穷多组解
        }
        Rep(i, n-1, 0){
            rep(j, i+1, n){
                a[i][n]^=a[i][j]*a[j][n];
            }
        }
        return 0;// 有唯一解
    }
    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        n=read();
        rep(i, 0, n){
            rep(j, 0, n+1){
                a[i][j]=read();
            }
        }
        int t=gu();
        if(t==2){
            puts("No solution");
        }else if(t==1){
            puts("Multiple sets of solutions");
        }else{
            rep(i, 0, n){
                printf("%lld\n", a[i][n]);
            }
        }
        return 0;
    }

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 884.]: https://www.acwing.com/problem/content/886/
[b0bc575bfb46462d93d99977f8b5fe76.png]: https://img-blog.csdnimg.cn/b0bc575bfb46462d93d99977f8b5fe76.png
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://img-blog.csdnimg.cn/9cb4cb80a18345158f8a69e2f196e5b9.png