正睿 NOIP2023 20连 Day1 T2 题解

Description

有一面由 $n\times m$ 个格子组成的墙，每个格子要么是黑色，要么是白色。你每次将会进行这样的操作：等概率随机选择一个位置 $(x,y)$，和一个颜色 $c$（黑色或者白色），（$1 \leq x \leq n, 1 \leq y \leq m$, 任意 $(x,y,c)$ 的组合选择它的概率均为 $\frac {1} {2\times n\times m}$），然后将在 $(x,y)$ 左上角的所有格子的颜色涂成 $c$。

即将所有满足 $1 \leq x' \leq x, 1 \leq y' \leq y$ 的 $(x',y')$ 格子上的颜色涂成 $c$。

这次操作的代价为涂的格子的数量，即 $x\times y$。给定初始状态和终止状态，问期望要花费多少代价才能将墙面从初始状态涂成终止状态。

$n,m\leq 5$，对 $998244353$ 取模。

Solution

首先有个显然的想法就是对所有的状态直接状压然后高斯消元解方程。

但是这样做时间复杂度是 $O(2^{3nm})$，过不了。

---

考虑优化这个状压方式，即找到一种等价类，使得同一等价类会转移到同一个等价类。

注意到如果一个点右下方有一个初始状态与结束状态不同，那么这个点当前的状态就没用了，因为右上方的一定会覆盖它。

设 $p_{i,j}$ 表示 $(i,j)$ 右下方是否全部满足当前状态 $=$ 结束状态。

容易发现 $p$ 值为 $1$ 的一定是一个在右下角的阶梯，那么状态数总共就只有 $C_{n+m}^{n}$ 了。

然后考虑转移，假设是操作 $(x,y,c)$，那么不在操作区域内的 $p$ 值一定不变。

对于一个 $(i,j)$ 满足 $1\leq i\leq x,1\leq j\leq y$，$p_{i,j}$ 操作后为 $1$ 当且仅当 $(i,j)-(x,y)$ 这个矩形的最终状态全为 $c$ 并且 $p_{x+1,j}$ 和 $p_{i,y+1}$ 都为 $1$。

容易发现这样做是对的。

然后对这个状态做高斯消元即可。

时间复杂度：$O\left((C_{n+m}^{n}) ^3\right)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxS = 505, kMod = 998244353;

int n, m, tot;
int a[10][10], b[10][10], pp[kMaxS][10], idx[kMaxS], w[kMaxS][kMaxS], res[kMaxS];
std::unordered_map<int, int> mp;

int fix(int x) { return (x % kMod + kMod) % kMod; }
int add(int x, int y) { return (x + y) >= kMod ? (x + y - kMod) : (x + y); }
int sub(int x, int y) { return (x - y) < 0 ? (x - y + kMod) : (x - y); }
void inc(int &x, int y) { (x += y) >= kMod ? (x -= kMod) : x; }
void dec(int &x, int y) { (x -= y) < 0 ? (x += kMod) : x; }

int qpow(int bs, int idx = kMod - 2) {
  int ret = 1;
  for (; idx; idx >>= 1, bs = 1ll * bs * bs % kMod)
    if (idx & 1) ret = 1ll * ret * bs % kMod;
  return ret;
}

int gethash(int *p) {
  int ret = 0;
  for (int i = 1; i <= n; ++i) ret = ret * (m + 1) + p[i];
  return ret;
}

void dfs(int x) {
  static int p[10] = {0};
  if (x == n + 1) {
    int val = gethash(p);
    mp[val] = ++tot;
    idx[tot] = val;
    return;
  }
  for (int i = p[x - 1]; i <= m; ++i) {
    p[x] = i;
    dfs(x + 1);
  }
}

int getstate(int a[10][10]) {
  static int p[10];
  for (int i = n; i; --i) {
    p[i] = 0;
    for (int j = m; j; --j) {
      if (a[i][j] == b[i][j]) {
        p[i] = m - j + 1;
      } else {
        break;
      }
    }
    if (i < n) p[i] = std::min(p[i], p[i + 1]);
  }
  return mp[gethash(p)];
}

int work(int s, int x, int y, int c) {
  static int p[10], pp[10][10];
  s = idx[s];
  for (int i = n; i; --i) {
    p[i] = s % (m + 1);
    s /= (m + 1);
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = m; j >= m - p[i] + 1; --j) pp[i][j] = 1;
    for (int j = 1; j <= m - p[i]; ++j) pp[i][j] = 0;
  }
  for (int i = 1; i <= x; ++i) {
    for (int j = 1; j <= y; ++j) {
      bool fl = 1;
      if (x < n) fl &= pp[x + 1][j];
      if (y < m) fl &= pp[i][y + 1];
      for (int xx = i; xx <= x; ++xx)
        for (int yy = j; yy <= y; ++yy)
          fl &= (b[xx][yy] == c);
      pp[i][j] = fl;
    }
  }
  for (int i = n; i; --i) {
    p[i] = 0;
    for (int j = m; j; --j) {
      if (pp[i][j]) {
        p[i] = m - j + 1;
      } else {
        break;
      }
    }
    if (i < n) p[i] = std::min(p[i], p[i + 1]);
  }
  return mp[gethash(p)];
}

void gauss() {
  for (int i = 1; i <= tot; ++i) {
    if (!w[i][i]) {
      for (int j = i + 1; j <= tot; ++j) {
        if (w[j][i]) {
          std::swap(w[i], w[j]);
          break;
        }
      }
    }
    for (int j = i + 1; j <= tot; ++j) {
      int val = 1ll * w[j][i] * qpow(w[i][i]) % kMod;
      dec(w[j][0], 1ll * w[i][0] * val % kMod);
      for (int k = i; k <= tot; ++k)
        dec(w[j][k], 1ll * w[i][k] * val % kMod);
    }
  }
  for (int i = tot; i; --i) {
    for (int j = i + 1; j <= tot; ++j) {
      dec(w[i][0], 1ll * res[j] * w[i][j] % kMod);
    }
    res[i] = 1ll * w[i][0] * qpow(w[i][i]) % kMod;
  }
}

void dickdreamer() {
  std::cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    std::string s;
    std::cin >> s;
    for (int j = 1; j <= m; ++j)
      a[i][j] = (s[j - 1] == 'B');
  }
  for (int i = 1; i <= n; ++i) {
    std::string s;
    std::cin >> s;
    for (int j = 1; j <= m; ++j)
      b[i][j] = (s[j - 1] == 'B');
  }
  dfs(1);
  int iv = qpow(2 * n * m);
  for (int i = 1; i <= tot; ++i) {
    if (i == tot) {
      w[i][i] = 1;
    } else {
      w[i][i] = 1;
      for (int x = 1; x <= n; ++x) {
        for (int y = 1; y <= m; ++y) {
          for (int c = 0; c <= 1; ++c) {
            int j = work(i, x, y, c);
            dec(w[i][j], iv);
            inc(w[i][0], 1ll * x * y * iv % kMod);
          }
        }
      }
    }
  }
  gauss();
  std::cout << res[getstate(a)] << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}