高斯消元解异或线性方程组（高斯消元，模板）

题意

(a_{ij})以及(b_i)都是(0/1)

方法

异或运算可以看成是不进位的加法，因此直接高斯消元即可

代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 110;

int n;
int a[N][N];

int gauss()
{
    int r, c;
    for(r = 0, c = 0; c < n; c ++) {
        int t = r;
        for(int i = r; i < n; i ++) {
            if(a[i][c]) {
                t = i;
                break;
            }
        }
        if(!a[t][c]) continue;
        for(int i = c; i < n + 1; i ++) swap(a[r][i], a[t][i]);
        for(int i = r + 1; i < n; i ++) {
            if(a[i][c]) {
                for(int j = n; j >= c; j --) {
                    a[i][j] ^= a[r][j];
                }
            }
        }
        r ++;
    }
    if(r < n) {
        for(int i = r; i < n; i ++) {
            if(a[i][n]) {
                return 2;
            }
        }
        return 1;
    }
    for(int i = n - 1; i >= 0; i --) {
        for(int j = i + 1; j < n; j ++) {
            a[i][n] ^= a[j][n] & a[i][j];
        }
    }
    return 0;
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i ++) {
        for(int j = 0; j < n + 1; j ++) {
            scanf("%d", &a[i][j]);
        }
    }
    int t = gauss();
    if(!t) for(int i = 0; i < n; i ++) printf("%d
", a[i][n]);
    else if(t == 1) puts("Multiple sets of solutions");
    else puts("No solution");
    return 0;
}