分析

• 异或又可以被看成不进位的加法。

• 这里的步骤是和高斯消元法一样的，只不过需要将运算换成异或运算。

• 第一步：转为上三角矩阵：枚举每一列c

（1）找到非零行；

（2）将该行换到最上面；

（3）将下面所有行的第c列消成0；

• 第二步：回代求解。

从最后一个方程进行回代可以求出所有的答案。

• 结果存在三种情况：

（1）唯一解：做完第一步之后，满秩，即系数矩阵没有全0行；

（2）无解：系数矩阵存在全0行，且该行对应的b值不为0；

（3）无穷多组解：系数矩阵存在全0行，且0行对应的b值都为0；

代码

#include <iostream>

using namespace std;

const int N = 110;

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

// 返回0：存在唯一解; 返回1：存在无穷多组解; 返回2：无解
int gauss() {

    int r, c;
    for (r = 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[t][i], a[r][i]);

        for (int i = r + 1; i < n; i++)
            if (a[i][c]) 
                for (int j = c; j < n + 1; 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[i][j] & a[j][n];

    return 0;
}

int main() {

    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n + 1; j++)
            cin >> a[i][j];

    int t = gauss();

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

    return 0;
}