|
|
|
|
|
##[$AcWing$ $884$. 高斯消元解异或线性方程组](https://www.acwing.com/problem/content/description/886/)
|
|
|
|
|
|
|
|
|
|
|
|
### 一、题目描述
|
|
|
|
|
|
输入一个包含 $n$ 个方程 $n$ 个未知数的异或线性方程组。
|
|
|
|
|
|
|
|
|
|
|
|
方程组中的系数和常数为 $0$ 或 $1$，每个未知数的取值也为 $0$ 或 $1$。
|
|
|
|
|
|
|
|
|
|
|
|
求解这个方程组。
|
|
|
|
|
|
|
|
|
|
|
|
异或线性方程组示例如下：
|
|
|
|
|
|
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
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`。
|
|
|
|
|
|
|
|
|
|
|
|
**数据范围**
|
|
|
|
|
|
$1≤n≤100$
|
|
|
|
|
|
|
|
|
|
|
|
**输入样例**：
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
3
|
|
|
|
|
|
1 1 0 1
|
|
|
|
|
|
0 1 1 0
|
|
|
|
|
|
1 0 0 1
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
**输出样例：**
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
1
|
|
|
|
|
|
0
|
|
|
|
|
|
0
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
### 二、解题思路
|
|
|
|
|
|
**核心思想**: 异或-不进位的加法
|
|
|
|
|
|
那么等式与等式间的异或要一起进行才能保证等式左右两边依然是相等关系!
|
|
|
|
|
|
`a^b^c = x`
|
|
|
|
|
|
`d^f = y`
|
|
|
|
|
|
则
|
|
|
|
|
|
`a^b^d^c^f = x^y`
|
|
|
|
|
|
|
|
|
|
|
|
#### 1 左下角消$0$
|
|
|
|
|
|
① 枚举列
|
|
|
|
|
|
② 找第一个非零行
|
|
|
|
|
|
③ 交换
|
|
|
|
|
|
④ 把同列下面行消零(异或)
|
|
|
|
|
|
|
|
|
|
|
|
#### 2 判断$3$种情况
|
|
|
|
|
|
① 唯一解
|
|
|
|
|
|
② 秩<$n$
|
|
|
|
|
|
- 有矛盾 无解
|
|
|
|
|
|
- 无矛盾 无穷多解
|
|
|
|
|
|
|
|
|
|
|
|
#### 3 手绘流程
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
#### $Code$
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
#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;
|
|
|
|
|
|
}
|
|
|
|
|
|
```
|
