mxqz,关于高斯消元解异或方程组
查看原帖
mxqz,关于高斯消元解异或方程组
469312
int_R楼主2023/7/23 14:57

已经通过但是有几点疑问,是照着这篇博客写的。

这是我自己的代码。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<bitset>
using namespace std;
const int MAXN=50;
int m,n,tot=1,ans[MAXN*MAXN];
bitset <MAXN*MAXN> a[MAXN*MAXN];
int main()
{
	cin.tie(0),cout.tie(0);
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(register int i=1;i<=n;++i)
	{
		for(register int j=1;j<=m;++j)
		{
			a[(i-1)*m+j][(i-1)*m+j]=1;
			if(i>1) a[(i-1)*m+j][(i-1)*m+j-m]=1;
			if(i<n) a[(i-1)*m+j][(i-1)*m+j+m]=1;
			if(j>1) a[(i-1)*m+j][(i-1)*m+j-1]=1;
			if(j<m) a[(i-1)*m+j][(i-1)*m+j+1]=1;
		}
	}
	for(int i=1;i<=n*m;++i)
	{
		int max=i;
		for(int j=i+1;j<=n*m;++j)
			if(a[j][i]>a[max][i]) max=j;
		if(!a[max][i]){ans[i]=1;continue;}
		swap(a[i],a[max]);
		for(int j=1;j<=n*m;++j)
		{
			if(j==i) continue;
			if(a[j][i]) a[j]^=a[i];
		}
	}
	for(int i=n*m;i>=1;--i)
		for(int j=i+1;j<=n*m;++j)
			ans[i]^=(ans[j]&a[i][j]); 
	for(int i=1;i<=n*m;++i)
	{
		cout<<ans[i]<<' ';
		if(!(i%m)) cout<<'\n';
	}
}

1.这段代码所实现的是什么?

for(int i=n*m;i>=1;--i)
	for(int j=i+1;j<=n*m;++j)
		ans[i]^=(ans[j]&a[i][j]); 

2.在题解中说 if(!a[max][i]){ans[i]=1;continue;} 这一行是将自由元赋值为 11 ,那如果没有自由元最后输出的会不会全是 00 ,还是说在这道题中没有自由元等价与没有解?

2023/7/23 14:57
加载中...