模板 高斯消元异或版

const int maxn=110;

int equ, var;//equ个方程 var个变量
int a[maxn][maxn];//增广矩阵
int x[maxn];//解集
int x_i[maxn];
bool free_x[maxn];//判断是不是自由变元
int free_num;//自由变元的个数

int Gauss(){
    int Max_r;//当前列绝对值最大的存在的行
    //col：处理当前的列
    int row,col=0;
    int free_x_num;
    int free_index;
    free_num=0;
    for(int i=0;i<=var;i++){
        x[i]=0;
        free_x[i]=1;
    }
    for(row=0;row<equ && col<var;row++,col++){
        Max_r=row;
        for(int i=row+1;i<equ;i++){
            if(abs(a[i][col])>abs(a[Max_r][col])){
                Max_r=i;
            }
        }
        if(a[Max_r][col]==0){
            free_x[col]=1;
            x_i[free_num++]=col;
            row--;
            continue;
        }
        if(Max_r!=row){
            for(int i=col;i<var+1;i++){
                swap(a[row][i],a[Max_r][i]);
            }
        }
        //消元
        for(int i=row+1;i<equ;i++){
            if(a[i][col]){
                for(int j=col;j<var+1;j++){
                    a[i][j]^=a[row][j];
                }
            }
        }
    }
    for(int i=row;i<equ;i++){
        if(a[i][col]) return -1;//无解
    }
    //保证对角线主元非0
    for(int i=0;i<equ;i++){
        if(!a[i][i]){
            int j;
            for(j=i+1;j<var;j++){
                if(a[i][j]) break;
            }
            if(j==var) break;
            for(int k=0;k<equ;k++){
                swap(a[k][i],a[k][j]);
            }
        }
    }
    if(row<var){
        return var-row;//自由变元的个数
    }
    //回代，得到解集
    for(int i=var-1;i>=0;i--){
        x[i]=a[i][var];
        for(int j=i+1;j<var;j++){
            x[i]^=(a[i][j] && x[j]);
        }
    }
    return 0;//唯一解
}

模板 高斯消元异或版

原文：https://www.cnblogs.com/fxq1304/p/14606596.html