高斯消元 AcWing 884. 高斯消元解异或線性方程組

原題鏈接

AcWing 884. 高斯消元解异或線性方程組

算法標簽

線性空間 高斯消元 异或

思路

代碼

#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;
}

原創不易
轉載請標明出處
如果對你有所幫助 別忘啦點贊支持哈