题目描述
给定 \(k\) 个坐标的颜色 \((0\) 或 \(1)\)，用 \(0\) 和 \(1\) 两种颜色对剩下的方格染色，使得对于任意 \(2 \times 2\) 的方格中，只有 \(1\) 个 \(1\) 或 \(3\) 个 \(1\)。求满足条件的染色方案数，答案对 \(10^9\) 取模。
数据范围：\(2 \leqslant n,m \leqslant 10^5\)，\(0 \leqslant k \leqslant 10^5\)。
题解
本题解中 \(n, m\) 被视为同阶。
我们规定 \(f(x, y)\) 表示 \((x, y)\) 上的颜色。注意到，任意 $ 2 \times 2 $ 的方格中有 \(1\) 个或 \(3\) 个 \(1\)，这等价于这四个方格的异或和为 \(1\)，即对于任意 \(1 \le x < n\)，\(1 \le y < m\)，都满足：
\[f(x, y) \oplus f(x + 1, y) \oplus f(x, y + 1) \oplus f(x + 1, y + 1) = 1 \]Theorem 1
所以如果合法方格内的第一行和第一列的格子颜色被确定，那么整个 $ n \times m $ 方格即可被唯一确定。
Prove 1
如果我们已知 $ 2 \times 2 $ 的格子中的 \(3\) 个的颜色，显然可以确定剩下一个的颜色。接下来按照第二行，第三行，\(\dots\)，第 \(n\) 行的顺序，每行从左往右依次确定颜色，每次用 \((x - 1, y), (x, y - 1), (x - 1, y - 1)\) 三个点的颜色确定 \((x, y)\) 的颜色，即整个 $ n \times m $ 方格即可被唯一确定。
形式化地讲，利用数学归纳法，当 \(n = 1\) 或 \(m = 1\) 时结论显然成立。假定 \((n, m) = (x - 1, y)\) 和 \((n, m) = (x, y - 1)\) 结论成立，其中 \(x \ne 1, y \ne 1\)，那么当 \((n, m) = (x, y)\) 时，\(f(x, y) = f(x - 1, y) \oplus f(x, y - 1) \oplus f(x - 1, y - 1) \oplus 1\)，因此结论成立。
Theorem 2
合法方格中，对于任意 \(1 \le x \le n\)，\(1 \le y \le m\)，都有 \((1, 1)\)，\((x, y)\)，\((x, 1)\)，\((1, y)\) 的颜色异或和为 \((x - 1)(y - 1) \bmod 2\)，即
\[f(1, 1) \oplus f(1, y) \oplus f(x, 1) \oplus f(x, y) = \begin{cases} 1 & x \bmod 2 = y \bmod 2 = 0 \ \\ 0 & \text{Otherwise} \end{cases} \]Prove 2
我们将这 $ x \times y $ 方格中的每个 $ 2 \times 2 $ 的单位方格全部异或起来，注意到，不在该方格边缘的格子被异或了 \(4\) 次，而在方格边缘又不在四个角的格子被异或了 \(2\) 次，它们的颜色对答案不做贡献，因此最后的异或和等于方格中四个角的异或和。由于每个 $ 2 \times 2 $ 的单位方格的异或值都为 \(1\)，又共有 \((x - 1)(y - 1)\) 个单位方格，所以最后的异或和为 \((x - 1)(y - 1) \bmod 2\)。
由 \(\text{Theorem 1}\) 可知答案等价于第一行和第一列的合法染色数。
因此，我们考虑枚举 \((1, 1)\) 位置的颜色，对于每个已知的点 \((x, y)\)，由 \(\text{Theorem 2}\) 可知 \((x, 1)\) 和 \((1, y)\) 的关系，用拓展域并查集维护。如果在维护中矛盾，此时不存在合法方案，否则我们记 \(cnt\) 为第一行和第一列中连通块的数量，由于和 \((1, 1)\) 相连的点颜色确定，因此这次枚举答案便为 \(2 ^ {cnt - 1}\)，求和取模即可。
注意，若 \((1, 1)\) 的颜色已经确定，那么便不需要枚举。
时间复杂度为：$ \mathcal O(n \log n)$ 或 $ \mathcal O(n \times \alpha(n))$
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1000000000;
struct dsu {
vector<int> fa;
dsu(int n) : fa(n + 2) { iota(fa.begin(), fa.end(), 0); };
inline int Find(int r) {
while (r != fa[r]) r = fa[r] = fa[fa[r]];
return r;
}
inline bool Merge(int x, int y) {
x = Find(x); y = Find(y);
if (x == y) return true;
else return fa[y] = x, false;
}
}; // 并查集模板
inline int read() {
int w = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if(ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
w = (w << 1) + (w << 3) + ch - 48;
ch = getchar();
}
return w * f;
}
inline int Pow(int a, int b) {
int ans = 1;
a %= MOD;
for (; b; b >>= 1) {
if (b & 1) ans = ans * a % MOD;
a = a * a % MOD;
}
return ans;
}
signed main() {
int n, m, k, ans = 0, flag = -1;
n = read(); m = read(); k = read();
const int tot = n + m - 1; // 第一行和第一列的总点数
vector<int> x(k + 1), y(k + 1), z(k + 1);
for (int i = 1; i <= k; i++) {
x[i] = read(); y[i] = read(); z[i] = read();
if (y[i] == 1 && x[i] == 1) flag = z[i];
}
auto Pos = [&](int x, int op1, int op2) {
if (x == 1) {
if (op2 == 1) return tot + 1; // (1, 1) 的扩展域为 tot + 1
else return x;
}
if (op2 == 1) x += tot; // 表示为扩展域
if (op1 == 1) x += n - 1; // 表示在第一行上
return x;
};
for (int rt = 0; rt <= 1; rt++) {
int sum = 0;
dsu A(tot << 1);
if (flag != -1 && flag != rt) continue; // 若 (1, 1) 确定就不进行枚举
for (int i = 1; i <= k; i++) {
if (x[i] == 1 && y[i] == 1) continue;
int x1 = Pos(x[i], 0, 0), y1 = Pos(y[i], 1, 0), x2 = Pos(x[i], 0, 1), y2 = Pos(y[i], 1, 1);
int opt = ((x[i] & 1) | (y[i] & 1)) ^ (z[i] ^ rt);
if (!opt) A.Merge(x1, y2), A.Merge(x2, y1);
else A.Merge(x1, y1), A.Merge(x2, y2);
if (A.Find(x1) == A.Find(x2) || A.Find(y1) == A.Find(y2)) {
printf("0\n"); // 发生冲突
return 0;
}
}
for (int i = 1; i <= tot; i++)
if (i == A.Find(i)) sum++; // 统计联通块数目
ans = (ans + Pow(2, sum - 1)) % MOD;
}
printf("%lld\n", ans);
return 0;
}