题意:

给你一个$n\times m$的棋盘(n,m<=1e6),每个方格里填入1或0,要求每个$2\times 2$的方格中1为奇数个.有一些格子已经填了1或0,求总方案数.

分析:

题意可以转化为:每$2\times 2$方格中的异或值为1.
假设我们在棋盘上选择了一些点,这些点的异或值为x.如果我们继续选择一个$2\times 2$的方格中的点,那么异或值将变为x^1.选择方格的时候,已经选过的再选一遍,对x的影响就消除了,因此相当于它没有被选,因此选与不选也成为了异或的过程.
因此我们可以选择一些恰当的方格,使得真正被选择的格子比较恰当.
比如,通过尝试,我们可以知道:
对于都是偶数的x,y,有:(1,1)^(x,y)^(1,y)^(x,1)=1
对于其他的x,y,有:(1,1)^(x,y)^(1,y)^(x,1)=0
这样,对于任何一个已知格子,我们都可以求出第一行和第一列的某些格子的相等或不相等的关系.这种关系可以利用带权并查集轻松维护.

但是还是有一个需要注意的地方:如何判定无解.

对于x,y都不是1的已知格子,我们用它维护并查集.
对于x,y中存在1的已知格子,我们用它来强制将一个并查集设为已知,或者判断是否与已经已知的并查集冲突,来判断无解.

至此该算法就可以在luogu和BZOJ上AC了.


#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 2000002
#define MD 1000000000

using namespace std;

typedef long long ll;

int fa[MX],dis[MX];
int must[MX],have[MX];
int n,m,k;
int px[MX],py[MX],pn[MX];
int vis[MX];

ll ksm(ll x,int t)
{
    ll ans=1;
    while(t)
    {
        if(t&1)ans=ans*x%MD;
        x=x*x%MD;
        t>>=1;
    }
    return ans;
}

int findfa(int x)
{
    if(fa[x]==x)return x;
    else
    {
        findfa(fa[x]);
        dis[x]+=dis[fa[x]];
        fa[x]=fa[fa[x]];
        return fa[x];
    }
}

ll work(int top)
{
    int f1,f2,x,y,del,ans=0;
    for(int i=1;i<=n+m;i++)fa[i]=i,dis[i]=0,vis[i]=0,must[i]=0,have[i]=0;
    for(int i=1;i<=k;i++)
    {
        if(px[i]==1||py[i]==1)continue;
        f1=findfa(x=px[i]);
        f2=findfa(y=(py[i]+n));
        del=(top+pn[i])&1;
        if(f1==f2)
        {
            if(((x&1)||(y&1)))
            {
                if((dis[x]+del)%2!=dis[y]%2)return 0;
            }
            else
            {
                if((dis[x]+del)%2==dis[y]%2)return 0;
            }
        }
        else
        {
            fa[f1]=f2;
            dis[f1]=((dis[x]%2!=dis[y]%2)+del+((x&1)||(y&1))+1)%2;
        }
    }
    fa[1]=n+1;
    have[findfa(1)]=1;
    must[fa[1]]=top;
    for(int i=1;i<=k;i++)
    {
        x=px[i];
        y=n+py[i];
        if(px[i]==1)
        {
            if(have[findfa(y)]==0)have[fa[y]]=1,must[fa[y]]=(pn[i]+dis[y])%2;
            else if(must[fa[y]]!=(pn[i]+dis[y])%2)return 0;
        }
        if(py[i]==1)
        {
            if(have[findfa(x)]==0)have[fa[x]]=1,must[fa[x]]=(pn[i]+dis[x])%2;
            else if(must[fa[x]]!=(pn[i]+dis[x])%2)return 0;
        }
    }
    for(int i=1;i<=n+m;i++)
        if(!vis[findfa(i)]&&!have[findfa(i)])
            vis[fa[i]]=1,ans++;
    return ksm(2,ans);
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;i++)scanf("%d%d%d",&px[i],&py[i],&pn[i]);
    cout<<(work(0)+work(1))%MD<<endl;
    return 0;
}
分类: 所有

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *