E1. 墨西哥比索（简单版本）详细题解

1. 问题理解

• 有一个 $n \times m$ 的网格，部分单元格已填充值 $v$（$0 \le v < 2^{30}$）。
• 网格是美丽的，当且仅当对于任意 $2 \times 2$ 子网格，四个角的异或和为 $0$：$$A_{i_1,j_1} \oplus A_{i_1,j_2} \oplus A_{i_2,j_1} \oplus A_{i_2,j_2} = 0 $$
• 需要计算填充剩余单元格的方案数（模 $10^9+7$）。
• 在简单版本中，$q = 0$，没有更新操作。

---

2. 关键观察

观察 1：条件等价于任意 $2 \times 2$ 子网格异或和为 $0$

由于异或的性质，这个条件实际上等价于：

$$A_{i_1,j_1} \oplus A_{i_1,j_2} = A_{i_2,j_1} \oplus A_{i_2,j_2} $$

即同一列两行的差值与行无关。

观察 2：存在行数组 $X$ 和列数组 $Y$

可以证明，对于任意满足条件的网格，存在两个数组 $X[1..n]$ 和 $Y[1..m]$，使得：

$$A_{i,j} = X[i] \oplus Y[j]$$

证明思路：

• 固定 $A_{1,1} = X[1] \oplus Y[1]$，令 $X[1] = 0$，则 $Y[1] = A_{1,1}$
• 由 $2 \times 2$ 条件可递推出所有 $X[i]$ 和 $Y[j]$

---

3. 图论建模

将每个已知单元格 $A_{i,j} = v$ 转化为约束：

$$X[i] \oplus Y[j] = v$$

这等价于：

$$X[i] = Y[j] \oplus v \quad \text{或} \quad Y[j] = X[i] \oplus v $$

我们可以构建一个二分图：

• 左侧节点：行 $1..n$（编号 $0..n-1$）
• 右侧节点：列 $1..m$（编号 $n..n+m-1$）
• 对于已知单元格 $(i, j, v)$，在行节点 $i$ 和列节点 $n+j-1$ 之间添加一条边，权值为 $v$

关键性质：在图中，任意路径的异或和给出了两个端点之间的关系。

---

4. 一致性检查

在 DFS 过程中，我们维护 pref[u] 表示从当前连通分量的根到节点 $u$ 的路径异或和。

对于一条边 $(u, v, w)$：

• 如果 $v$ 未访问，则 pref[v] = pref[u] ^ w
• 如果 $v$ 已访问，则检查 (pref[u] ^ pref[v]) == w
  • 如果不成立，则存在矛盾，答案为 $0$

这实际上是在检查所有环的异或和是否为 $0$。

---

5. 计算方案数

假设没有矛盾，设图中有 $K$ 个连通分量。

对于每个连通分量：

• 一旦确定其中一个节点的值，整个分量的所有节点值都被确定
• 每个连通分量有 $2^{30}$ 种可能的起始值（因为 $X[1]$ 可以自由选择）

但是，不同连通分量之间是独立的吗？不是完全独立，因为 $X[i]$ 和 $Y[j]$ 的值可以任意选择，但一旦选择了一个分量的根值，整个分量就固定了。

实际上，总方案数为：

$$(2^{30})^{K-1}$$

解释：

• 整个图有 $n+m$ 个节点（行 + 列）
• 有 $K$ 个连通分量
• 第一个分量的根可以自由选择（$2^{30}$ 种）
• 后续每个分量需要一条边连接到已知分量，该边的权值有 $2^{30}$ 种选择
• 总方案数 = $2^{30} \times (2^{30})^{K-1} = (2^{30})^{K}$？等等，需要仔细推导。

实际上，对于每个连通分量，一旦根节点值确定，整个分量就确定了。但不同分量之间没有约束，所以每个分量可以独立选择根值。总方案数 = $(2^{30})^{K}$。

但注意：$X[1]$ 和 $Y[1]$ 不是独立的吗？等等，实际上行和列的总自由度是 $n+m-1$（因为 $X[1]$ 固定后，所有其他值由边确定）。这正好对应 $K$ 个连通分量：$K$ 个自由参数。

重新推导：

• 一个连通分量有 $s$ 个节点，自由度为 $1$（选择一个根的值）
• $K$ 个连通分量 → 自由度为 $K$
• 但 $X$ 和 $Y$ 的表示中，整体异或一个常数不影响结果？实际上，如果所有 $X[i]$ 和 $Y[j]$ 都异或同一个常数 $c$，$A_{i,j} = (X[i] \oplus c) \oplus (Y[j] \oplus c) = X[i] \oplus Y[j]$ 不变。所以有一个冗余自由度。

因此，有效自由度 = $K - 1$。

所以方案数 = $(2^{30})^{K-1}$。

---

6. 算法步骤

1. 构建二分图：$n+m$ 个节点，$k$ 条边
2. DFS 遍历，检查所有环的异或和是否为 $0$
3. 统计连通分量数 $K$
4. 如果有矛盾，输出 $0$；否则输出 $(2^{30})^{K-1} \bmod (10^9+7)$

---

7. 时间复杂度

• 建图：$O(k)$
• DFS：$O(n + m + k)$
• 总复杂度：$O(\sum (n + m + k)) \le 3 \times 10^5$，完全可行

---

8. 代码实现要点

precalc[0] = 1;
for (int i = 1; i < Mxn; i++) {
    precalc[i] = (precalc[i-1] << 30) % MOD;
}

• 预计算 $(2^{30})^i \bmod MOD$

void dfs(int node) {
    for (auto [child, w] : adj[node]) {
        if (pref[child] == -1) {
            pref[child] = pref[node] ^ w;
            dfs(child);
        } else {
            if ((pref[child] ^ pref[node]) != w) valid = false;
        }
    }
}

• DFS 遍历，维护路径异或和

---

9. 示例验证

第一个示例：

• $n=3, m=3, k=8$，有 $8$ 个已知单元格
• 图中有 $n+m=6$ 个节点，$8$ 条边
• 检查一致性后，$K=1$（全连通）
• 方案数 = $(2^{30})^{0} = 1$ ✅

---

10. 总结

核心思想：

1. 美丽网格等价于存在 $X[i]$ 和 $Y[j]$ 使得 $A_{i,j} = X[i] \oplus Y[j]$
2. 将已知单元格建模为二分图中的边
3. 检查所有环的异或和是否为 $0$
4. 方案数 = $(2^{30})^{K-1}$，其中 $K$ 是连通分量数