Luogu P3631 【[APIO2011]方格染色】

T15 Apio2011 方格染色

20分算法：暴力枚举每个点

抄题解做的还是好好写总结吧

把红色视为0，蓝色视为1

假设有一个表格如下：

根据题设有\(A\bigoplus B\bigoplus C\bigoplus D=C\bigoplus D\bigoplus E\bigoplus F=1\)

然后有\(A\bigoplus B\bigoplus E\bigoplus F=0\)

而\(E\bigoplus F\bigoplus G\bigoplus H=1\)

所以\(A\bigoplus B\bigoplus G\bigoplus H=1\)

再放到一般性的表格中

当C，D处于奇数列的时候，有:

\(A\bigoplus B\bigoplus C\bigoplus D=0,E\bigoplus F\bigoplus G\bigoplus H=0,B\bigoplus I\bigoplus D\bigoplus J=0\)

所以有:

\(A\bigoplus C\bigoplus I\bigoplus J=0\)

推出

\(A\bigoplus C\bigoplus F\bigoplus H=0\)

即：

\(A\bigoplus H=C\bigoplus F\)

当C，D在偶数列上，有：

\(A\bigoplus B\bigoplus C\bigoplus D=1,E\bigoplus F\bigoplus G\bigoplus H=1,B\bigoplus I\bigoplus D\bigoplus J=1\)

当H在奇数行：

\(1\bigoplus A\bigoplus H=C\bigoplus F\)

当H在偶数行：

\(A\bigoplus H=C\bigoplus F\)

设H坐标为\((i,j)\),A坐标为\((1,1)\)

则有：
\(if(i\ mod\ 2==0\ and\ j\ mod \ 2==0) \ 1\bigoplus(1,1)\bigoplus(i,j) ==(1,j)\bigoplus(i,1)\)
\(else\ (1,1)\bigoplus(i,j) ==(1,j)\bigoplus(i,1)\)

而显然如果确定了第一排，第一列，那么可以确定整张图。

所以可以枚举\((1,1)\)的值，然后合并所有相关的集合，去掉已知点的集合，剩下的集合个数为\(cnt\)，则答案为\(2^{cnt}\)。
把(1,1)为0,1的答案加起来即可

合并集合的时候使用扩展域并查集维护到根节点的异或值。

#include <cstdio>
#include <cstring>
#include <cstdlib>

#define R register
#define ll long long

const int MAXN=1e6+10;
const int Mod=1e9;

inline int read()
{
	int x=0,f=1;
	char a=getchar();
	for(;a>'9'||a<'0';a=getchar()) if(a=='-') f=-1;
	for(;a>='0'&&a<='9';a=getchar()) x=x*10+a-'0';
	return x*f;
}

int n,m,k,flg=-1,cnt,Size;
int fa[MAXN];
int X[MAXN],Y[MAXN],Z[MAXN];

inline int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); }
inline void merge(int x,int y)
{	
	int fx=find(x),fy=find(y); 
	fa[fx]=fy;cnt-=fx!=fy;
}

inline void Init()
{
	n=read();m=read();k=read();
	Size=n+m-1;
	for(R int i=1;i<=k;i++)
	{
		X[i]=read();Y[i]=read();Z[i]=read();
		if(X[i]==1&&Y[i]==1) flg=Z[i];
	}
}

inline int id(int x) { return x==1?1:m+x-1; }

int vis[MAXN];
int ans=0;

inline void Solve(bool delta)
{
	for(R int i=1;i<=Size*2;i++) fa[i]=i;
	cnt=Size*2;
	for(R int i=1;i<=k;i++)
	{
		int a=X[i],b=Y[i];
		if(a==1&&b==1) continue;
		if(a%2==0&&b%2==0)
		{
			if(1^delta^Z[i]) 
			{
				merge(id(a),b+Size);merge(id(a)+Size,b);
			}
			else
			{
				merge(id(a),b);merge(id(a)+Size,b+Size);
			}
		}
		else
		{
			if(delta^Z[i]) 
			{
				merge(id(a),b+Size);
				merge(id(a)+Size,b);
			}
			else
			{
				merge(id(a),b);
				merge(id(a)+Size,b+Size);
			}
		}
		if(find(b)==find(b+Size)||find(id(a))==find(id(a)+Size))
		{
			printf("0\n");
			exit(0);
		}
	}
	memset(vis,0,sizeof(vis));
	cnt--;
	vis[find(1)]=1;
	for(R int i=1;i<=k;i++)
	{
		if(X[i]==1&&vis[find(Y[i])]==0) 
		{
			vis[find(Y[i])]=1;
			cnt--;
		}
		else 
			if(Y[i]==1&&vis[find(id(X[i]))]==0)
			{
				vis[find(id(X[i]))]=1;
				cnt--;
			}
	}
	cnt>>=1;
	int tmp=1;
	for(R int i=1;i<=cnt;i++) tmp=(tmp<<1)>=Mod?(tmp<<1)-Mod:(tmp<<1);
	ans=ans+tmp>=Mod?ans+tmp-Mod:ans+tmp;
}

int main()
{
	Init();
	if(flg==-1) Solve(0),Solve(1);
	if(flg==0) Solve(0);
	if(flg==1) Solve(1);
	printf("%d\n",ans);
	return 0;
}