AcWing 884. 高斯消元解异或线性方程组
原题链接
简单
作者:
我要出去乱说
,
2021-01-24 15:14:04
,
所有人可见
,
阅读 230
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int a[N][N];
int gauss()
{
int r, c;
for (r = 0, c = 0; c < n; c ++ )
{
int t = r;
for (int i = r; i < n; i ++ )
if (a[i][c])
{
t = i;
break; //只需要找非零行,找到直接break
}
if (!a[t][c]) continue; //若当前列全为零,进入下一个列循环
for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]);
for (int i = r + 1; i < n; i ++ )
if (a[i][c])
{
for (int j = n; j >= c; j -- ) //正着来反着来都行,因为i行第一个系数是肯定是1
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 ++ )
a[i][n] ^= a[i][j] * 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 res = gauss();
if (res == 0)
{
for (int i = 0; i < n; i ++ )
cout << a[i][n] << endl;
}
else if (res == 1) puts("Multiple sets of solutions");
else puts("No solution");
return 0;
}