夏晓光(loveJY)的博客

写这题解就离谱...

看上去就好神仙啊,考虑dp怎么解决?不太行,因为只有20pts

于是我们考虑找找规律,能发现相当于四个点如果为红色就是1,为蓝色就是0,那么异或起来值为1

然后这个结论由于异或显然有拓展性

XZU
YWI

X^Y^Z^W=Z^W^U^I=1

X^Y^U^I=0!

那么好像我们可以通过类似于平移一块2*2地毯的形式去不断的得到新的这样的关系

然后又找到了新结论:确定第一行第一列就确定了整个矩阵

证明显然吧,自己推一推?

然后相当于我们要计算第一行第一列的填色方案,于是考虑用这个东西找到规律

如果对于矩阵1,1->x,y,x,y中有一个为偶数那么异或值为0,否则为1

这个可以考虑这个矩阵中有多少个2*2得知

然后有了这个结论我们就可以考虑通过枚举1,1的取值来缩点得到几个连通块进而计算出答案

同一连通块的值确地一个就确定了整块,所以就为2^连通块数是答案

然后注意这样我们的给出的(x,y)是用于缩连通块的,而且他的取值决定了这一切是否合法

是否合法的部分可以用带权并查集去解决

你又会发现我们可以通过增加一行0来解决枚举1,1取值,不过没什么必要,只是更好写

而且我们之前结论还要变一下...

有一个坑点是模数是1e9不是质数...

code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int P = 1e9;
const long long inv2 = (P) / 2;
const int MAXN = 1e6 + 7;
int f[MAXN], op[MAXN], val[MAXN];
inline int getf(int x) {
	return f[x] == x ? x : f[x] = getf(f[x]);
}
inline int merge(int x, int y, int z) {
	int f1 = getf(x);
	int f2 = getf(y);
	if(z) {
		if(f1 == f2)return 0;
		if(f1 == op[f2])return 1;
		f[f1] = op[f2];
		f[op[f1]] = f2;
	} else {
		if(f1 == op[f2])return 0;
		if(f1 == f2)return 1;

		f[f1] = f2;
		f[op[f1]] = op[f2];
	}
	return 1;
}
long long ksm(long long x, long long y) {
	long long ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}
int n, m, k;
int main() {
	scanf("%d%d%d", &n, &m, &k);
	int qwq = n + m;
	for(int i = 1; i <= qwq; ++i) {
		f[i] = op[i + qwq] = i;
		f[i + qwq] = op[i] = i + qwq;
		//扩展域并查集
	}
	for(int i = 1, x, y, z; i <= k; ++i) {
		scanf("%d%d%d", &x, &y, &z);
		if(((x + 1 & 1) == 0) && (y + 1 & 1) == 0)z ^= 1;
		y += n;
		if(!merge(x, y, z)) {
			puts("0");
			return 0;
		}
	}
	// puts("qwq");
	long long ans = 0;
	int st = getf(1);
	val[op[st]] = 1;
	val[st] = 1;
	for(int i = 2; i <= qwq; ++i) {
		int p = getf(i);
		if(!val[p]) {
			++ans;
			// printf("%d?\n", p);
		}
		val[p] = val[op[p]] = 1;
	}
	printf("%lld\n", ksm(2, ans));
	return 0;
}