记 表示 位置格子的颜色。
把 相邻的四个 矩阵拼到一起做差可以得到 。因此容易想到按 的值将整个矩阵划分为 个等价类分别讨论。
对一个等价类而言，其大小必然是长 宽 的矩阵，为了方便后面记 ，改等价类对应的矩阵为 。则此时根据前面的推论可以得到有 。发现这个就是二阶差分的形式，因此 的形态必然要么每一行内所有元素相等，要么每一列内所有元素相等。
这里存在一种特殊情况是 矩阵内所有元素均相等。后面为了方便将这个情况归类为所有行元素相等的情况。
然后考虑对所有等价类做整体计数。
在 基础块中考虑一行一行的计数。假设当前在处理基础块中第 行对答案的贡献。考虑枚举这一行里有 个块是所有行元素相等的块。然后为了满足题目中一开始给出的条件，这 个行元素相同的块每一行的 数组中的和必须相同。算贡献可以再枚举每一行 数组中元素的和为 ，贡献即为 。记这个贡献为 。
然后再考虑列元素相等的块对答案的贡献。和前面行元素相等的部分本质相同，但是需要容斥掉所有元素都相等的情况，钦定有 个位置是所有元素都相同的，然后每个位置要么是全 要么是全 有两种选法，对答案的贡献即为 ，其中 是不管不能所有元素都相等这个条件时的答案，有 。记这个贡献为 。
因此对一个 的基础块，记其第 行中 的个数是 ，第 列中 的个数是 ，答案就是 。直接枚举基础块内每个格子填的是 显然不行，考虑进一步优化。按列做状压 dp，设 表示当前处理到了第 列，当前所有已处理了的列中每一行对应格子的行型格子数量组成的集合为 ，对答案的贡献是多少。 可以直接压成 进制来处理。转移枚举下一行每个格子分别是行型 / 列型然后更新 集合和答案即可。具体细节见代码。
namespace lowspeed_song {
int fac[N], inv[N], ifac[N];
int a[N], f[N], ff[N], cost[N], dlt[N], A[N], B[N];
inline void init() {
fac[0] = inv[0] = ifac[0] = 1;
fac[1] = inv[1] = ifac[1] = 1;
for (int i = 2; i < N; ++i) {
fac[i] = fac[i - 1] * i % mod;
inv[i] = mod - inv[mod % i] * (mod / i) % mod;
ifac[i] = ifac[i - 1] * inv[i] % mod;
}
}
inline int binom(int a, int b) {
if (b < 0 || a < b) return 0;
return fac[a] * ifac[b] % mod * ifac[a - b] % mod;
}
inline void sol() {
int n, m; cin >> n >> m;
int g[8] = {0}, A[8] = {0}, B[8] = {0};
for (int i = 0; i < 8; ++i)
for (int j = 0; j <= i; ++j) A[i] = (A[i] + power(binom(i, j), n / 6, mod)) % mod;
for (int i = 0; i < 7; ++i)
for (int j = 0; j <= i; ++j) g[i] = (g[i] + power(binom(i, j), m / 7, mod)) % mod;
for (int i = 0; i < 7; ++i)
for (int j = 0; j <= i; ++j) {
int now = binom(i, j) * (1 << j) % mod * g[i - j] % mod;
if (j & 1) B[i] = (B[i] + mod - now) % mod;
else B[i] = (B[i] + now) % mod;
}
for (int i = 0; i < 64; ++i) {
cost[i] = B[6 - __builtin_popcount(i)];
for (int j = 0; j < 6; ++j) if (i >> j & 1) dlt[i] += (1 << (j + j + j));
}
f[0] = 1;
for (int i = 0; i < 7; ++i) {
memset(ff, 0, sizeof ff);
for (int j = 0; j < (1 << 18) ;++j)
for (int k = 0; k < (1 << 6); ++k)
ff[j + dlt[k]] = (ff[j + dlt[k]] + f[j] * cost[k] % mod) % mod;
for (int j = 0; j < (1 << 18); ++j) f[j] = ff[j];
}
int ans = 0;
for (int i = 0; i < (1 << 18); ++i) {
int tmp = i, res = f[i];
for (int j = 0; j < 6; ++j) res = res * A[tmp & 7] % mod, tmp >>= 3;
ans = (ans + res) % mod;
}
cout << ans << '\n';
}
} // namespace lowspeed_song
喜欢的话，留下你的评论吧～