LambdaOJ：十字刷子解题报告

wzf2000
2020年11月24日

主要题面

简单分析

对于题目给出的 $n \times m$ 维的矩阵，其中值为 $1$ 的点 $(i, j)$ ，我们希望刷到其奇数次，为 $0$ 的点，我们希望刷到其偶数次。

那么在异或的意义下（刷到一次就 ^=1），我们希望每个点被刷的状态构成的新矩阵，应该等于原矩阵（恰好抵消）。

因此很容易想到，假设 $x_{i, j}$ 表示每个点是否作为中心被刷， $a_{i, j}$ 为输入的矩阵的第 $i$ 行第 $j$ 列，那么对于每个点 $(i, j)$ 应该有方程：

$x_{i, j – 2} \oplus x_{i, j – 1} \oplus x_{i, j} \oplus x_{i, j + 1} \oplus x_{i, j + 2} \oplus x_{i – 2, j} \oplus x_{i – 1, j} \oplus x_{i + 1, j} \oplus x_{i + 2, j} = a_{i, j}$
其中

$\oplus$ 为异或，对于

$(i, j)$ 处于范围外的

$x_{i, j}$ 自动默认为

$0$ （即不构成影响）。

这样，我们得到了 $n \times m$ 个变量（ $x_{i, j}$ ）以及 $n \times m$ 个方程（每个 $a_{i, j}$ 对应一个）。

这样通过 bitset 和各种位运算优化，便可能可以通过本题（取决于你的常数）。

但我们当然也可以通过预先的降维来加快这一过程。

尝试优化？

下面所说变量均指 $x_{i, j}$ 。

我们考虑设定了前两作为中心是否被翻的状态，即 $x_{1, j}, x_{2, j}$ 。

那么对于 $a_{1, j}$ ：

$a_{1, j} = x_{1, j – 2} \oplus x_{1, j – 1} \oplus x_{1, j} \oplus x_{1, j + 1} \oplus x_{1, j + 2} \oplus x_{2, j} \oplus x_{3, j} \\ \Rightarrow x_{3, j} = x_{1, j – 2} \oplus x_{1, j – 1} \oplus x_{1, j} \oplus x_{1, j + 1} \oplus x_{1, j + 2} \oplus x_{2, j} \oplus a_{1, j}$
因此我们用前两行的变量和常数

$0, 1$ 表示出了第三行的变量。

进一步假设我们假设了前两行的变量，并且用前两行变量和最多一个常数表示出了前 $k – 1$ 行，那么第 $k$ 行有：

$x_{k – 2, j – 2} \oplus x_{k – 2, j – 1} \oplus x_{k – 2, j} \oplus x_{k – 2, j + 1} \oplus x_{k – 2, j + 2} \oplus x_{k – 4, j} \oplus x_{k – 3, j} \oplus x_{i – 1, j} \oplus x_{k, j} = a_{k – 2, j} \\ \Rightarrow x_{k, j} = x_{k – 2, j – 2} \oplus x_{k – 2, j – 1} \oplus x_{k – 2, j} \oplus x_{k – 2, j + 1} \oplus x_{k – 2, j + 2} \oplus x_{k – 4, j} \oplus x_{k – 3, j} \oplus x_{i – 1, j} \oplus a_{k – 2, j}$
根据前设，对于前

$k – 1$ 行的

$x_{i, j}(i \le k – 1)$ ，我们可以有（用前两行的变量表示）：

$x_{i, j} = \left(\bigoplus_{u = 1, 2, v = 1, \cdots, m} c_{i, j, u, v} x_{u, v} \right) \oplus c_{i, j}$
其中

$c_{i, j, u, v}$ 为

$x_{i, j}$ 表示中

$x_{u, v}$ 的系数。

因此通过递推我们得出第 $k$ 行的 $x_{k, j}$ ，进而得出所有 $n$ 行的变量表示。

这时我们考虑：

$\begin{cases} x_{n – 1, j – 2} \oplus x_{n – 1, j – 1} \oplus x_{n – 1, j} \oplus x_{n – 1, j + 1} \oplus x_{n – 1, j + 2} \oplus x_{n – 3, j} \oplus x_{n – 2, j} \oplus x_{n, j} = a_{n – 1, j} \\ x_{n, j – 2} \oplus x_{n, j – 1} \oplus x_{n, j} \oplus x_{n, j + 1} \oplus x_{n, j + 2} \oplus x_{n – 2, j} \oplus x_{n – 1, j} = a_{n, j} \end{cases}$
又由于上述方程的变量都可以表示为前两行变量的组合与一个常数

$0, 1$ 的异或和，因此实际上这

$2m$ （对于

$(n – 1, 1,\cdots, m)$ 和

$(n, 1, \cdots, m)$ ）个方程，实际上就是前两行

$2m$ 个变量的方程。

因此我们就成功降低了方程的维数，从 $n \times m$ 降到了 $2m$ 。

代码实现？

声明：下面代码不保证正确性！只是为了助于对上面分析的理解！如果因为简单的复制代码造成查重，后果自负！！！

为了下面叙述的方便，我们下面所说的坐标均改为 $0 \sim n – 1$ 和 $0 \sim m – 1$ （包括非代码部分），请各位自行转换一下。

首先我们假设读入的状态存储在了 bool a[100][100]; 这样的一个数组中。

由于上面所说的方法均需要考虑超出边界的情况，我们不妨先在边界自动添加两圈。

考虑一个系数数组 bool c[104][104][2][100];，其中 c[i][j][u][v] 表示上述中的 $c_{i – 2, j – 2, u, v}$ ，也就是 $x_{i – 2, j – 2}$ 中 $x_{u, v}$ 的系数，特别的，另外 d[i][j] 我们定义为常数 $0, 1$ 对其的影响。

