题目描述

利用高斯消元法求解线异或线性方程组
异或线性方程组与一般的线性方程组不同之处在于
一般的线性方程组各个未知量之间是加法运算符，如
$a_1x + a_2x + … + a_nx = b$
而异或线性方程组各个未知量之间是异或运算符，如

$a_1x$ xor $a_2x$ xor … xor $a_nx = b$

算法步骤

一、高斯消元得到上三角矩阵
    1、枚举列
    2、找到当前列的非零行
    3、非零行换到剩余行的最上面
    4、剩余行中除去最上面一行，下面所有行的当前列都消零 
二、判断解的种类
    1、无解
    2、无穷多解
    3、唯一解

具体的实现可以参考下面的代码（抄袭y总）
本题解主要证明 执行高斯消元的第4步：
剩余行中除去最上面一行，下面所有行的当前列都消零
的过程中使用异或的正确性

一般线性方程组消元的正确性

总的来说，就是乘法对加法有分配律
系数消成0主要依靠的是某一行乘以若干倍，加到另一行所得方程组与原方程组同解

命题：x是原方程组的解 当且仅当 x是变换后方程组的解

用trivial的方程组（更多未知数同理）
$a_1x = b1$
$a_2x = b2$
把第一行的k倍加到第二行,方程组变为
$a_1x = b1$
$(ka_1 + a_2)x = kb_1 + b2$

充分性：
显然的，如果x是原方程组的解，
那么x也变换后方程组的解

必要性：
乘法对加法有分配律，如果
$a_1x = b1$
$(ka_1 + a_2)x = kb_1 + b2$成立
那么
$ka_1x = kb1$
$ka_1 x + a_2x = kb_1 + b2$成立
第二个方程减去第一个得到
$a_2x = b2$成立
得到，x是原方程组的解

异或线性方程组消元的正确性

类似的，乘法对异或有分配律

由上图，的确是可以分配的
所以证明类似

x是方程组
$a_1x = b1$
$a_2x = b2$
的解

等价于

x是方程组
$a_1x = b1$
$a_1x$ xor a_2x = b1 xor b2
的解
(因为x xor x = 0, 所以变换后的第二个方程左右两边分别异或第一个方程的左右两边，
即得到原方程组的第二个方程)
等价于

x是方程组
$a_1x = b1$
$(a_1$ xor a_2)x = b1 xor b2
的解

(高斯消元)

C++ 代码

#include <iostream>
using namespace std;

const int N = 110;
int a[N][N];
int n;
int gauss()
{
    //第一：消成同解的上三角矩阵
    int r, c;
    //1.枚举列,可以跳过行，但是不能跳过列
    for (r = 0, c = 0; c < n; c++) {
        //2.找到剩余行中的非零行
        int t = r;
        for (int i = r; i < n; i++)
            if (a[i][c]) {
                t = i;
                break;
            }
        if (a[t][c] == 0) continue;
        //3.非零行换到剩余行中的最上面
        for (int i = c; i <= n; i++) swap(a[r][i], a[t][i]);
        //4.剩余行中的第c列下面消成0
        for (int i = r + 1; i < n; i++) {
            if (a[i][c]) {
                for (int j = c; j <= n; 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;
    } else {
        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()
{
    //int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= n; j++)
            cin >> a[i][j];
    int res = gauss();
    if (res == 0) {
        for (int i = 0; i < n; i++)
            cout << a[i][n] << endl;
    } else if (res == 1) 
        cout << "Multiple sets of solutions"<< endl;
    else 
        cout <<   "No solution" << endl;
}