16.高斯消元解异或线性方程组

样例解释：

异或又叫不进位加法

思路：

原题样例转换为上三角矩阵后是这样

有唯一解

求出唯一解后，反推一遍，就可以求出所有解

异或版的高斯消元，比普通版的高斯消元更容易。为数不多的衍生题比母题简单系列

1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 110;
 4 int n;
 5 int a[N][N];
 6 int gauss() {
 7     int c, r;
 8     //c表示枚举的每一列
 9     //r表示行
10     for (c = 0, r = 0; c < n; c++) {
11         int t = r;
12         for (int i = r; i < n; i++) { 
13             if (a[i][c]) {
14                 t = i;
15                 break;
16             }
17         }
18         if (!a[t][c]) { 
19             continue;
20         }
21         for (int i = c; i <= n; i++) { //换到最上面
22             swap(a[t][i], a[r][i]);
23         }
24         for (int i = r + 1; i < n; i++) { //把下面的都变为0
25             if (a[i][c]) { 
26                 for (int j = n; j >= c; j--) {
27                     a[i][j] ^= a[r][j];
28                 }
29             }
30         }
31         r++;
32     }
33     //已经变好了
34     if (r < n) { //如果不到n个方程，不是唯一解
35         for (int i = r; i < n; i++) {
36             if (a[i][n]) { //如果出现了0 = ?的情况
37                 return 2; //无解
38             }
39         }
40         return 1; //无穷多解
41     }
42     for (int i = n - 1; i >= 0; i--) { //最后一步，倒着把答案推出来
43         for (int j = i + 1; j < n; j++) {
44             a[i][n] ^= a[i][j] * a[j][n]; //*可以写成&
45         }
46     }
47     return 0; //唯一解
48 }
49 int main() {
50     cin >> n;
51     for (int i = 0; i < n; i++) {
52         for (int j = 0; j < n + 1; j++) {
53             cin >> a[i][j];
54         }
55     }
56     int t = gauss();
57     if (t == 0) { //唯一解
58         for (int i = 0; i < n; i++) {
59             cout << a[i][n] << endl;
60         }
61     } else if (t == 1) { //无穷多解
62         cout << "Multiple sets of solutions" << endl;
63     } else { //无解
64         cout << "No solution" << endl;
65     }
66     return 0;
67 }

原文链接: https://www.cnblogs.com/fx1998/p/13454027.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