P15410 「TBOI Round 1」Niton & Matrix
有两个大小为 $N \times M $ 的矩阵 \(A\) 和 \(B\)。矩阵中的每个元素都等于 \(0\) 或 \(1\)。定义矩阵 \(A'\) 为操作后的矩阵，你可以对矩阵 \(A\) 进行以下操作任意次（0 或更多）：
- 翻转某行：选择数字 \(k\)（\(1 \leq k \leq N\)），进行以下操作：\(A'_{i,j} \gets \begin{cases} A_{i,M - j + 1} , & i=k,\\A_{i,j} , & i\neq k.\end{cases}\)
- 翻转某列：选择数字 \(k\)（\(1 \leq k \leq M\)），进行以下操作：\(A'_{i,j} \gets \begin{cases} A_{N - i + 1,j} , & j=k,\\A_{i,j} , & j\neq k.\end{cases}\)
- 取反某行：选择数字 \(k\)（\(1 \leq k \leq N\)），进行以下操作：\(A'_{i,j} \gets \begin{cases} A_{i,j}\oplus 1 , & i=k,\\A_{i,j} , & i\neq k.\end{cases}\)
- 取反某列：选择数字 \(k\)（\(1 \leq k \leq M\)），进行以下操作：\(A'_{i,j} \gets \begin{cases} A_{i,j}\oplus 1 , & j=k,\\A_{i,j} , & j\neq k.\end{cases}\)
其中 \(\oplus\) 为异或运算，\(x \oplus 1\) 表示将 \(x\) 取反（\(0\) 变 \(1\)，\(1\) 变 \(0\)）。
求是否有一串合法的操作序列使得矩阵 \(A\) 等于矩阵 \(B\)。
对于 \(100\%\) 的数据，保证 \(1\leq N\)，$ M \leq 10^5$，\(1\leq N\times M \leq 10^5\)，\(1\leq T \leq 10\)。
点击查看解析
遇到这种题，我们可以从改变一个点要进行哪些操作，会影响到哪些点入手。比如说这个题，改变一个点的权值会使其关于中轴线对称的点改变。所以整个矩阵会形成若干个四元环，在不改变四元环整体异或和的情况下，可以将一个点的值修改成任意值。
P11543 [Code+#5] 我有矩阵，你有吗？
企鹅豆豆手里有两个 \(01\) 矩阵 \(\mathbf{A}\) 和 \(\mathbf{B}\)。他可以进行两种操作：
- 选择 \(\mathbf{A}\) 矩阵的一行，然后把这一行的 \(0\) 变成 \(1\)，把 \(1\) 变成 \(0\)。
- 选择 \(\mathbf{A}\) 矩阵的一列，然后把这一列的 \(0\) 变成 \(1\)，把 \(1\) 变成 \(0\)。
现在他想知道能不能把 \(\mathbf{A}\) 矩阵通过以上操作变成 \(\mathbf{B}\) 矩阵。保证 \(\mathbf{A}\) 矩阵和 \(\mathbf{B}\) 矩阵的大小一致。
对于所有数据，\(n \le 1000,m \le 1000\)。
点击查看解析
令 \(c_{i,j}=a_{i,j} \text{ xor} b_{i,j}\)，于是问题转化为若干次操作使 \(c_{i,j}\) 变为全 \(0\) 的状态。显然每一行和每一列至多操作一次。对于第一行，我们要使第一行全变为 \(0\)，只能把第一行中所有 \(c_{1,j}=1\) 的第 \(j\) 列操作才行。所以我们可以通过判定其他行的 \(1\) 的位置与第一行的差异来判定答案。