LambdaOJ:十字刷子 解题报告

LambdaOJ:十字刷子 解题报告

Contents

主要题面

image-20201124200809300

image-20201124200818262

简单分析

对于题目给出的 $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 数组实际上就是我们想要的解。

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

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

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

总结

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

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

 

点赞 5

No Comments

Add your comment