CF2022E 题解 | 数学、并查集

传送门

标签：数学、并查集

题意

给你一个 \(n\) 行 \(m\) 列的矩阵 \(a\)，满足限定条件：
对于 \(\forall i_1, i_2, j_1, j_2, a_{i_1, j_1} \oplus a_{i_2, j_1} \oplus a_{i_1, j_2} \oplus a_{i_2, j_2} = 0\)。
换句话说，就是所有的子矩阵都满足四个角上的值异或和为 \(0\)。

同时，给出 \(k\) 个约束，形如 \(a_{r, c} = v\)。
给出 \(q\) 个持久化修改，形如 \(a_{r, c} = v\)。

思路

\[\because a_{i_1, j_1} \oplus a_{i_2, j_1} \oplus a_{i_1, j_2} \oplus a_{i_2, j_2} = 0 \]

\[\therefore a_{i_1, j_1} \oplus a_{i_1, j_2} = a_{i_2, j_1} \oplus a_{i_2, j_2} \]

即，给定 \(i_1, i_2\)，这两行中同一列的两个数异或和是定值，也就是不受到 \(j\) 的影响。

同时结合异或的性质，我们已经可以猜想：构造一个数列 \(Y_{1,...,m}\)，\(a_{i,j}\) 是 \(Y_{j}\) 异或另一些值得到的。
同理，我们将行和列换过来，可以得到类似的直觉，于是大胆猜想：\(a_{i,j}=X_{i} \oplus Y_{j}\)。

经过验证，这是满足题目限定的一种构造。

证明：\(a_{i,j}=X_{i} \oplus Y_{j}\)：

观察这个式子，肯定要将一个坐标和行、列结合。
又是异或运算，容易想到 \(a'_{i,j} \leftarrow a_{i,j} \oplus a_{i,1} \oplus a_{1,j}\)。

然后我们发现，这样之后得到的新的 \(a'\) 依然是满足条件的矩阵。

证明：

每个子矩阵的表达式都异或上了 \(a_{i_1, 1}, a_{i_2, 1}, a_{1, j_1}, a_{1, j_2}\) 且都异或两遍。

那么，考虑一个左上角的矩阵（即 \(i_1 = j_1 = 1\)）：

\[\because a'_{1, 1} = a'_{1, j_2} = a'{i_2, 1} = a_{1, 1} \]

\[\therefore a'_{i_2, j_2} = a_{1, 1}, \therefore a_{i_2, j_2} = a_{1, 1} \oplus a_{i_2, 1} \oplus a_{1, j_2} \]