感觉题解区里的形式化解法不是人类能够想到的，这里给出一个比较容易理解的解题过程。

思路

没有已经染色的格子限制

思考整个问题的简化版，假设 $n=2$，且没有已经染色的限制，则答案怎么求？我们进行一个简单的分类讨论：

• 如果第一列的两个格子颜色不同：则下一列的颜色必然相同，再下一列的各自颜色必然不同，以此类推，而对于每一列，显然有 $2$ 种不同的涂色方案，则共有 $2^m$ 次方种涂色方案。
• 如果第一列的两个格子颜色相同：则下一列的颜色必然不同，再下一列的各自颜色必然相同，以此类推，而对于每一列，显然有 $2$ 种不同的涂色方案，则共有 $2^m$ 次方种涂色方案。

综上，显然是有 $2^{m+1}$ 种不同的涂色方案的。

这时，我们考虑把 $n$ 放大，看看会发生什么：

• 首先，第一列的涂色情况是没有限制的，所以方案数是 $2^n$。
• 而对于第 $i+1$ 列来说，其涂色方法是依赖于第 $i$ 列的，就像 $n=2$ 时，如果上下相邻两个格子在上一行里颜色相同，则在这一行里颜色就不同，否则就直接反过来。而这时，如果你确认了第一行的格子颜色是什么，你就可以根据这个方法把这一列里所有的格子全部确认下来。
• 于是每一列又有了 $2$ 种方案，最终用乘法原理乘起来就是 $2^{n+m-1}$ 种情况了。

正解

分析一下上述部分的关键：如果上下相邻两个格子在上一行里颜色相同，则在这一行里颜色就不同，否则相反。

观察该条性质的实质，通过手玩一下格子即可看出来，若用 $0,1$ 分别表示红色和蓝色，则上述过程完全等价于：将上一列的所有奇数行或者偶数行取反。

此时，我们便可以来理解限制对答案的影响：

• 如果某一列中有至少一个被涂色了的格子，则无论上一列是什么，想要推得这一列的情况至多只会有一种操作方式，也就是说在上一列已知的情况下，这一列最多只有一种情况。证明是容易的，随便选取一个被涂色了的点，如果该点和上一行的点颜色一样，则进行取反时就不能对该点所在的奇偶性进行取反，剩下的几种情况也是一样的。
• 如果某一列中只有一个被涂色了的格子，则其对上一行实际上没有要求，无论如何都不会产生冲突，这里的产生冲突是指导致不存在符合条件的涂色方案。
• 如果某一列中有多个被涂色的了格子，则我们随机选取两个格子：
  • 如果这两个格子所在的行奇偶性相同，则在第一列中，对应行上的格子颜色是否相同与这两个格子是一样的。
  • 如果这两个格子所在的行奇偶性不同，则在第一列中，对应行上的格子颜色是否相同是取决于这两个格子的，具体来说：
    • 如果这一列是奇数列：则在第一列中，对应行上的格子颜色是否相同与这两个格子是相反的。
    • 如果这一列是偶数列：则在第一列中，对应行上的格子颜色是否相同与这两个格子是一样的。

于是，我们能够把所谓的涂色限制，转化为在第一列中某两个格子的颜色是否一样，这个东西就很简单了，显然用一个扩展域并查集维护即可。

而对于某一列中的多个限制来说，不难发现其具有传递性，所以我们实际上不需要对任意两个限制进行转化，只需要对上下相邻的限制转化即可。

综上所述，则我们能够求得最终答案为：

• 如果条件出现了冲突，即没有满足条件的涂色方案，输出 0。
• 否则，统计第一列的连通块个数，注意要去掉那些已经确认了颜色的块数，记其为 $c_1$；记第 $2$ 到 $m$ 列中没有涂色限制的列的个数为 $c_2$。输出 $2^{c_1+c_2}$ 即可。

代码

