P3631 [APIO2011] 方格染色

      ~~~~~      P3631 [APIO2011] 方格染色       ~~~~~      总题单链接

思路

      ~~~~~      用 $1$表示红色，$0$ 表示蓝色，$col[i][j]$ 表示第 $i$ 行，第 $j$ 列的颜色。发现 $i\ge 2,j\ge 2$ 时，$col[i][j]=col[i-1][j-1]\oplus col[i-1][j]\oplus col[i][j-1]\oplus 1$，所以只要第一行和第一列的颜色确定了，整个矩阵就能确定。

      ~~~~~      但这还不够，先不管 $\oplus 1$ 画个图看一下：

      ~~~~~      发现 $a[i][j]=a[1][1]\oplus a[i][1]\oplus a[1][j]$，所以每次涂色等同于一个形如一个（若第 $i$行第一列的值是 $a$，则第 $j$ 列第一行的值是$b$）的限制，这里的 a , b ∈ { 0 , 1 } a,b \in{\{0,1\}} a,b∈{0,1}，欸，那么 $a[1][1]$ 去哪了，仔细想想，假如这条限制默认 $a[1][1]=0$，那 $a[1][1]=1$ 的情况不就是把 $a,b$ 换一下吗，所以 $a[1][1]$ 在这条限制中其实不重要。

      ~~~~~      那么大概就可以往连边和连通块的方向去想了。

      ~~~~~      将每行每列视为两个点 $u_0$ 和 $u_1$，表示这一行$/$列的第一个值选 $0/1$。

      ~~~~~      对于一次在第 $i$ 行，第 $j$ 列，颜色为 $c$ 的涂色，设 $u_0,u_1$ 表示第 $i$ 行表示的两个点，$v_0,v_1$ 表示第 $j$ 列表示的两个点，连两条边 $u_0——v_c,u_1——v_{c\oplus 1}$，连边后一个连通块就必须要一起选了，如果存在一个点使得 $u_0,u_1$ 在一个连通块中，那么答案就是 $0$。

      ~~~~~      我们还没有考虑 $\oplus 1$，再画一个只考虑 $\oplus 1$的图：

      ~~~~~      发现只有 $i,j$ 都为偶数的情况下才会 $\oplus 1$，直接将 $c\oplus 1$即可。

      ~~~~~      我个人认到这里还是比较难理解的，我也想了很久，所以如果你没有理解大可不必着急，慢慢来，再看一遍或者自己动手画图，模拟一下样例。

代码

#include<bits/stdc++.h>
#define ll long long
#define MOD 1000000000
using namespace std;

inline ll qmi(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1)(res*=a)%=MOD;
		(a*=a)%=MOD;b>>=1;
	}
	return res;
}

ll n,m,Q;

inline ll U(ll x,ll y){return(y==0?x:x+n);} 
inline ll V(ll x,ll y){return(y==0?x+n*2:x+n*2+m);}

struct BJ{
	ll fas[400005],cnt;
	void init(){for(ll i=1;i<=2*(n+m);i++)fas[i]=i;cnt=2*(n+m);}
	inline ll fid(ll p){
		if(fas[p]!=p)fas[p]=fid(fas[p]);
		return fas[p];
	}
	inline void uni(ll x,ll y){
		x=fid(x),y=fid(y);
		if(x!=y)fas[x]=y,cnt--;
	}
}bj;

signed main(){
	ios::sync_with_stdio(false);
	
	cin>>n>>m>>Q;
	if(n==1||m==1){
		cout<<qmi(2,n*m-Q);
		return 0;
	}
	
	bj.init();
	
	ll opt=1;
	while(Q--){
		ll x,y,c;
		cin>>x>>y>>c;
		if(x%2==0&&y%2==0)c^=1;
		bj.uni(U(x,0),V(y,c));
		bj.uni(U(x,1),V(y,c^1));
		if(bj.fid(U(x,0))==bj.fid(U(x,1))||bj.fid(V(y,0))==bj.fid(V(y,1)))opt=0;
	}
	cout<<(opt==1?qmi(2,bj.cnt/2-1):0)<<endl;
	
	return 0;
}

      ~~~~~      侵权必 $\dots$ 算了都没人看，哪来的侵权。考虑给个赞和关注吗？