題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 P3631 [APIO2011] 方格染色

Problem Statement

題目簡述

給定一個 n×mn \times m 的方格，部分格子已經被染上紅色（1）或藍色（0）。要求判定是否能將所有剩餘格子填滿，並使得每個 2×22 \times 2 的子矩陣都包含奇數個紅色格子。如果可以，請求出所有合法的染色方案數對 10910^9 取模的結果。

Constraints

約束條件

  • 2⩽n,m⩽1052 \leqslant n,m \leqslant 10^5
  • 0⩽k⩽1050 \leqslant k \leqslant 10^5
  • 1⩽xi⩽n,1⩽yi⩽m1 \leqslant x_i \leqslant n, 1 \leqslant y_i \leqslant m
  • ci∈{0,1}c_i \in \{0,1\}

思路：帶權並查集 (Weighted DSU)

這道題目要求每一個 2×22 \times 2 的區域中都有奇數個紅色格子。我們約定紅色為 1，藍色為 0。
對於任意一個左上角座標為 (i,j)(i, j) 的 2×22 \times 2 矩型，必須滿足其內部四個格子的異或 (XOR) 和為 1：

A[i][j]⊕A[i+1][j]⊕A[i][j+1]⊕A[i+1][j+1]=1A[i][j] \oplus A[i+1][j] \oplus A[i][j+1] \oplus A[i+1][j+1] = 1

1. 將局部約束推廣至全局

如果我們把左上角為 (1,1)(1, 1)、右下角為 (x,y)(x, y) 的長方形中，所有 (x−1)×(y−1)(x-1) \times (y-1) 個 2×22 \times 2 小矩形的異或和全部 XOR 起來，會發生什麼事？

抵消原理

對這個大範圍的內部格子求異或和時，同一個格子會被重複計算。計算次數取決於該格子的位置：

  • 四個頂點 (1,1),(1,y),(x,1),(x,y)(1, 1), (1, y), (x, 1), (x, y) 只會被計算 1次。
  • 在邊界上但非頂點的格子，會被相鄰的兩個 2×22 \times 2 覆蓋，被計算 2次。
  • 在內部的格子，會被周圍的四個 2×22 \times 2 覆蓋，被計算 4次。

根據異或的性質 k⊕k=0k \oplus k = 0，被計算偶數次的格子都會抵消。

因此，所有小矩形的異或和將只剩下四個頂角的格子被留下來：

A[1][1]⊕A[1][y]⊕A[x][1]⊕A[x][y]A[1][1] \oplus A[1][y] \oplus A[x][1] \oplus A[x][y]

因為整個範圍內共有 (x−1)(y−1)(x-1)(y-1) 個小區域，每個區域的異或值都是 1，所以總異或和等於該數字的奇偶性：

A[1][1]⊕A[1][y]⊕A[x][1]⊕A[x][y]=(x−1)(y−1)(mod2)A[1][1] \oplus A[1][y] \oplus A[x][1] \oplus A[x][y] = (x-1)(y-1) \pmod 2

2. 轉換為帶權並查集模型

我們可以透過移項，將目標格子 A[x][y]A[x][y] 用邊界的格子表示出來：

A[x][y]=A[1][y]⊕A[x][1]⊕A[1][1]⊕((x−1)(y−1) & 1)A[x][y] = A[1][y] \oplus A[x][1] \oplus A[1][1] \oplus ((x-1)(y-1) \ \& \ 1)

為了方便表示，令Rx=A[x][1]R_x = A[x][1]，Cy=A[1][y]C_y = A[1][y]。
我們把原式整理為關於 RxR_x 與 CyC_y 的關係式：

Rx⊕Cy=A[x][y]⊕A[1][1]⊕((x−1)(y−1) & 1)R_x \oplus C_y = A[x][y] \oplus A[1][1] \oplus ((x-1)(y-1) \ \& \ 1)

我們發現只要給定第一橫列 RR 和第一直行 CC 的所有值，整個面板的填色狀態就會被唯一確定。而且上面的方程式只描述了兩個變數之間的異或值（距離），這正是帶權並查集經典的應用場景：
把 N=n+mN=n+m 個變數當成圖上的節點，RxR_x 與 CyC_y 的權重距離即為等號右側的常數。

處理未知數 A[1][1]A[1][1]

由於我們不知道左上角 A[1][1]A[1][1] 是 0 還是 1，但它只有兩種可能，因此可以直接：

  1. 枚舉 A[1][1]∈{0,1}A[1][1] \in \{0, 1\}。
  2. 將基準條件 R1⊕C1=0R_1 \oplus C_1 = 0 加入並查集（因為它們代表同一個格子 A[1][1]A[1][1]）。
  3. 對於每條已知的條件，如果並查集合併時發生權重矛盾，代表這條分支出現了不合法的組合；如果順利走完，說明這條分支可行。