这个铸币笔者把 merge_ 打错了，导致调了一个下午，大家都快来嘲笑他。

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const ll N=1e6+10;
const ll MOD=1000000000;
ll fa[N<<1],n,m,k;
void init(){for(ll i=1;i<=(n<<1);i++) fa[i]=i;}
ll findf(ll x){return (fa[x]==x)?x:fa[x]=findf(fa[x]);}
void merge_(ll x,ll y){
	ll fx=findf(x),fy=findf(y);
	if(fy!=fx) fa[fy]=fx;
}
pair<ll,bool> lst[N];
struct node{ll x,y;bool col;}dot[N];
inline bool cmp(node x,node y){return x.x<y.x;}
ll ans=1;
bool vis[N];
ll clc[N],p1,p2;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>k;
	init();
	for(ll i=1;i<=k;i++) cin>>dot[i].x>>dot[i].y>>dot[i].col;
	sort(dot+1,dot+1+k,cmp);
	for(ll i=1;i<=k;i++){
		ll L=dot[i].y;
		if(lst[L].first){
			if(lst[L].first%2==dot[i].x%2){
				if(lst[L].second==dot[i].col) merge_(lst[L].first,dot[i].x),merge_(lst[L].first+n,dot[i].x+n);
				else merge_(lst[L].first,dot[i].x+n),merge_(lst[L].first+n,dot[i].x);
			}
			else{
				if(lst[L].second==dot[i].col) merge_(lst[L].first,dot[i].x+((L+1)&1)*n),merge_(lst[L].first+n,dot[i].x+(L&1)*n);
				else merge_(lst[L].first,dot[i].x+(L&1)*n),merge_(lst[L].first+n,dot[i].x+((L+1)&1)*n);
			}
		}
		lst[L].first=dot[i].x,lst[L].second=dot[i].col;
	}
	for(ll i=1;i<=n;i++){
		ll f=findf(i),nf=findf(i+n);
		if(f==nf){cout<<"0";return 0;}
	}
	for(ll i=1;i<=k;i++){
		ll L=dot[i].y;if(L!=1) continue;
		ll f=findf(dot[i].x),nf=findf(dot[i].x+n);
		if(!vis[f]){
			vis[f]=1;vis[nf]=1;
			clc[f]=dot[i].col+1;clc[nf]=(dot[i].col^1)+1;
		}
		else if(clc[f]!=dot[i].col+1||clc[nf]!=(dot[i].col^1)+1){cout<<"0";return 0;}
	}
	ll cnt=0,ccnt=0;
	for(ll i=1;i<=n;i++){
		ll f=findf(i),nf=findf(i+n);
		if(vis[f]) continue;
		vis[f]=vis[nf]=1;
		cnt++;
	}
	for(ll i=2;i<=m;i++) if(!lst[i].first) ccnt++;
	cnt+=ccnt;
	while(cnt--) ans=(ans<<1)%MOD; 
	cout<<ans;
	return 0;
}

首先，假设 $mp[x][y]$ 表示第 $x$ 行，第 $y$ 列的颜色，则题目的要求可以转化为

$$mp[x][y]\oplus mp[x][y-1]\oplus mp[x-1][y]\oplus mp[x-1][y-1]=1 $$

其中 $\oplus$ 表示按位异或。

暴力

然后注意到如果一个 $2\times 2$ 的方格中，有三个已经确定颜色了，另外的一个的颜色可以直接确定。我们根据这个可以写出暴力代码，枚举第一行和第一列的颜色，复杂度 $\Theta(2^{n+m})$。

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e<'0'||e>'9') {
		if(e=='-')y=-1;
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<1)+(x<<3)+(e^'0');
		e=getchar();
	}
	return x*y;
}
int n,m,k,ans;
int mp[130][130],a[130][130];
signed main() {
	R(n),R(m),R(k);
	memset(mp,-1,sizeof mp);
	for(int i=1; i<=k; ++i) {
		int R(x),R(y),R(c);
		mp[x][y]=c;
	}
	for(int i=0; i<(1<<m); ++i) {
		for(int j=0; j<(1<<n); ++j) {
			if((i&1)!=(j&1))continue;
			int fl=1;
			for(int x=1; x<=n; ++x) {
				if(mp[1][x]!=-1&&(i>>(x-1)&1)!=mp[1][x]) {
					fl=0;
					break;
				}
				a[1][x]=(i>>(x-1)&1);
			}
			if(!fl)continue;
			for(int y=1; y<=m; ++y) {
				if(mp[y][1]!=-1&&(j>>(y-1)&1)!=mp[y][1]) {
					fl=0;
					break;
				}
				a[y][1]=(j>>(y-1)&1);
			}
			if(!fl)continue;
			for(int x=2; x<13; ++x) {
				for(int y=2; y<13; ++y) {
					a[x][y]=mp[x][y];
				}
			}
			for(int x=2; x<=n&&fl; ++x) {
				for(int y=2; y<=m&&fl; ++y) {
					int s=a[x-1][y]+a[x][y-1]+a[x-1][y-1];
					a[x][y]=(s&1)^1;
					if(mp[x][y]!=-1&&mp[x][y]!=a[x][y]) fl=0;
				}
			}
			if(fl)++ans;
		}
	}
	cout<<ans<<"\n";
	return 0;
}

接下来我们考虑正解。注意到 $n,m$ 比较大，所以我们必须把 $mp[x][y]$ 颜色转化为更加好处理的条件。我们不妨看一下题目要求的公式有什么性质。

先说结论，当 $x$，$y$ 中至少有一个是奇数时，$mp[x][y]=mp[x][1]\oplus mp[1][y]\oplus mp[1][1]$。

