AcWing 884. 高斯消元解异或线性方程组
本博客提供本题截图：
本题解析
本题思路和上题思路基本一致，注意4.将下面所有行的第c列消成0 这一步，其实就和和第r行的每一列的对应元素进行异或运算
异或运算中满足a ^ b = c, c ^ b = a，故我们在求解每个元素的值得时候可以利用异或去运算求解.
AC代码
#include <iostream> #include <algorithm> using namespace std; const int N = 110; int n; int a[N][N]; int gauss() { int c, r; for (c = 0, r = 0; c < n; c ++ ) { int t = r; for (int i = r; i < n; i ++ ) if (a[i][c]) t = i; if (!a[t][c]) continue; for (int i = c; i <= n; i ++ ) swap(a[r][i], a[t][i]); for (int i = r + 1; i < n; i ++ ) if (a[i][c]) for (int j = n; j >= c; 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 ++ ) if (a[i][j]) a[i][n] ^= 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 ++ ) cout << a[i][n] << endl; } else if (t == 1) puts("Multiple sets of solutions"); else puts("No solution"); return 0; }
三、时间复杂度
关于高斯消元各步操作的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
