题解 P2225 【[HNOI2001]棋盘变换】

· · 题解

前言

今天下午同学 YLWang 突然告诉我有这样一个帖子，于是思考了一下此题不打表的做法，就有了这篇题解。

前置知识：高斯消元，burnside 引理

我们将 1 看成 (-1)^0 ， -1 看成 (-1)^1 ，我们求两个数的乘积就可以变成幂次相加的性质，又因为有 (-1)^2 = (-1)^0 ，所以我们的幂次相加是在 \mod 2 意义下进行的，容易发现这就是异或，我们可以将题目转换为在每个位置上填上 0/1 ，使得每个数等于相邻的四个数的异或和，求本质不同的方案数。

如果不用考虑本质不同的限制，我们可以对于每个位置 (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} = 0 ，其中 \oplus 是异或，我们求出这个方程组的解的个数就行了，方程组解的个数是 2 的方程组自由元个数次幂，可以用高斯消元 O(n^6) 求出，由于是用高斯消元求解异或方程组，可以用 bitset 将复杂度优化至 O(\frac{n^6}{w}) 。

如果要求本质不同的方案数，我们可以用 burnside 引理来解决，容易发现只有翻转和旋转的置换群大小是常数级别的（小于等于 8 ），我们对于每种置换群把不动点压成一个变量，求一下方案数即可。

复杂度 O(\frac{n^6}{w}) ，实际上 n=100 也能在 1 秒之内跑出解。

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
using namespace std;

typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef long long ll;

template <typename _T>
inline void read(_T &f) {
    f = 0; _T fu = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') { fu = -1; } c = getchar(); }
    while (c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); }
    f *= fu;
}

template <typename T>
void print(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x < 10) putchar(x + 48);
    else print(x / 10), putchar(x % 10 + 48);
}

template <typename T>
void print(T x, char t) {
    print(x); putchar(t);
}

const int N = 35;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

bitset <N * N> mat[N * N];

int gauss(int n, int m) {
    int ans = 1;
    for (int i = 1; i <= m; i++) {
        int id = 0;
        for (int j = i; j <= n; j++) {
            if (mat[j][i] == 1) {
                id = j;
                break;
            }
        }
        if (!id) {
            ans <<= 1;
            continue;
        }
        if (id != i) swap(mat[i], mat[id]);
        for (int j = i + 1; j <= n; j++) {
            if (mat[j][i]) {
                mat[j] ^= mat[i];
            }
        }
    }
    return ans;
}

int go[N * N], used[N * N], id[N * N];
int n, len, tot, ans;

struct Matrix { int a[N][N]; };

bool operator < (const Matrix a, const Matrix b) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (a.a[i][j] != b.a[i][j]) {
                return a.a[i][j] < b.a[i][j];
            }
        }
    }
    return 0;
}

set <Matrix> states;
set <Matrix> :: iterator it;
queue <Matrix> q;

Matrix rotate(Matrix a) {
    Matrix ans;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            ans.a[j][n - i + 1] = a.a[i][j];
        }
    }
    return ans;
}

Matrix flip(Matrix a) {
    Matrix ans;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            ans.a[n - i + 1][j] = a.a[i][j];
        }
    }
    return ans;
}

inline int calc(int x, int y) {
    return (x - 1) * n + y;
}

int main() {
    read(n);
    Matrix a;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            a.a[i][j] = calc(i, j);
        }
    }
    states.insert(a); q.push(a);
    while (!q.empty()) {
        Matrix u = q.front(), v; q.pop();
        v = rotate(u);
        if (!states.count(v)) {
            states.insert(v);
            q.push(v);
        }
        v = flip(u);
        if (!states.count(v)) {
            states.insert(v);
            q.push(v);
        }
    }
    for (it = states.begin(); it != states.end(); ++it) {
        Matrix u = *it;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                go[u.a[i][j]] = calc(i, j);
            }
        }
        memset(used, 0, sizeof(used)); tot = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                int now = calc(i, j);
                if (!used[now]) {
                    ++tot;
                    while (!used[now]) {
                        used[now] = 1;
                        id[now] = tot;
                        now = go[now];
                    }
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                int now = calc(i, j);
                mat[now].reset(); mat[now][id[now]] = 1;
                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x <= 0 || y <= 0 || x > n || y > n) continue;
                    int v = id[calc(x, y)];
                    mat[now][v] = 1 - mat[now][v];
                }
            }
        }
        ans += gauss(n * n, tot);
    }
    ans /= (int)states.size();
    print(ans, '\n');
    return 0;
}

upd：可以将此做法优化至 O(\frac{n^4}{w}) ，感谢 @142857cs 的提点

我们只把第一行设为未知数，剩下的格子可以通过第一行表示出来，这样就只有 n^2 个方程和 n 个系数了

code