自动搬运

查看原文

来自洛谷，原作者为

	bmatrix ⁧⁧‭

搬运于2025-08-24 22:54:30，当前版本为作者最后更新于2024-01-22 13:42:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题面。

$\Theta\left(\dfrac{n^3}w\right)$ 过 $4096$，这就是伟大的 bitset 的伟大之处！

下文用 $\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;，前者需要存中间值，常数大。

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