[APIO2011]方格染色（带权并查集，连通块问题）

• 每一个2*2矩阵的异或值为1

• 任意一个矩阵的左上左下右上右下的值异或值为1/0

• 且当这个矩阵由奇数个2*2矩阵组成时为0，偶数个为1

• 题目给出了(k)个条件，可以发现，确定了左上角和右下角后，我们就可以知道左下角和右上角的关系（相等或不等）

• 我们枚举(1,1)这个点，这样，就有(k)组关系式。

• 建出一个二分图，当某两个点已经被联通且边的异或值与将要连的边权值相等，那么便无解

• 用带权并查集维护连通块

• 最后答案就是(2^{连通块个数-1})

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5, MOD = 1e9;
int n, m, k;
int x[N], y[N], z[N];
int fa[N << 1], g[N << 1];
inline int read () {
    int tot = 0, f = 1; char c = getchar ();
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar (); }
    while (c >= '0' && c <= '9') { tot = tot * 10 + c - '0'; c = getchar (); }
    return tot * f;
}
inline int find (int t) { // 带权并查集
    if (fa[t] == t) return t;
    int tmp = find (fa[t]);
    g[t] ^= g[fa[t]];
    return fa[t] = tmp;
}
inline int qpow (int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}
inline int work (int tag) {
    if (tag) for (int i = 1; i <= k; i++) { // 更换（1，1）项
        if (x[i] != 1 && y[i] != 1) z[i] ^= 1;
    }
    for (int i = 1; i <= n + m; i++) fa[i] = i, g[i] = 0;
    fa[n + 1] = 1;
    for (int i = 1; i <= k; i++) { // 合并联通块
        int fx = find (x[i]), fy = find (n + y[i]); // warning!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
        int tx = g[x[i]] ^ g[y[i] + n] ^ z[i];
        if (fx != fy) {
            fa[fy] = fx;
            g[fy] = tx;
        }
        else if (tx) return 0;
    }
    int tot = 0;
    for (int i = 1; i <= n + m; i++)
        if (find (i) == i) tot++;
    return qpow (2, tot - 1);
}
signed main () {
    n = read (); m = read (); k = read ();
    int flag = -1;
    for (int i = 1; i <= k; i++) {
        x[i] = read (); y[i] = read (); z[i] = read ();
        if ((x[i]&1) == 0 && (y[i]&1) == 0) z[i] ^= 1; // 先假装（1，1）是0
        if (x[i] == 1 && y[i] == 1) // 如果（1，1）已经给定，则不必枚举
            flag = z[i];
    }
    if (flag != -1) printf ("%lld
", work(flag) % MOD);
    else printf ("%lld
", (work(0) + work(1)) % MOD);//枚举（1，1）项
    return 0;
}