P3164 [CQOI2014]和谐矩阵

乱写能AC，暴力踩标程（雾

第一眼

诶这题能暴力枚举2333！！！

第二眼

诶这题能高斯消元！那只需要把每个位置的数给设出来就能够列方程了！然后就可以\(O(1600^3)\)跑了！

第三眼

只需要对每一行每一列有奇数还是偶数个1列方程就行了！

然而我太菜了想不到这种方法

第三眼

这个方程好像系数都是0而且结果都是1！那么消的时候只需要下面方程减上面方程就行了！而且这是个模2意义下的方程！

emmm所以不需要减只需要异或？

所以可以用bitset存系数？？？

然后异或一下？？？

就可以\(O(1600^3/32)\)辗标算？

第四眼

诶好像可以卡常！显然1的数量很小，所以可以用bitset自带的findfirst和findnext可以寻找1的位置再减。。。

然后code出来就不开O2 8ms，开O2 0ms了

// It is made by XZZ

#include<cstdio>

#include<algorithm>

#include<bitset>

#define il inline

#define rg register

#define vd void

#define sta static

typedef long long ll;

il int gi(){

	rg int x=0,f=1;rg char ch=getchar();

	while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();

	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

	return x*f;

}

using namespace std;

bitset<1601>S[1601];

int p[1601];

int id[41][41];

int ans[1601];

int main(){

#ifdef xzz

	freopen("3164.in","r",stdin);

	freopen("3163.out","w",stdout);

#endif

	int n=gi(),m=gi(),N=n*m;

	for(rg int i=1;i<=n;++i)

		for(rg int j=1;j<=m;++j)

			id[i][j]=++id[0][0];

	for(rg int i=1;i<=n;++i)

		for(rg int j=1;j<=m;++j)

			S[id[i][j]][id[i][j]]=1;

	for(rg int i=1;i<=n;++i)

		for(rg int j=1;j<m;++j)

			S[id[i][j]][id[i][j+1]]=1;

	for(rg int i=1;i<=n;++i)

		for(rg int j=2;j<=m;++j)

			S[id[i][j]][id[i][j-1]]=1;

	for(rg int i=1;i<n;++i)

		for(rg int j=1;j<=m;++j)

			S[id[i][j]][id[i+1][j]]=1;

	for(rg int i=2;i<=n;++i)

		for(rg int j=1;j<=m;++j)

			S[id[i][j]][id[i-1][j]]=1;

	for(rg int i=1;i<=N;++i)p[i]=i;

	for(rg int i=1;i<=N;++i){

		for(rg int j=S[p[i]]._Find_first();j<i;j=S[p[i]]._Find_next(j))

			if(S[p[j]][j])S[p[i]]^=S[p[j]];

			else swap(p[i],p[j]);

	}

	for(rg int i=N;i;--i){

		if(S[p[i]][i]==0){ans[i]=1;continue;}

		for(rg int j=S[p[i]]._Find_next(i);j<=N;j=S[p[i]]._Find_next(j))

			ans[i]^=ans[j];

	}

	for(rg int i=1;i<=n;++i){

		for(rg int j=1;j<=m;++j)

			printf("%d ",ans[id[i][j]]);

		puts("");

	}

	return 0;

}

巴特西

P3164 [CQOI2014]和谐矩阵

P3164 [CQOI2014]和谐矩阵

第一眼

第二眼

第三眼

第三眼

第四眼

最新文章

热门文章