「Bzoj 2303」「Apio2011」方格染色 (带权并查集+异或方程+数学归纳法)

发表于 | 分类于 | | + s

BZOJ 2303
题意：有一个$n \times m$的矩阵，可以放入$0$或$1$，现在已经有$k$个格子放好了$0$或$1$，要把矩阵放满，要求是矩阵中每个$2 \times 2$的格子有奇数个$1$。输入$n、m$和已经放了的格子，求方案数。

根据异或性质$a \oplus b \oplus a = b$
考虑一个矩阵

ABCD
EFGH
IJKL

我们发现对于任意$2 \times 2$矩形异或和都是$1$，因为要符合题意

那么我们发现
$$
A \oplus B \oplus E \oplus F=1 \tag{1}
$$
$$
B \oplus C \oplus F \oplus G=1 \tag{2}
$$
$(1), (2)$异或，则得
$$
A \oplus E \oplus C \oplus G=0 \tag{3}
$$
又可以得到
$$
C \oplus G \oplus D \oplus H = 1 \tag{4}
$$
$(3), (4)$异或，则得
$$
A \oplus E \oplus D \oplus H = 1
$$
我们发现横向异或可以数学归纳法证明，$(1,1) \to (i, j)​$, 如果列数是偶数，则异或和为1，否则为0
对于列同理
那么我们发现只要行列都是偶数，那么异或和是1，否则是0

也可以直观上来看，对于$(1,1) \to (i, j)$这个矩形，考虑矩形包含$2 \times 2$矩形的个数。

根据数学归纳法，如果原方格内的第一行和第一列的格子被确定，那么整个方格即可被唯一确定。

我们可以发现$(1,1) \oplus (i,1) \oplus (1,j) \oplus (i,j)=0 / 1$ (取决于上述规则)

那么我们就可以枚举$(1,1)$填什么(如果没有限定，否则就只填一种)，然后维护异或关系。

显然可以用带权并查集来做。具体看代码实现。最后答案是除了$(1,1)$联通块的个数$k$, $2^k$

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 200000 + 5, MO = 1e9;

    int n, m, k, x[MAXN], y[MAXN], c[MAXN];
    int f[MAXN], g[MAXN]; // g[i] 是 i 和 rt 的关系

    int find(int x) {
        if (x == f[x]) return x;
        int rt = find(f[x]);
        g[x] ^= g[f[x]];
        return f[x] = rt;
    }
    void mge(int a, int b, int ans) { // 带权并查集
        int x = find(a), y = find(b);
        if (x != y) {
            f[x] = y;
            g[x] = g[a] ^ g[b] ^ ans; 
        }
    }

    LL ksm(LL a, LL b) {
        LL ans = 1, bs = a;
        while (b) {
            if (b & 1) ans = (ans * bs) % MO;
            bs = (bs * bs) % MO;
            b >>= 1;
        }
        return ans;
    }

    LL work(int whw) {
        for (int i = 0; i <= n + m; ++i) f[i] = i, g[i] = 0; f[n + 1] = 1; // n + 1, 1 是同一个位置
        for (int i = 1; i <= k; ++i) {
            int tx = x[i], ty = y[i];
            if (tx == 1 && ty == 1) continue ;
            if (tx % 2 == 0 && ty % 2 == 0) { // 行列均偶
                if (whw ^ c[i] ^ 1) {
                    if (find(tx) == find(ty + n) && (g[tx] ^ g[ty + n]) != 1) return 0; 
                    mge(tx, ty + n, 1);
                } else {
                    if (find(tx) == find(ty + n) && (g[tx] ^ g[ty + n]) != 0) return 0;     
                    mge(tx, ty + n, 0);
                }
            } else {
                if (whw ^ c[i]) {
                    if (find(tx) == find(ty + n) && (g[tx] ^ g[ty + n]) != 1) return 0; 
                    mge(tx, ty + n, 1);
                } else {
                    if (find(tx) == find(ty + n) && (g[tx] ^ g[ty + n]) != 0) return 0;     
                    mge(tx, ty + n, 0);
                }
            }
        }
        int tot = 0;
        for (int i = 1; i <= n + m; ++i) if (find(i) == i) ++tot; // 找连通块

        return ksm(2ll, tot - 1);
    }

    void clean() {
    }
    int solve() {

        clean();
        cin >> n >> m >> k;
        int fl = -1;
        for (int i = 1; i <= k; ++i) {
            scanf("%d%d%d", &x[i], &y[i], &c[i]);
            if (x[i] == 1 && y[i] == 1) fl = c[i]; // 1 被确定
        }

        if (fl == -1) {
            printf("%lld\n", (work(1) + work(0)) % MO);
        } else printf("%lld\n", work(fl));

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
//
/*
1 1 1
1 1 0
*/
------ 本文结束 ------