Gaussian elimination acwing 884. Gaussian elimination for solving XOR linear equations

Gauss elimination AcWing 884. Gauss elimination is used to solve XOR linear equations

Original link

AcWing 884. Gauss elimination is used to solve XOR linear equations

Algorithm tags

Linear space Gauss elimination Exclusive or

Ideas

Code

#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(){//  Gauss elimination , The answer lies in a[i][n] in ,0 <= i < n
    // c Representative column  r On behalf of the line 
    int c, r;
    //  Enumerate by column 
    for(c=0, r=0; c<n; ++c){
        int t=r;
        rep(i, r, n){
            if(a[i][c]){//  Find non-zero line 
                t=i;
                break;
            }
        }
        if(!a[t][c]){
            continue;
        }
        rep(i, c, n+1){//  Change non-zero lines to the top 
            swap(a[r][i], a[t][i]);
        }
        rep(i, r+1, n){//  Use non-zero rows and the following columns to eliminate as 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;//  unsolvable 
            }
        }
        return 1;//  There are infinite sets of solutions 
    }
    Rep(i, n-1, 0){
        rep(j, i+1, n){
            a[i][n]^=a[i][j]*a[j][n];
        }
    }
    return 0;//  There is a unique solution 
}
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;
}

Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support