题意：

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

分析：

题意可以转化为：每 $2\times 2$方格中的异或值为１．
假设我们在棋盘上选择了一些点，这些点的异或值为 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;
}