【题目来源】
AcWing：884. 高斯消元解异或线性方程组 - AcWing题库
【题目描述】
输入一个包含 \(n\) 个方程 \(n\) 个未知数的异或线性方程组。
方程组中的系数和常数为 \(0\) 或 \(1\)，每个未知数的取值也为 \(0\) 或 \(1\)。
求解这个方程组。
异或线性方程组示例如下：
M[1][1]x[1] ^ M[1][2]x[2] ^ … ^ M[1][n]x[n] = B[1]
M[2][1]x[1] ^ M[2][2]x[2] ^ … ^ M[2][n]x[n] = B[2]
…
M[n][1]x[1] ^ M[n][2]x[2] ^ … ^ M[n][n]x[n] = B[n]
其中 ^ 表示异或(\(XOR\))，\(M[i][j]\) 表示第 \(i\) 个式子中 \(x[j]\) 的系数，\(B[i]\) 是第 \(i\) 个方程右端的常数，取值均为 \(0\) 或 \(1\)。
【输入】
第一行包含整数 \(n\)。
接下来 \(n\) 行，每行包含 \(n+1\) 个整数 \(0\) 或 \(1\)，表示一个方程的 \(n\) 个系数以及等号右侧的常数。
【输出】
如果给定线性方程组存在唯一解，则输出共 \(n\) 行，其中第 \(i\) 行输出第 \(i\) 个未知数的解。
如果给定线性方程组存在多组解，则输出 Multiple sets of solutions。
如果给定线性方程组无解，则输出 No solution。
【输入样例】
3
1 1 0 1
0 1 1 0
1 0 0 1
【输出样例】
1
0
0
【解题思路】
【算法标签】
《AcWing 884 高斯消元解异或线形方程组》 #线性空间# #高斯消元# #异或#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 105; // 定义常量 N，表示矩阵的最大大小
int a[N][N]; // a 数组存储增广矩阵
int n; // 定义整数 n，表示矩阵的大小// 高斯消元法求解异或方程组
int gauss()
{int r = 0; // r 表示当前处理的行for (int c = 0; c < n; c++) { // 遍历每一列int t = r; // t 表示当前列中第一个非零元素所在的行for (int i = r; i < n; i++) { // 遍历当前列的所有行if (a[i][c] == 1) { // 如果当前元素为 1t = i; // 更新 tbreak; // 跳出循环}}if (a[t][c] == 0) continue; // 如果当前列全为 0，跳过// 交换第 r 行和第 t 行for (int i = 0; i <= n; i++) swap(a[r][i], a[t][i]);// 用第 r 行消去下面所有行的第 c 列for (int i = r + 1; i < n; i++) {if (a[i][c] == 1) { // 如果当前行的第 c 列为 1for (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] == 1) return 2; // 如果有矛盾，返回 2（无解）}return 1; // 否则返回 1（多组解）}// 回代求解for (int i = n - 2; i >= 0; i--) { // 从倒数第二行开始回代for (int j = i + 1; j < n; j++) { // 遍历当前行后面的所有列a[i][n] = a[i][n] ^ (a[i][j] * a[j][n]); // 异或消元}}return 0; // 返回 0（唯一解）
}int main()
{cin >> n; // 输入矩阵的大小 nfor (int i = 0; i < n; i++) { // 输入增广矩阵for (int j = 0; j <= n; j++) {cin >> a[i][j];}}int t = gauss(); // 调用高斯消元法求解if (t == 0) { // 如果唯一解for (int i = 0; i < n; i++) cout << a[i][n] << endl; // 输出解} else if (t == 1) { // 如果多组解cout << "Multiple sets of solutions" << endl;} else { // 如果无解cout << "No solution" << endl;}return 0; // 程序结束
}
【运行结果】
3
1 1 0 1
0 1 1 0
1 0 0 1
1
0
0