# LambdaOJ：十字刷子 解题报告

## LambdaOJ：十字刷子 解题报告

Contents

### 简单分析

$$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}$$

### 尝试优化？

$$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}$$

$$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}$$

$$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}$$

$$\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}$$

### 代码实现？

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


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];
}


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];
}


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];
}