题解：P10456 The Pilots Brothers' refrigerator

Sunnysky0 · 2025-04-04 13:28:08 · 题解

一种多项式时间算法

由于每个手柄有且只有 2 种状态，所以可以用二进制 0 和 1 来表示，因此可以将翻转问题建模为异或方程组（或者 GF(2) 上的线性方程组）。

异或方程组的构建

对于 4×4 矩阵的 16 个位置，我们定义 16 个变量 x_{i,j}:

对于输入的矩阵，将符号 + 定义为 1（表示需要翻转为 - ），符号 - 定义为 0（已经是目标状态）。初始矩阵的状态用 0 和 1 表示，例如：

+--+    1 0 0 1
-++- -> 0 1 1 0
+++-    1 1 1 0
-+++    0 1 1 1

最终目标是使所有位置的最终状态变为 0。

现在考虑翻转操作的影响，显然，对于原矩阵中的每个状态，翻转两次相当于不翻转。翻转位置 [i,j] 会影响：

第 i 行的所有位置：[i, 0], [i, 1], [i, 2], [i, 3]。
第 j 列的所有位置：[0, j], [1, j], [2, j], [3, j]。

因此，我们可以将位置[p, q]上的最终状态表示为初始状态加上翻转次数的异或：

s_{p,q} = a_{p,q} \oplus(\bigoplus^3_{j=0}x_{p,j})\oplus(\bigoplus^3_{i=0}x_{i,q})

因为目标是所有位置变为“-”（即 0），所以：
a_{p,q} \oplus(\bigoplus^3_{j=0}x_{p,j})\oplus(\bigoplus^3_{i=0}x_{i,q}) = 0
(\bigoplus^3_{j=0}x_{p,j})\oplus(\bigoplus^3_{i=0}x_{i,q}) = a_{p,q}

这就是位置 [p, q] 上的方程。

接下来就可以写出整个方程组的矩阵表示。总共有 16 个位置，因此需要 16 个方程，并且每个方程涉及 16 个变量 x_{i, j} 。

为方便处理，将 4×4 矩阵元素的坐标 [i, j] 映射为 0 到 15 的编号：

idx(i,j)=i×4+j

对于每个位置 [i, j]:

第 i 行的变量 x_{i,0},x_{i, 1}, x_{i, 2}, x_{i, 3} 的系数为 1
第 j 列的 x_{0, j}, x_{1, j}, x_{2, j}, x_{3, j} 的系数为 1
常数项：a_{i, j}

最终得到一个 16×17 的增广矩阵，如：

位置  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | 常数
[0,0] 1 1 1 1 1 0 0 0 1 0  0  0  1  0  0  0 | 1
[0,1] 1 1 1 1 0 1 0 0 0 1  0  0  0  1  0  0 | 0
[0,2] 1 1 1 1 0 0 1 0 0 0  1  0  0  0  1  0 | 0
[0,3] 1 1 1 1 0 0 0 1 0 0  0  1  0  0  0  1 | 1
...

表示为 AX = B ，其中 A 为系数矩阵， X 为未知数列向量，B 为常数项列向量

使用高斯消元法（在模 2 运算下）求解此矩阵方程即可。

有解性及唯一性证明

先考虑齐次方程 AX=0 ，显然 X=0 是解。接下来讨论非平凡解是否存在。

显然， X=\left[\begin{matrix} 1 \\ ... \\ 1\end{matrix}\right] 不是解，于是设某个 x_{i, j} = 1 ，那么对于 x_{i, k} = 0 且 k \not=j，位置 [i, k] 上的方程为 1\oplus0=0 ，无解。于是对于第 j 列的所有 x_{p, j} ，都有 x_{p, j}=1。同理，对于第 i 列的所有 x_{i, q} ，都有 x_{i, q}=1 。重复这个过程，必然得到 X=\left[\begin{matrix} 1 \\ ... \\ 1\end{matrix}\right] \oplus \left[\begin{matrix} 1 \\ ... \\ 1\end{matrix}\right] = \left[\begin{matrix} 0 \\ ... \\ 0\end{matrix}\right]，于是 X=0 是唯一解。

由此可知，AX=B 有唯一解。

注意：这里“唯一”指的是翻转位置的集合唯一，而非翻转的顺序（顺序不影响异或结果）。

得到最简步骤

现在我们得到了一个解，但是这个解一定对应着最少翻转次数吗？由于方程组有唯一解，任何其他翻转组合要么无法实现目标，要么与此解相同。从而可知解中的每个操作都是必要的，去掉任何一个都会导致失败。

最优性证明

假设存在一个更小的操作集合 S，其翻转次数少于解向量中 1 的数量, 设 X_S 为 S 对应的向量。
若 A X_S = B , 则得到 X_S = X ，与 S 中翻转次数少于解向量 X 中 1 的数量矛盾。
反之，则得到A X_S \not= B，与 S 是解矛盾。

于是解向量 X 便对应唯一的最优翻转操作步骤。从 X 得到翻转操作是简单的。令 x_i = 1 是 X 的第 i 个元素，由于使用映射 idx(i,j)=i×4+j 将 [i, j] 映射到整数，只需求出其反函数 arcidx(x)=[x/4,\ x\mod 4] 即可知道翻转 x_i 对应的行和列。

复杂度 O(N^6)=O(4096) 远优于二进制状态枚举

附上高斯消元代码

int mat[M][M + 1];
vector<int> row_reduction() {
    vector<int> solution(M, 0);
    for(int col = 0; col < M; col++) {
        int pivot = -1;
        for(int row = col; row < M; row++) {
            if(mat[row][col] == 1) {
                pivot = row;
                break;
            }
        }
        if(pivot == -1) continue;
        if(pivot != col)
            for(int j = col; j <= M; j++)
                swap(mat[col][j], mat[pivot][j]);
        for(int row = 0; row < M; row++) {
            if(row != col && mat[row][col] == 1)
                for(int j = col; j <= M; j++)
                    mat[row][j] ^= mat[col][j];
        }
    }
    for(int row = M - 1; row >= 0; row--) {
        int leading = -1;
        for(int col = 0; col < M; col++) {
            if(mat[row][col] == 1) {
                leading = col;
                break;
            }
        }
        if(leading == -1) continue;
        solution[leading] = mat[row][M];
        for(int col = leading + 1; col < M; col++)
            if(mat[row][col] == 1)
                solution[leading] ^= solution[col];
    }
    return solution;
}