wzf2000 LambdaOJ：十字刷子 解题报告
Contents
主要题面
简单分析
对于题目给出的 $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)$ 的复杂度进行消元。
欢迎大家对于上面题解中可能存在的问题提出意见。
No Comments