洛谷传送门

yyy，题解没看懂，还是自己说一个吧

Solution

如果只要 $20\%$ 的分，状压是你最好的选择

（此题正解和状压没关系）

---

还是想想正解吧(*^_^*)

既然输入就是这么输的，就直接将蓝色看作 $0$ ，红色看作 $1$ ，那么满足条件的 $2\times 2$ 的区域就是 $a_{i,j}\oplus a_{i,j+1}\oplus a_{i+1,j}\oplus a_{i+1,j+1}=1$ 。

注意到，当第一列和第一行确定了如何染色时，整个表格就确定了。因为当一个 $2\times 2$ 的区域有三个确定时，最后一个也就确定了。

如果没有 $k$ 个已填格子的限制，方案数就是 $2^{n+m-1}$ 。

那么只要能把限制转化成和第一行第一列有关系，就可以求出真的方案数了。

对于一个点 $(x,y)$ ，经过一系列推导（推导别的题解写的很清楚）得：

$$a_{1,1}\oplus a_{x,1}\oplus a_{1,y}\oplus a_{x,y}=((x-1)*(y-1))\&1$$

人话就是：当 $x,y$ 均为偶数时，这四个东西异或为 $1$ ，不然为 $0$ 。

进一步意思是，我们知道了 $a_{x,y},a_{1,1}$ ，就可以知道 $a_{x,1}$ 和 $a_{1,y}$ 是颜色相同 $(0)$ 还是不同 $(1)$ 。

这个性质具有传递性——我们知道 $i,j$ 和 $j,k$ 的关系， $i,k$ 的关系也确定了。

那么考虑枚举 $a_{1,1}$ 的染色情况，用带权并查集来维护不同的关系。当块里某一个值确定了，那整个块就确定了。因为值有 $0,1$ 两种，所以每个块的贡献为 $2$ 。

设块数为 $cnt$ ，则答案为 $2^{cnt-1}$ 。（因为 $a_{1,1}$ 是确定的，则所在的连通块是确定的）

完结撒花

小细节：1.如果题目给了 $a_{1,1}$ 是什么色，那就不用枚举了。2. $a_{1,1}=0$ 直接枚举，当 $a_{1,1}=1$ 时，把除了第一行第一列的全部取反。因为之前是 $a_{x,y}\oplus0=a_{x,y}$ ，现在是 $a_{x,y}\oplus 1=(a_{x,y}\oplus1)\oplus 0$ 。3.在确定 $a_{x,1},a_{{1,y}}$ 关系时，为了方便，使得四个东西什么情况异或都为 $0$ ，具体操作为使得 $a_{x,y}\oplus 1$

其他细节可以看代码

Code

#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
const int N=200010,mod=1e9;
int fa[N],g[N],n,m,k,ans,flag[2]={1,1};
int x[N],y[N],c[N];

int find(int x){
    if(x==fa[x]) return x;
    int tmp=find(fa[x]);
    g[x]^=g[fa[x]];	//带权并查集特殊之处
    return fa[x]=tmp;
}


int solve(){
    for(int i=1;i<=n+m;i++) fa[i]=i,g[i]=0;
    fa[n+1]=1;
    for(int i=1;i<=k;i++){
        int fx=find(x[i]),fy=find(y[i]+n);
        int tmp=g[x[i]]^g[y[i]+n]^c[i];
        if(fx!=fy) fa[fx]=fy,g[fx]=tmp;
        else if(tmp) return 0;
    }
    int res=-1;
    for(int i=1;i<=n+m;i++)
        if(fa[i]==i){
            if(res==-1) res=1;
            else res<<=1;
            if(res>=mod) res-=mod;
        }
    return res;
}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;i++){
        scanf("%d%d%d",&x[i],&y[i],&c[i]);
        if(x[i]==1&&y[i]==1) flag[c[i]^1]=0,--k,--i;
        else if(x[i]%2==0&&y[i]%2==0) c[i]^=1;	//x,y都为偶数时
    }
    if(flag[0]) ans+=solve();
    if(flag[1]){
        for(int i=1;i<=k;i++)
            if(x[i]>1&&y[i]>1) c[i]^=1;	//除了第一行第一列，都取反
        ans+=solve();
    }
    if(ans>=mod) ans-=mod;
    printf("%d\n",ans);
}