Gauss Cancellation acwing 884. Solution d'un système d'équations Xor linéaires par élimination gaussienne

Gauss cancel AcWing 884. Solution d'élimination gaussienne pour un système d'équations Xor linéaires

Lien vers la question originale

AcWing 884. Solution d'élimination gaussienne pour un système d'équations Xor linéaires

Étiquette de l'algorithme

Espace linéaire Gauss cancel XOR

Idées

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 cancel, Réponse stockée dans a[i][n]Moyenne,0 <= i < n
    // cColonne représentative rLigne représentative
    int c, r;
    //  Liste par colonne 
    for(c=0, r=0; c<n; ++c){
        int t=r;
        rep(i, r, n){
            if(a[i][c]){// Trouver une ligne non nulle
                t=i;
                break;
            }
        }
        if(!a[t][c]){
            continue;
        }
        rep(i, c, n+1){//  Changez la ligne non nulle en haut 
            swap(a[r][i], a[t][i]);
        }
        rep(i, r+1, n){//  Utilisez une ligne non nulle avec la colonne suivante pour éliminer à 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;// Pas de solution
            }
        }
        return 1;// Il y a un nombre infini de solutions de groupe
    }
    Rep(i, n-1, 0){
        rep(j, i+1, n){
            a[i][n]^=a[i][j]*a[j][n];
        }
    }
    return 0;// Il y a une solution unique
}
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;
}

L'originalité n'est pas facile
Réimpression Veuillez indiquer la source
Si ça t'aide N'oublie pas de me soutenir.