AcWing 884. 高斯消元解异或线性方程组
原题链接
简单
作者:
术
,
2021-03-14 20:57:18
,
所有人可见
,
阅读 238
#include <iostream>
using namespace std;
int n;
const int N=110;
int a[N][N];
int ans[N];
void print(){
for(int i=0;i<n;i++)
{
for(int j=0;j<=n;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
}
int gauss()
{
int r,c;
for(r=c=0; c<n; c++)
{
int t=r;
for(int i=r; i<n; i++)
if(a[i][c])
{
t=i;
break;
}
if(!a[t][c])
continue;
for(int i=c; i<=n; i++)
swap(a[t][i],a[r][i]);
//将未确定行的第c列变为0
for(int i=r+1; i<n; i++)
{
if(a[i][c])//注意加上
for(int j=n; j>=c; j--)
{
a[i][j]=a[i][j]^a[r][j];
}
}
//print();
r++;
}
if(r<n)
{
for(int i=r; i<n; i++)
if(a[i][n])
return 3;
return 2;
}
for(int i=n-1; i>=0; i--)
{
ans[i]=a[i][n];
for(int j=i+1; j<n; j++)
{
ans[i]=ans[i]^(ans[j]*a[i][j]);
}
}
return 1;
}
int main()
{
cin>>n;
for(int i=0; i<n; i++)
for(int j=0; j<=n; j++)
cin>>a[i][j];
int flag=gauss();
if(flag==1)
{
for(int i=0; i<n; i++)
cout<<ans[i]<<endl;
}
else if(flag==2)
cout<<"Multiple sets of solutions"<<endl;
else
cout<<"No solution"<<endl;
//cout << "Hello world!" << endl;
return 0;
}