首先我们先将 c 数组全部置零，然后设置前两行的初值：

for (int i = 0; i < 2; ++i)
    for (int j = 0; j < m; ++j)
        c[i + 2][j + 2][i][j] = 1;

这根据上面的假设也容易得到。

接下来我们进行剩余 $n – 2$ 行的状态递推：

for (int i = 2; i < n; ++i)
    for (int j = 0; j < m; ++j)
    {
        // 首先考虑常数项的影响
        d[i + 2][j + 2] = a[i - 2][j] ^ d[i - 2][j + 2] ^ d[i - 1][j + 2]
                                      ^ d[i + 1][j + 2] ^ d[i][j]
                                      ^ d[i][j + 1] ^ d[i][j + 2]
                                      ^ d[i][j + 3] ^ d[i][j + 4];
        // 各系数逐项异或得出总的系数
        for (int u = 0; u < 2; ++u)
            for (int v = 0; v < m; ++v)
                c[i + 2][j + 2][u][v] = c[i - 2][j + 2][u][v] ^ c[i - 1][j + 2][u][v]
                                      ^ c[i + 1][j + 2][u][v] ^ c[i][j][u][v]
                                      ^ c[i][j + 1][u][v] ^ c[i][j + 2][u][v]
                                      ^ c[i][j + 3][u][v] ^ c[i][j + 4][u][v];
    }

这样我们便得到了整个系数数组。

再考虑最后 $2m$ 行的状态，我们用 bool A[200][200]; 数组表示得出的方程的系数矩阵，bool b[200]; 数组表示常数项。

那么：

for (int j = 0; j < m; ++j)
{
    // 第 n - 1 行
    b[j] = d[n][j] ^ d[n][j + 1]
         ^ d[n][j + 2] ^ d[n][j + 3]
         ^ d[n - 2][j + 2] ^ d[n - 1][j + 2]
         ^ d[n + 1][j + 2] ^ d[n][j + 4]
         ^ a[n - 2][j];
    for (int u = 0; u < 2; ++u)
        for (int v = 0; v < m; ++v)
            A[j][u * m + v] = c[n][j][u][v] ^ c[n][j + 1][u][v]
                            ^ c[n][j + 2][u][v] ^ c[n][j + 3][u][v]
                            ^ c[n - 2][j + 2][u][v] ^ c[n - 1][j + 2][u][v]
                            ^ c[n + 1][j + 2][u][v] ^ c[n][j + 4][u][v];
    // 第 n 行
    b[j + m] = d[n + 1][j] ^ d[n + 1][j + 1]
             ^ d[n + 1][j + 2] ^ d[n + 1][j + 3]
             ^ d[n - 1][j + 2] ^ d[n][j + 2]
             ^ d[n + 1][j + 4] ^ a[n - 1][j];
    for (int u = 0; u < 2; ++u)
        for (int v = 0; v < m; ++v)
            A[j + m][u * m + v] = c[n + 1][j][u][v] ^ c[n + 1][j + 1][u][v]
                                ^ c[n + 1][j + 2][u][v] ^ c[n + 1][j + 3][u][v]
                                ^ c[n - 1][j + 2][u][v] ^ c[n][j + 2][u][v]
                                ^ c[n + 1][j + 4][u][v];
}

到此时我们已经得到了一个 $Ax = b$ 的异或方程组。

这种方程组与线性方程组很像，只是用异或代替了加法，乘法保持不变，并且所有的元素都是 $0, 1$ 。

对其求解基本类似于普通的高斯消元，下面假设这个方程组的阶数为 $n$ 。

for (int i = 0; i < N; ++i)
{
    int t = i;
    // 判断此列是主元列还是自由列
    for (int j = i; j < N; ++j)
        if (A[j][i])
        {
            t = j;
            break;
        }
    if (!A[t][i]) // 如果是自由列，那么自动将此列对应的变量设为 0，保证其对其他变量、方程不构成影响（当然也可设为 1，但可能导致一些麻烦）
    {
        for (int j = i; j < N; ++j)
            A[i][j] = 0;
        b[i] = 0;
        continue;
    }
    // 保证对角元 A[i][i] 为 1
    for (int j = i; j < N; ++j)
        swap(A[i][j], A[t][j]);
    swap(b[i], b[t]);
    for (int j = i + 1; j < N; ++j)
        if (A[j][i]) // 类比于倍加变换，化为上三角阵
        {
            for (int k = i; k < N; ++k)
                A[j][k] ^= A[i][k];
            b[j] ^= b[i];
        }
}

接下来，再进行从上三角阵到对角阵的消元：

for (int i = N - 1; i; --i)
    for (int j = i - 1; j >= 0; --j)
        if (A[j][i])
        {
            for (int k = i; k < N; k++)
                A[j][k] ^= A[i][k];
            b[j] ^= b[i];
        }

最终得到的 b 数组实际上就是我们想要的解。

最后只须根据解得的解代入 c 和 d 的系数即可得到每个点的变量解 $x_{i, j}$ ，这也就是我们所需要的答案了。

另外，也可以考虑在转移 c 和 d 时，假设矩阵增加了两行，这样就会多出两行变量的条件。

但是由于其实际上是不存在的，我们需要强制要求其值（ $x$ ）必须为 $0$ ，因此方程的系数 $A$ 和 $b$ 就可以直接转换为增加的 c、d 数组的后两行，这样可以稍微简化一下计算。

总结

本题是一个大型异或方程组的求解的问题，但是由于每个方程组涉及的元素数量极其有限，所以我们能通过基于此的一些快速方法进行远优于 $O(n^3)$ 的复杂度进行消元。

欢迎大家对于上面题解中可能存在的问题提出意见。

数算题解

423 次浏览

No Comments