当 $x$，$y$ 全是偶数时，$mp[x][y]=mp[x][1]\oplus mp[1][y]\oplus mp[1][1]\oplus 1$。

证明

我们代入 $(x-1,y)$。

$$mp[x-1][y]\oplus mp[x-2][y]\oplus mp[x-1][y-1]\oplus mp[x-2][y-1]=1 $$

与最初的公式联立，可以得到：

$$mp[x-2][y]\oplus mp[x-2][y-1]=mp[x][y]\oplus mp[x][y-1] $$

如果 $x$ 为奇数，那么可以一直迭代这个式子。

$$mp[1][y]\oplus mp[1][y-1]=mp[x][y]\oplus mp[x][y-1] $$

然后我们稍微移一下项。

$$mp[x][y]=mp[1][y]\oplus mp[1][y-1]\oplus mp[x][y-1] $$

其中的 $mp[x][y-1]$ 又可以迭上面的式子，即：

$$mp[x][y-1]=mp[x][y-2]\oplus mp[1][y-1]\oplus mp[1][y-2] $$

把这个式子带回原式，得到：

$$mp[x][y]=mp[1][y]\oplus mp[1][y-2]\oplus mp[x][y-2] $$

此时我们已经找到规律，如果我们一直迭代这个式子，我们最终能够得到：

$$mp[x][y]=mp[x][1]\oplus mp[1][y]\oplus mp[1][1]$$

注意我们的前提是 $x$ 为奇数。同理我们可以得到当 $y$ 为奇数时，上式也成立。

现在我们讨论 $x$，$y$ 全都是偶数的情况，我们把

$$mp[x][y]=mp[x-1][y]\oplus mp[x-1][y-1]\oplus mp[x][y-1]\oplus 1 $$

按照刚才的推论展开，我们有：

$$mp[x][y]=mp[1][y]\oplus mp[x-1][1]\oplus mp[1][1]\oplus mp[x-1][1]\oplus mp[1][y-1]\oplus mp[1][1]\oplus mp[x][1]\oplus mp[1][y-1]\oplus mp[1][1]\oplus1 $$

异或全部抵消掉，得到：

$$mp[x][y]=mp[x][1]\oplus mp[1][y]\oplus mp[1][1]\oplus 1 $$

上式成立的条件是 $x$，$y$ 全是偶数。

做法

通过我们刚才的推论，我们可以把每一个 $mp[x][y]$ 投影成 $mp[1][1]$，$mp[x][1]$ 和 $mp[1][y]$ 之间的关系。其中 $mp[1][1]$ 可以枚举得到。然后我们可以开一个带权并查集，$dep_x$ 表示 $x$ 和根节点的关系。

最后统计答案时，每个连通块都有两种方案，但是由于我们钦定了 $mp[1][1]$，所以 $(1,1)$ 所在连通块只能算一次。

代码

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e<'0'||e>'9') {
		if(e=='-')y=-1;
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<1)+(x<<3)+(e^'0');
		e=getchar();
	}
	return x*y;
}
const int N=100005,mod=1e9;
int n,m,k;
struct node{
	int x,y,c;
}a[N];
int fa[N<<1],dep[N<<1];
int Find(int x){
	if(x==fa[x])return x;
	int rt=Find(fa[x]);
	dep[x]^=dep[fa[x]];
	return fa[x]=rt;
}
//mp[x][y]=mp[x][1]^mp[1][y]^a11^(x%2==0&&y%2==0)
int work(int a11){
	for(int i=1;i<=n+m;++i)fa[i]=i;
	fa[1]=1+n; 
	memset(dep,0,sizeof dep);
	for(int i=1;i<=k;++i){
		int x=a[i].x,y=a[i].y,c=a[i].c;
		if(x==1&&y==1)continue; 
		int fx=Find(x),fy=Find(y+n);
		bool fl=x%2==0&&y%2==0;
		if(fx==fy&&(dep[x]^dep[y+n]^c^a11^fl))return 0;
		if(fx!=fy){
			fa[fx]=fy;
			dep[fx]=dep[x]^dep[y+n]^c^a11^fl;
		}
	}
	int res=1;
	for(int i=1;i<=n+m;++i){
		if(i==Find(i)&&Find(i)!=Find(1)) res=res*2%mod;
	}
	return res;
}
int mp11[2],ans;
signed main() {
//	freopen("ex.in","r",stdin);
	R(n),R(m),R(k);
	for(int i=1;i<=k;++i){
		R(a[i].x),R(a[i].y),R(a[i].c);
		if(a[i].x==1&&a[i].y==1) mp11[a[i].c]=1;
	}
	for(int i=0;i<2;++i){
		if(!mp11[i])ans+=work(i^1);
	}
	cout<<ans%mod<<"\n";
	return 0;
}