python/TangDou/AcWing/Gauss/884.cpp

#include <bits/stdc++.h>

using namespace std;

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

void gauss() {
    int r = 1;
    for (int c = 1; c <= n; c++) {
        int t = r;
        // 找到第一个是1的行，不用找最大值,因为只有0、1，1就是最大值
        for (int i = r + 1; i <= n; i++)
            if (a[i][c]) t = i;
        // 没有找到的话，下一列
        if (!a[t][c]) continue;
        // 交换
        swap(a[r], a[t]);

        for (int i = r + 1; i <= n; i++)         // 后面的行
            if (a[i][c])                         // 如果与c同一列有数字1
                for (int j = n + 1; j >= c; j--) // 从右侧结果开始，到c列为止,利用当前的r行c列值1，通过异或运算，将后续行此列消为0
                    a[i][j] ^= a[r][j];
        // 下一行
        r++;
    }
    // 判断无解和无穷多解
    if (r <= n) {
        for (int i = r; i <= n; i++)
            if (a[i][n + 1]) {
                // 无解
                puts("No solution");
                exit(0);
            }
        // 无穷多组解
        puts("Multiple sets of solutions");
        exit(0);
    }
    // 唯一解，还原成各个方程的解
    for (int i = n; i >= 1; i--)
        for (int j = i + 1; j <= n; j++)
            a[i][n + 1] ^= a[i][j] * a[j][n + 1];
    // 这个乘法用的好！因为a[i][j]只有01两种形式，0乘以什么都是0，异或后还是本身。1的话就相当于异或一下等式左右两端
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n + 1; j++)
            cin >> a[i][j];
    gauss();
    // 唯一解
    for (int i = 1; i <= n; i++) cout << a[i][n + 1] << endl;
    return 0;
}