AcWing 884. 高斯消元解异或线性方程组

题目传送门

#include <bits/stdc++.h>

using namespace std;

//异或：不进位的加法
const int N = 110;
int n;
int a[N][N];
int c, r;

void gauss() {
    for (c = 0, r = 0; c < n; c++) {
        int t = r;
        //找到第一个是1的行
        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; i++) swap(a[r][i], a[t][i]);

        for (int i = r + 1; i < n; i++)
            //是1的才需要消元
            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]) {
                //无解
                puts("No solution");
                exit(0);
            }
        //无穷多组解
        puts("Multiple sets of solutions");
        exit(0);
    }
    //唯一解，还原成各个方程的解
    for (int i = n - 1; i >= 0; i--)
        for (int j = i + 1; j < n; j++)
            a[i][n] ^= a[i][j] * a[j][n];
}

int main() {
    //优化输入
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n + 1; j++)
            cin >> a[i][j];
    //高斯消元
    gauss();
    //唯一解
    for (int i = 0; i < n; i++) cout << a[i][n] << endl;
    return 0;
}