BZOJ 2303 方格染色(带权并查集)

要使得每个2*2的矩形有奇数个红色，如果我们把红色记为1，蓝色记为0，那么我们得到了这2*2的矩形里的数字异或和为1.

对于每个方格则有a(i,j)^a(i-1,j)^a(i,j-1)^a(i-1,j-1)=1.由这些方程可以推出对于每个方格:

如果i,j都是偶数，则有a(i,j)^a(1,1)^a(i,1)^a(1,j)=1.

否则，a(i,j)^a(1,1)^a(i,1)^a(1,j)=0.枚举a(1,1)的染色情况。可以由a(i,j)的染色情况推出a(i,1)和a(1,j)是否颜色相同或者相反。

类似于a bug's life。那么把它们用带权并查集维护后，染色的种数就是一些联通块的染色种数，因为这些联通块互相不影响。

那么总染色数就是2^(cnt-1).

# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <set>
# include <cmath>
# include <algorithm>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-3
# define MOD 1000000000
# define INF 1000000000
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FO(i,a,n) for(int i=a; i<n; ++i)
# define bug puts("H");
# define lch p<<1,l,mid
# define rch p<<1|1,mid+1,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
int Scan() {
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void Out(int a) {
    if(a<0) {putchar('-'); a=-a;}
    if(a>=10) Out(a/10);
    putchar(a%10+'0');
}
const int N=200005;
//Code begin...

struct Node{int l, r, c;}node[N];
int fa[N], dis[N];

LL pow_mod(LL a, LL n, LL mod){
    LL ret=1, temp=a%mod;
    while (n) {
        if (n&1) ret=ret*temp%mod;
        temp=temp*temp%mod;
        n>>=1;
    }
    return ret;
}
int find(int x){
    int tmp;
    if (fa[x]!=x) tmp=find(fa[x]), dis[x]=dis[x]^dis[fa[x]], fa[x]=tmp;
    return fa[x];
}
bool union_set(int x, int y, int d){
    int u=find(x), v=find(y);
    if (u!=v) {dis[u]=dis[y]^d^dis[x]; fa[u]=v; return true;}
    else return dis[x]^dis[y]^d==0;
}
int main ()
{
    int n, m, k, u, v, flag;
    LL ans=0;
    scanf("%d%d%d",&n,&m,&k);
    FOR(i,1,k) scanf("%d%d%d",&node[i].l,&node[i].r,&node[i].c);
    mem(dis,0); flag=true; FOR(i,1,n+m-1) fa[i]=i;
    FOR(i,1,k) {
        if (node[i].l==1) u=1;
        else u=m+node[i].l-1;
        v=node[i].r;
        if (node[i].l%2==0&&node[i].r%2==0) {
            if (!union_set(u,v,node[i].c^1)) {flag=false; break;}
        }
        else {
            if (!union_set(u,v,node[i].c)) {flag=false; break;}
        }
    }
    if (flag) {
        int cnt=0;
        FOR(i,1,n+m-1) if (fa[i]==i) ++cnt;
        ans=(ans+pow_mod(2,cnt-1,MOD))%MOD;
    }
    mem(dis,0); flag=true; FOR(i,1,n+m-1) fa[i]=i;
    FOR(i,1,k) {
        if (node[i].l==1) u=1;
        else u=m+node[i].l-1;
        v=node[i].r;
        if (node[i].l%2==0&&node[i].r%2==0) {
            if (!union_set(u,v,node[i].c)) {flag=false; break;}
        }
        else {
            if (!union_set(u,v,node[i].c^1)) {flag=false; break;}
        }
    }
    if (flag) {
        int cnt=0;
        FOR(i,1,n+m-1) if (fa[i]==i) ++cnt;
        ans=(ans+pow_mod(2,cnt-1,MOD))%MOD;
    }
    printf("%lld
",ans);
    return 0;
}

View Code

BZOJ 2303 方格染色(带权并查集)

相关推荐