【APIO2011】方格染色 <带权并查集>

Posted on Symbols count in article: 986 Reading time ≈ 4 mins.

Problem

【APIO2011】方格染色

Time  Limit:  20  Sec\mathrm{Time\;Limit:\;20\;Sec}
Memory  Limit:  256MB\mathrm{Memory\;Limit:\;256MB}

Description

Sam\mathrm{Sam}和他的妹妹Sara\mathrm{Sara}有一个包含n×mn\times m个方格的表格。她们想要将其的每个方格都染成红色或蓝色。
出于个人喜好，他们想要表格中每个2×22\times 2的方形区域都包含奇数个（11个或33个）红色方格。 可是昨天晚上，有人已经给表格中的一些方格染上了颜色！
现在Sam\mathrm{Sam}和Sara\mathrm{Sara}非常生气。不过，他们想要知道是否可能给剩下的方格染上颜色，使得整个表格仍然满足她们的要求。
如果可能的话，满足他们要求的染色方案数有多少呢？

Input

输入的第一行包含三个整数nn, mm和kk，分别代表表格的行数、列数和已被染色的方格数目。
之后的kk行描述已被染色的方格。其中第ii行包含三个整数xix_i, yiy_i和cic_i，分别代表第ii个已被染色的方格的行编号、列编号和颜色。cic_i为11表示方格被染成红色，cic_i为00表示方格被染成蓝色。

Output

输出一个整数，表示可能的染色方案数目WW模10910^9得到的值。

Sample Input

1
2
3
4
3 4 3
2 2 1
1 2 0
2 3 1

Sample Output

1
8

Hint

对于所有的测试数据，2≤n,m≤1062\le n,m\le10^6, 0≤k≤1060\le k\le10^6, 1≤xi≤n1\le x_i\le n, 1≤yi≤m1\le y_i\le m。
数据为国内数据+国际数据+修正版
鸣谢GYZ

标签：带权并查集 异或方程组

Solution

并查集解异或方程组。

令ai,ja_{i,j}表示第ii行第jj列的格子最终是否被染，对于∀i∈[1,n),j∈[1,m)\forall i\in[1,n),j\in[1,m)，一定有ai,j⊕ai,j+1⊕ai+1,j⊕ai+1,j+1=1a_{i,j}\oplus a_{i,j+1}\oplus a_{i+1,j}\oplus a_{i+1,j+1}=1。而易得到结论：确定一行一列的情况，即可确定最后是否能正确染色。

于是我们尝试确定第一行和第一列的情况，即做一个n+m−1n+m-1个变量的异或方程组。
对于给定的ax,y=0/1a_{x,y}=0/1，我们如果把i∈[1,x),j∈[1,y)i\in[1,x),j\in[1,y)的所有上一段所属方程异或起来，那么相同元抵消，可知a1,1⊕ai,1⊕a1,j=ai,j⊕1a_{1,1}\oplus a_{i,1}\oplus a_{1,j}=a_{i,j}\oplus1，如果我们知道a1,1a_{1,1}，那么就能确定ai,1⊕a1,ja_{i,1}\oplus a_{1,j}的值，这时用一个带权并查集维护一下，即可得到联通块的个数。那么答案为2自由元个数−12^{自由元个数-1}（a1,1a_{1,1}所在联通块的取值是一定的）。
如果我们预先不知道a1,1a_{1,1}的值，就可以枚举两种取值，分别计算后加起来即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
#define MAX_N 200000
#define MOD 1000000000
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, k, f[MAX_N+5], g[MAX_N+5];
int x[MAX_N+5], y[MAX_N+5], c[MAX_N+5];
int getf(int x) {return f[x] == x ? x : getf(f[x]), g[x] ^= g[f[x]], f[x] = f[f[x]];}
lnt calc(int val) {
    lnt ret = 1;
    for (int i = 1; i <= k; i++) if (x[i] > 1 && y[i] > 1) c[i] ^= val;
    for (int i = 1; i <= n+m; i++) f[i] = i, g[i] = 0; f[n+1] = 1;
    for (int i = 1; i <= k; i++) if ((x[i]^1) || (y[i]^1)) {
        int u = getf(x[i]), v = getf(y[i]+n), w = g[x[i]]^g[y[i]+n]^c[i];
        if (u^v) f[v] = u, g[v] = w; else if (w) return 0LL;
    }
    for (int i = 1, t = 0; i <= n+m; i++) if (getf(i) == i)
        {if (t) (ret *= 2LL) %= MOD; else t = 1;}
    return ret;
}
int main() {
    read(n), read(m), read(k);
    bool f0 = true, f1 = true; lnt ans = 0;
    for (int i = 1; i <= k; i++) {
        read(x[i]), read(y[i]), read(c[i]);
        if (!(x[i]%2) && !(y[i]%2)) c[i] ^= 1;
        if (x[i] == 1 && y[i] == 1) c[i] ? f0 = false : f1 = false;
    }
    if (f0) (ans += calc(0)) %= MOD;
    if (f1) (ans += calc(1)) %= MOD;
    return printf("%lld\n", ans), 0;
}