P10085 题解
bmatrix
·
·
题解
题面。
下文用 $\oplus$ 表示异或运算，加减运算均在模 $2^n$ 意义下进行。
设 $x_{i,j}$ 表示坐标为 $(i,j)$ 的格子是否进行操作，不难发现，题目就是给定了若干个限制：$x_{i,j}\oplus x_{i-1,j}\oplus x_{i+1,j}\oplus x_{i,j-1}\oplus x_{i,j+1}=a_{i,j}$。共 $2^{2n}$ 个变量，$2^{2n}$ 个方程，高斯消元即可拿到 35 分。
事实上，当我们知道第 $i$ 行和第 $i-1$ 行的所有 $x$ 时，我们可以直接推导出第 $i+1$ 行的 $x$，不需要高斯消元。
因此考虑只设出前两行共 $2^{n+1}$ 个变量，逐行推导，用这些变量表示出最后两行，然后用最后两行与前两行形成方程，进行高斯消元。
用 bitset 优化，时间复杂度 $\Theta\left(\dfrac{2^{3n+3}}w\right)$，大数据点需要对 $4096$ 个元素进行高斯消元。但由于 bitset 伟大的小常数，卡卡常就能跑进 1s。
卡常小寄巧：
1. 本题输入输出量大，建议使用 `fread` 和 `fwrite` 加速。
2. 滚动数组不用拷贝或清空，直接原地异或即可。
3. 不要写 `a ^= b ^ c ^d;`，写 `a ^= b, a ^= c, a ^= d;`，前者需要存中间值，常数大。
```cpp
constexpr int N = 1 << 11;
int n, a[N][N], ans[N][N];
bitset<N * 2 + 1> bs[N * 2];
signed main() {
cin >> n;
n = 1 << n;
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
cin >> a[i][j];
for(int i = 0; i < n * 2; ++i)
bs[i][i] = 1;
for(int i = 2; i < n; ++i) {
int x = i & 1, y = x ^ 1;
for(int j = 0; j < n; ++j) {
bs[x * n + j] ^= bs[y * n + j],
bs[x * n + j] ^= bs[y * n + (j - 1 + n) % n],
bs[x * n + j] ^= bs[y * n + (j + 1) % n];
if(a[i - 1][j]) bs[x * n + j].flip(n * 2);
}
}
for(int j = 0; j < n; ++j) {
bs[j] ^= bs[n + j];
bs[j] ^= bs[n + (j - 1 + n) % n];
bs[j] ^= bs[n + (j + 1) % n];
bs[j].flip(j);
if(a[n - 1][j]) bs[j].flip(n * 2);
}
for(int j = 0; j < n; ++j) {
bs[n + j].flip(j), bs[n + j].flip(n + j), bs[n + j].flip((j - 1 + n) % n), bs[n + j].flip((j + 1) % n);
if(a[0][j]) bs[n + j].flip(n * 2);
}
// cerr << clock() / 1e3 << endl;
for(int i = 0; i < n * 2; ++i) {
for(int j = i; j < n * 2; ++j) {
if(bs[j][i]) {
if(j != i) swap(bs[j], bs[i]);
break;
}
}
for(int j = 0; j < n * 2; ++j)
if(j != i && bs[j][i]) bs[j] ^= bs[i];
}
// cerr << clock() / 1e3 << endl;
int cnt = 0;
for(int i = 0; i < n * 2; ++i) {
ans[i / n][i % n] = bs[i][n * 2];
if(ans[i / n][i % n]) ++cnt;
}
for(int i = 2; i < n; ++i)
for(int j = 0; j < n; ++j) {
ans[i][j] = ans[i - 1][j] ^ ans[i - 2][j] ^ ans[i - 1][(j - 1 + n) % n] ^ ans[i - 1][(j + 1) % n] ^ a[i - 1][j];
if(ans[i][j]) ++cnt;
}
// cerr << clock() / 1e3 << endl;
cout << cnt << endl;
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
if(ans[i][j]) cout << i << ' ' << j << endl;
return 0;
}
```