luoguP3631 [APIO2011]方格染色

边带权并查集

方格染色

转化有点多

思路

给一个转化：我们就是要保证任意一个 $2 \times 2$ 的矩阵异或和为 $1$

那么不难发现，只要第一行和第一列定了，整个矩阵就出来了，所以，如果 $k = 0$ 的话，答案就是 $2^{n + m - 1}$

考虑每个确定的点，这里有一个结论：任意一个 $a \times b$ 的矩阵四个角的异或值只和 $a, b$ 的奇偶性有关，证明：把 $2 \times 2$ 的矩阵依次覆盖在上面，当且仅当 $a, b$ 同时为偶数时，四个角异或和为 $1$ （因为最后只有四个角只被覆盖了一次，而只有 $a, b$ 为偶数的时候，所有 $2 \times 2$ 的矩阵异或和为 $1$ ）

那么对于给定 $(x, y) = c$ ，有 $(1, 1) \oplus (1, y) \oplus (x, 1) \oplus c = [x, y同时为偶数]$ ，我们发现，当 $(1, 1)$ 确定后， $(1, y)$ 和 $(x, 1)$ 的关系（相等或不等）就定了，用带权并查集维护这个关系，最后答案就是 $2^{联通个数 - 1}$

代码

一个特别难调的地方：合并时一定要先 $get()$ 再计算权值，因为 $get()$ 里面会修改权值！

#include <bits/stdc++.h>
using LL = long long;
const int N = 1e5 + 100, P = 1e9;
int n, m, num, nm, fa[N << 1], w[N << 1], rk[N << 1];
struct Q{ int x, y, c; } q[N];
int qpow(int x, int y)
{
    int res = 1;
    for (; y; y >>= 1, x = LL(x) * x % P) if (y & 1) res = LL(res) * x % P;
    return res;
}
int get(int x)
{
    if (x == fa[x]) return x;
    int t = get(fa[x]);
    w[x] ^= w[fa[x]];
    return fa[x] = t;
}
bool merge(int x, int y, int v)
{
    int fx = get(x), fy = get(y);
    v ^= w[x] ^ w[y];
    if (fx == fy) return !v;
    if (rk[fx] > rk[fy]) std::swap(fx, fy);
    fa[fx] = fy, w[fx] = v, rk[fy] += rk[fx] == rk[fy];
    return true;
}
int work(int col)
{
    int res = 0;
    for (int i = 1; i <= nm; ++i) fa[i] = i, w[i] = 0;
    fa[n + 1] = 1; //n+1和1是一个点
    for (int i = 1, x, y, c; i <= num; ++i)
    {
        x = q[i].x, y = q[i].y, c = q[i].c;
        if (x == 1 && y == 1)
            if (c == col) continue;
            else return 0;
        c ^= !(x & 1) && !(y & 1);
        if (x > 1 && y > 1) c ^= col; 
        if (!merge(x, y + n, c)) return 0;
    }
    for (int i = 1; i <= nm; ++i) res += get(i) == i;
    return qpow(2, res - 1);
}
int main()
{
    scanf("%d %d %d", &n, &m, &num);
    nm = n + m;
    for (int i = 1; i <= num; ++i) scanf("%d %d %d", &q[i].x, &q[i].y, &q[i].c);
    printf("%d\n", (work(0) + work(1)) % P);
    return 0;
}