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$ 算了都没人看，哪来的侵权。考虑给个赞和关注吗？