Tag

并查集，异或方程

很有意思的一道题，所以单独拿出来了。

完整分享看 这里

题目链接
luogu

题意

有一个包含 $n \times m$ 个方格的表格。要将其中的每个方格都染成红色或蓝色。表格中每个 $2 \times 2$ 的方形区域都包含奇数个（ $1$ 个或 $3$ 个）红色方格。例如，下面是一个合法的表格染色方案（R 代表红色，B 代表蓝色）：

B B R B R
R B B B B
R R B R B

表格中的一些方格已经染上了颜色.求给剩下的表格染色，使得符合要求的方案数。

思路

每天一道压轴好题。 其实这题跟并查集没啥关系，只是用来维护而已

题意可以简化为：在 $n\times m$ 的矩阵中放 01，k 个格子已经放好了，要放满，且每个 $2\times 2$ 的格子中有奇数个1.

由题意可知，任意四个格子（二乘二）的异或值为 1，不断异或相邻的两个“矩形”的异或式子 （如：$A\oplus B\oplus C\oplus D=C\oplus D\oplus E\oplus F=E\oplus F\oplus G\oplus H=1$，选取相邻的式子得到 $A\oplus B\oplus E\oplus F=0,A\oplus B\oplus G\oplus H=0$ )

由这个思路推广，设 $A(1,1),B(2,1),C(1,j),D(i,1)$

1. $C,D$ 在奇数列上， $A\oplus B\oplus C\oplus D=0,E\oplus F\oplus G\oplus H=0,=> A\oplus C\oplus F\oplus H=0,A\oplus H=C\oplus F.$
2. $C,D$ 在偶数列上。$A\oplus B\oplus C\oplus D=1,E\oplus F\oplus G\oplus H=1.$ 此时，当 $H$ 在偶数行，$1\oplus A\oplus H=C\oplus F$ ；如果在奇数行，则有 $A\oplus H=C\oplus F.$

综上所述，对于任意 $H(i,j):$

如果 $i|2,j|2$ ，那么 $1\oplus (1,1)\oplus (i,j)=(1,j)\oplus (i,1)$ ；否则 $(1,1)\oplus (i,j)=(1,j)\oplus (i,1)$

这样就转化为对 $(1,j),(i,1)$ 的约束。如果 $(1,1)$ 没有给出，那么就要枚举两种情况。

用并查集维护。$x\oplus y=0$ 时，合并 $(x,y),(x’,y’)$ ；否则合并 $(x,y’),(x’,y)$。无解特判就是 $x,x’\in S$ （属于同一个集合）

合并完成之后得到连通块个数 $sum$ ，枚举所有已知点（注意 $(1,1)$ 不算），去掉他们的连通块，剩下的就是未知个数，$2^{sum’}$ 即为方案。把 $(1,1)$ 的两种情况相加即可。

注意：此题由于有虚点（ $x’,y’$ ），所以空间要两倍。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9,N=2e5+10;
int n,m,k,x[N],y[N],z[N],fa[N],g[N];

ll power( ll a,ll b )
{
        ll res=1;
        for ( ; b; b>>=1,a=a*a%mod )
                if ( b&1 ) res=res*a%mod;
        return res;
}

int find( int x )
{
        if ( x==fa[x] ) return x;
        int fat=find( fa[x] ); g[x]^=g[fa[x]]; 
        return fa[x]=fat;
}

int calc( int opt )
{
        for ( int i=1; i<=n+m; i++ )
                fa[i]=i,g[i]=0;
        fa[n+1]=1;
        if ( opt==1 )
                for ( int i=1; i<=k; i++ )
                        if ( x[i]>1 && y[i]>1 ) z[i]^=1;
        for ( int i=1; i<=k; i++ )
        {
                int x=:: x[i],y=:: y[i],z=:: z[i];
                if ( x!=1 || y!=1 )
                {
                        int fx=find(x),fy=find(y+n),ty=g[x]^g[n+y]^z;
                        if ( fx!=fy ) fa[fy]=fx,g[fy]=ty;
                        else if ( ty ) return 0;
                }
        }
        int res=0;
        for ( int i=1; i<=n+m; i++ )
                if ( i==find(i) ) res++;
        return power( 2,res-1 );
}

int main()
{
        scanf( "%d%d%d",&n,&m,&k );
        int flag=-1;
        for ( int i=1; i<=k; i++ )
        {
                scanf( "%d%d%d",&x[i],&y[i],&z[i] );
                if ( (!(x[i]&1)) && (!(y[i]&1)) ) z[i]^=1;
                if ( x[i]==1 && y[i]==1 ) flag=z[i];
        }

        if ( flag!=-1 ) printf( "%d\n",calc( flag ) );
        else printf( "%d\n",(calc(0)+calc(1))%mod );       
}