3. 計算合法方案數

當檢查完所有給定約束後不發生衝突時，還有多少變數可以自由選擇？
在並查集森林中，如果共有 vv 個節點，cc 個連通分量。每個連通分量只要確定其中一個點的值（選 0 或選 1），內部其它點的值就會受約束立刻確定。理論上自由度為 cc 個。

但必須注意，包含節點 11（即 R1,C1R_1, C_1）的連通分量是不能夠被自由設定的。因為 R1R_1 的值剛好就是我們當下枚舉的 A[1][1]A[1][1]，它已經被事先規定死了。
所以剩下來真正未確定、可自由指定的連通分量為 c−1c - 1 個，這條分支貢獻的合法塗色方案數就是：

2c−1 mod 1092^{c - 1} \bmod 10^9

最後將 A[1][1]=0A[1][1] = 0 和 A[1][1]=1A[1][1] = 1 所產生的方案數相加，即可得到答案。

複雜度分析

  • 時間複雜度：O(n+m+kα(n+m))\mathcal{O}(n + m + k \alpha(n+m))。需要對兩種可能狀態各進行一輪並查集合併並遍歷連通塊計數，複雜度取決於初始化並查集的 O(n+m)\mathcal{O}(n+m) 以及加入限制的 O(kα(n+m))\mathcal{O}(k \alpha(n+m))。
  • 空間複雜度：O(n+m)\mathcal{O}(n+m)。

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
from typing import Optional

class WeightedDSU:
    """
    帶權並查集
    維護條件：potential(y) - potential(x) = w

    支援：
    - union(x, y, w): 合併並加入約束 y - x = w
    - diff(x, y): 若同集合，回傳 y - x；否則回傳 None
    """

    def __init__(self, n: int):
        self.n = n
        self.fa = list(range(n))
        self.sz = [1] * n
        # dis[x] = potential(x) - potential(fa[x])
        self.dis = [0] * n

    def find(self, x: int) -> int:
        """回傳 x 的根，同時做路徑壓縮並更新 dis[x] 為 x 到根的位勢差。"""
        fa = self.fa
        if fa[x] != x:
            rt = self.find(fa[x])
            self.dis[x] += self.dis[fa[x]]
            self.dis[x] %= 2
            fa[x] = rt
        return fa[x]

    def potential(self, x: int) -> int:
        """回傳 potential(x) - potential(fa[x])"""
        self.find(x)
        return self.dis[x]

    def union(self, x: int, y: int, w: int) -> bool:
        """
        合併並加入約束：potential(y) - potential(x) = w
        回傳：
        - True：成功合併（或已同集合且不發生矛盾）
        - False：已同集合但發生矛盾
        """
        w %= 2
        rx, ry = self.find(x), self.find(y)
        dx, dy = self.dis[x], self.dis[y]
        if rx == ry:
            # x 和 y 在同一集合，不做合併
            return (dy - dx) % 2 == w

        if self.sz[rx] < self.sz[ry]:  # fa[rx] = ry
            # rx <------- ry
            # |           |
            # | dx        | dy
            # ↓           ↓
            # x --------> y
            # => pot(rx) - pot(ry) = dy - w - dx
            self.fa[rx] = ry
            self.dis[rx] = (dy - w - dx) % 2
            self.sz[ry] += self.sz[rx]
        else:  # fa[ry] = rx
            # rx -------> ry
            # |           |
            # | dx        | dy
            # ↓     w     ↓
            # x --------> y
            # => pot(ry) - pot(rx) = w - dy + dx
            self.fa[ry] = rx
            self.dis[ry] = (w - dy + dx) % 2
            self.sz[rx] += self.sz[ry]

        return True

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    def diff(self, x: int, y: int) -> Optional[int]:
        """
        若同集合，回傳 potential(y) - potential(x)，否則回傳 None
        """
        if not self.same(x, y):
            return None
        return self.potential(y) - self.potential(x)


MOD = int(1e9)


def solve():
    n, m, k = map(int, input().split())
    N = n + m + 1

    constraints = []
    for _ in range(k):
        x, y, c = map(int, input().split())
        constraints.append((x, y, c))

    ans = 0
    for a in (0, 1):  # 枚舉 A[1][1] 是 0 或 1
        uf = WeightedDSU(N)
        uf.union(1, n + 1, 0)  # 約束: R[1] ^ C[1] = 0
        for x, y, c in constraints:
            w = c ^ ((x - 1) * (y - 1) & 1) ^ a
            if not uf.union(x, n + y, w):
                break
        else:
            comps = sum(1 for u in range(1, N) if uf.find(u) == u)
            ans += pow(2, comps - 1, MOD) % MOD
            ans %= MOD

    print(ans)


if __name__ == "__main__":
    solve()