Description：

一个 $n\times m$ 的矩阵，每个位置为红色或者蓝色，有些位置已经填了一些颜色，每个 $2\times 2$ 的方格里必须有奇数个蓝色，问是否存在合法方案以及合法方案的个数。

$1\leqslant n,m,k\leqslant 10^5$

Solution：

第一个问题是怎么处理每个 $2\times2$ 的方格里有奇数个蓝格子，设蓝格子为 $1$ ，红为 $0$ ，那么每一个 $2\times2$ 的格子异或和都为 $1$ ，即 $s[i][j]\text{ xor }s[i-1][j]\text{ xor }s[i][j-1]\text{ xor }s[i-1][j-1]=1$ ，推一下式子会发现 $s[i][j]\text{ xor }s[i-1][j]\text{ xor }s[i][1]\text{ xor }s[i-1][1]=[j\%2=0]$ ，同理可以发现 $s[i][j]\text{ xor }s[i][1]\text{ xor }s[1][j]\text{ xor }s[1]][1]=[i与j同为偶数]$ ，发现这题有一个重要的性质是只要确定了第一行第一列，整个矩阵的形态就确定了，所以先枚举 $s[1][1]$ ，新建一个节点代表 $1$ ，已经确定的点和这个点连 $1$ 或 $0$ 的边，对于其他的把两个在第 $1$ 行或第 $1$ 列的点连起来，这个可以用带权并查集维护一下，最后结果就是 $2$ 的联通快个数 $-1$ 次方，因为和新点相连的点的权值是确定的。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MOD 1000000000

int n,m,k;

#define MAXN 100010

int x[MAXN],y[MAXN],v[MAXN];

int f[MAXN << 1],g[MAXN << 1];

int find(int x)

{

	if(x == f[x])return x;

	int fa = find(f[x]);

	g[x] = g[x] ^ g[f[x]];

	f[x] = fa;

	return fa;

}

int cnt;

int merge(int a,int b,int c)

{

	int p = find(a),q = find(b);

	if(p == q)

	{

		return (g[a] ^ g[b] ^ c);

	}

	else

	{

		--cnt;

		g[p] = g[a] ^ g[b] ^ c;

		f[p] = q;

		return 0;

	}

}

int to(int i,int j)

{

	if(j == 1)return m + i;

	else return j;

}

int power(int a,int b)

{

	int res = 1;

	while(b > 0)

	{

		if(b & 1)res = 1ll * res * a % MOD;

		a = 1ll * a * a % MOD;

		b = b >> 1;

	}

	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],&v[i]);

	}

	int ans = 0;

	for(int a11 = 0;a11 <= 1;++a11)

	{

		for(int i = 1;i <= n + m;++i)f[i] = i;

		for(int i = 1;i <= n + m;++i)g[i] = 0;

		cnt = n + m;

		merge(to(1,1),1,a11 ^ 1);

		bool tag = true;

		for(int i = 1;i <= k;++i)

		{

			if(x[i] == 1 || y[i] == 1)

			{

				if(merge(to(x[i],y[i]),1,v[i] ^ 1))

				{

					tag = false;break;

				}

				continue;

			}

			if(merge(to(x[i],1),to(1,y[i]),v[i] ^ a11 ^ (!(x[i] & 1) && !(y[i] & 1))))

			{

				tag = false;break;

			}

		}

		if(tag)ans = (ans + power(2,cnt - 1)) % MOD;

	}

	cout << ans << endl;

	return 0;

}