自动搬运

查看原文

来自洛谷，原作者为

	xiaolilsq 灰名不比红名好看（

搬运于2025-08-24 21:50:59，当前版本为作者最后更新于2020-02-01 21:04:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目链接

刚刚做了这道题，感觉这题有诸多细节（调了我几个小时），后来发现大家的代码太麻烦了，于是过来写（shui）篇题解。

这道题思路大致是这样的（记$(x,y)$表示格子$(x,y)$的颜色）：

$$(x,y)\oplus(x-1,y)\oplus(x,y-1)\oplus(x-1,y-1)=1$$

令$x=x-1$，有：

$$(x-1,y)\oplus(x-2,y)\oplus(x-1,y-1)\oplus(x-2,y-1)=1 $$

两式异或起来得到：

$$(x,y)\oplus(x,y-1)\oplus(x-2,y)\oplus(x-2,y-1)=0$$

于是便有：

$$(x,y)\oplus(x,y-1)\oplus(x-2k,y)\oplus(x-2k,y-1)=0 $$

令$y=y-1$，得到：

$$(x,y-1)\oplus(x,y-2)\oplus(x-2k,y-1)\oplus(x-2k,y-2)=0 $$

两式异或起来得到：

$$(x,y)\oplus(x,y-2)\oplus(x-2k,y)\oplus(x-2k,y-2)=0 $$

同理：

$$(x,y)\oplus(x,y-t)\oplus(x-2k,y)\oplus(x-2k,y-t)=0 $$

同理亦有：

$$(x,y)\oplus(x,y-2k)\oplus(x-t,y)\oplus(x-t,y-2k)=0 $$

于是我们便得到若$x,y$中至少有一个是奇数时:

$$(x,y)\oplus(x,1)\oplus(1,y)\oplus(1,1)=0$$

当$x,y$都是偶数时，自己推一下不难得到:

$$(x,y)\oplus(x,1)\oplus(1,y)\oplus(1,1)=1$$

这时有些题解的做法是枚举$(1,1)$的所有可能（即$0$或$1$），其实这样做麻烦了，我们可以多开一行一列（即$(0,y)$和$(x,0)$），然后默认$(0,0)=0,(1,0)=0$，这样整个图就是新开的这一行这一列决定的了，然后就不必考虑那么多了

对于一个新添加的颜色$(x,y)=t$，若$x,y$中至少有一个是偶数时，令：

$$(x,0)\oplus(0,y)=(x,y)\oplus(0,0)\oplus1=t\oplus1$$

否则令：

$$(x,0)\oplus(0,y)=(x,y)\oplus(0,0)=t$$

用种类并查集维护一下$(x,0)$和$(0,y)$之间的关系，最后记得把$(1,0)$去掉，然后记录一下连通块的个数$cnt$，最后的答案便是$2^{cnt}$

放上巨丑无比的代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100005;
int fa[maxn<<2],opp[maxn<<2],del[maxn<<2];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
int push(int x,int y){
	fa[x]=y;
}
int push(int x,int y,int c){
	if(c){
		x=find(x);y=find(y);
		if(x==y)return false;
		if(x==opp[y])return true;
		push(x,opp[y]);push(opp[x],y);
	}
	else{
		x=find(x);y=find(y);
		if(x==opp[y])return false;
		if(x==y)return true;
		push(x,y);push(opp[x],opp[y]);
	}
	return true;
}
long long mod=1e9;
long long power(long long a,int n){
	long long ans=1;
	while(n){
		if(n&1)ans=ans*a%mod;
		n>>=1;a=a*a%mod;
	}
	return ans;
}
int main(){
	int n,m,k;
	scanf("%d %d %d",&n,&m,&k);int all=n+m;
	for(int i=1;i<=all;++i)opp[i+all]=fa[i]=i,opp[i]=fa[i+all]=i+all;//(x,0)->x (0,y)->y+n
	int Im=0;
	for(int i=0,x,y,c,t;i<k;++i){
		scanf("%d %d %d",&x,&y,&c);
		if((x+1&1)==0&&(y+1&1)==0)c^=1;
		y+=n;
		if(!push(x,y,c)){
			Im=1;break;
		}
	}
	if(Im){
		putchar(0);
	}
	else{
		int temp=find(1),ans=0;
		del[temp]=true;del[opp[temp]]=true;
		for(int i=2;i<=all;++i){
			int x=find(i);
			if(!del[x])++ans;
			del[x]=del[opp[x]]=true;
		}
		printf("%lld",power(2,ans));
	}
	return 0;
}

似乎比其他做法要简洁吧。。。

希望这篇题解对你有帮助

欢迎提供hack数据