题解

我们考虑忽略平移对这道题目的影响，毕竟我们对于旋转翻转之类的比较了解，于是我们思考设立一个状态状态来包含所有置换 于是我们设： $F$ $u-v$表示$u$行$v$列的矩阵中，在其每条边上都至少有一个格子被染色，其本质不同的染色方案数。 因为每条边上都有染色的格子，所以无论向哪个方向平移，都会有染色的格子移出矩阵，所以无法进行平移操作的，那么只需要考虑翻转和旋转了。

$G0uv$:表示每条边上都至少有一个格子被染色的$u$行$v$列的矩阵，总的染色方案数。

$G1uv$:表示每条边上都至少有一个格子被染色的$u$行$v$列的矩阵，其通过旋转$180$度保持不变的染色方案数。

$G2uv$:表示每条边上都至少有一个格子被染色的$u$行$u$列的矩阵，其通过旋转$90$度或$270$度保持不变的染色方案数。

$G3uv$:表示每条边上都至少有一个格子被染色的$u$行$v$列的矩阵，其通过上下翻转保持不变的染色方案数。

$G4uv$:表示每条边上都至少有一个格子被染色的$u$行$v$列的矩阵，其通过左右翻转保持不变的染色方案数。

$G5uv$:表示每条边上都至少有一个格子被染色的$u$行$u$列的矩阵，其通过沿某条对角线翻转保持不变的染色方案数。

求得所有的$G$值，$F$值就只需套用引理即可。而的求法也都大同小异。

求法：

容斥原理！！！

标程

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
#define ll long long 

using namespace std;

ll ans;
int n, m;

// 读取整数的函数
int read() {
    int x = 0, f = 1;
    char ch;
    while ((ch = getchar()) < '0' || ch > '9') {
        if (ch == '-') f = -1;
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

// 快速幂函数
ll ksm(ll x, int k) {
    ll res = 1;
    for (int i = k; i; i >>= 1, x *= x) {
        if (i & 1) res *= x;
    }
    return res;
}

// 手动实现 ceil 函数
int my_ceil(int a, int b) {
    return (a + b - 1) / b;
}

// 各种计算函数
ll get0(int u, int v) {
    ll res = 0;
    res = ksm(2, u * v)
        - ksm(2, (u - 1) * v) * 2 - ksm(2, u * (v - 1)) * 2
        + ksm(2, (u - 1) * (v - 1)) * 4 + ksm(2, (u - 2) * v) + ksm(2, u * (v - 2))
        - ksm(2, (u - 2) * (v - 1)) * 2 - ksm(2, (u - 1) * (v - 2)) * 2
        + ksm(2, (u - 2) * (v - 2));
    return res;
}

ll get1(int u, int v) {
    ll res = 0;
    res = ksm(2, my_ceil(u * v, 2))
        - ksm(2, my_ceil(u * v, 2) - u) - ksm(2, my_ceil(u * v, 2) - v)
        + ksm(2, my_ceil(u * v, 2) - u - v + 2);
    return res;
}

ll get2(int u, int v) {
    ll res = 0;
    res = ksm(2, my_ceil(u * v, 4)) - ksm(2, my_ceil(u * v, 4) - u + 1);
    return res;
}

ll get3(int u, int v) {
    ll res = 0;
    res = ksm(2, my_ceil(u, 2) * v)
        - ksm(2, my_ceil(u, 2) * (v - 1)) * 2 - ksm(2, (my_ceil(u, 2) - 1) * v)
        + ksm(2, my_ceil(u, 2) * (v - 2)) + ksm(2, (my_ceil(u, 2) - 1) * (v - 1)) * 2
        - ksm(2, (my_ceil(u, 2) - 1) * (v - 2));
    return res;
}

ll get4(int u, int v) {
    ll res = 0;
    res = ksm(2, u * my_ceil(v, 2))
        - ksm(2, (u - 1) * my_ceil(v, 2)) * 2 - ksm(2, u * (my_ceil(v, 2) - 1))
        + ksm(2, (u - 2) * my_ceil(v, 2)) + ksm(2, (u - 1) * (my_ceil(v, 2) - 1)) * 2
        - ksm(2, (u - 2) * (my_ceil(v, 2) - 1));
    return res;
}

ll get5(int u, int v) {
    ll res = 0;
    res = ksm(2, u * (u + 1) / 2) - ksm(2, (u - 1) * u / 2) * 2 + ksm(2, (u - 2) * (u - 1) / 2);
    return res;
}

ll get(int u, int v) {
    ll res = 0;
    if (v == 1) {
        if (u == 1) return 1;
        return (ksm(2, u - 2) + ksm(2, (u + 1) / 2 - 1)) / 2;
    } else {
        if (u == v) {
            res = (get0(u, v) + get1(u, v) + 2 * get2(u, v) + get3(u, v) + get4(u, v) + 2 * get5(u, v));
            return res / 8;
        } else if (u > v) {
            res = (get0(u, v) + get1(u, v) + get3(u, v) + get4(u, v));
            return res / 4;
        }
    }
    return 0;
}

int main() {
    n = read();
    m = read();
    for (int u = 1; u <= max(n, m); u++) {
        for (int v = 1; v <= min(u, min(n, m)); v++) {
            ans += get(u, v);
        }
    }
    printf("%lld\n", ans);
    return 0;
}