满分解法（100 分）

先数出所有染色方案

用 $b_i\in\{1,2,3\}$ 表示第 $i$ 列黑格所在的行。第一列有 $3$ 种选择；确定 $b_i$ 后，$b_{i+1}$ 可以选择另外两行中的任意一行。因此合法染色方案数为

下面统计所有方案的最大白色连通块大小之和，最后乘以 $W$ 在模 $998244353$ 下的逆元。

只保留仍接触右边界的连通块

按列从左到右加入网格。一个白色连通块如果已经不与当前列相交，它与以后加入的列之间至少隔着一整列。网格中的边只连接同列或相邻列的格子，因此这个连通块以后不可能再扩大或与别的块合并。我们只需把它的大小纳入“此前出现过的最大值”，不必继续保存它的形状。

每列只有两个白格，所以与当前列相交的部分只有两类：

• 当前列黑格在第一行或第三行。两个白格竖直相邻，属于同一个活动连通块，记为类型 $A$。
• 当前列黑格在第二行。顶部和底部白格不相邻，形成两个活动连通块，记为类型 $B$。

类型 $B$ 看似需要保存两个块的大小，实际上其中一个块一定只有一个格子。因为前一列黑格不能也在第二行，只能在外层行；前一列的两个白格属于同一个块，并且只会与当前列顶部、底部中的一侧通过水平边连接。另一侧没有白色左邻格，只是本列新产生的单点。

于是定义：

• $A_i(s,m)$：前 $i$ 列形成的方案中，第 $i$ 列黑格在外层行，当前活动块大小为 $s$，到目前为止所有连通块的最大大小为 $m$ 的方案数。上下两种对称方向合并计数。
• $B_i(s,m)$：第 $i$ 列黑格在第二行，两个活动块的大小分别为 $s$ 和 $1$，历史最大大小为 $m$ 的方案数。

这里的 $m$ 也包含尚未封闭的活动块。这样某个活动块以后封闭时，不需要再补记它的大小。

初始化与转移

只有第一列时，黑格在两个外层行各产生一个大小为 $2$ 的白色连通块；黑格在第二行时产生两个单点。因此

考虑一个 $A_i(s,m)$ 状态。当前黑格位于某个外层行，下一列的黑格有两个合法位置：

1. 若移动到另一侧外层行，新列的两个白格竖直相连，并且都并入原活动块。新块大小为 $s+2$：

   $$A_{i+1}(s+2,\max(m,s+2))\mathrel{+}=A_i(s,m).$$

2. 若移动到第二行，原活动块只接到一侧白格，另一侧白格成为单点。非平凡活动块大小为 $s+1$：

   $$B_{i+1}(s+1,\max(m,s+1))\mathrel{+}=A_i(s,m).$$

再考虑 $B_i(s,m)$。下一列黑格只能在两个外层行中选择：

1. 一个选择使大小为 $s$ 的活动块接上新列的两个白格，得到大小 $s+2$ 的块：

   $$A_{i+1}(s+2,\max(m,s+2))\mathrel{+}=B_i(s,m).$$

2. 另一个选择使大小为 $s$ 的活动块封闭，而原来的单点接上新列的两个白格，成为大小为 $3$ 的块：

   $$A_{i+1}(3,\max(m,3))\mathrel{+}=B_i(s,m).$$

当 $s=1$ 时，这两个选择会落入同一个 $A_{i+1}(3,\max(m,3))$，但它们对应黑格位于不同外层行的两个染色方案，所以仍要执行两次加法。这个处理也说明了为什么合并上下对称方向不会丢失方案数。

例如从 $A_i(5,7)$ 出发，外层到外层得到 $A_{i+1}(7,7)$，外层到中间得到 $B_{i+1}(6,7)$。从 $B_i(6,7)$ 出发，延伸大块得到 $A_{i+1}(8,8)$；延伸单点则让大小为 $6$ 的块封闭，得到 $A_{i+1}(3,7)$。

所有方案数都对 $998244353$ 取模。

计算期望

处理完第 $n$ 列后，每个状态中的 $m$ 已经是对应方案的最大白色连通块大小。令

则所求答案为

状态中的 $s,m$ 都不超过白格总数 $2n$。每一层最多有 $O(n^2)$ 个状态，每个状态只有常数次转移，因此时间复杂度为 $O(n^3)$，空间复杂度为 $O(n^2)$。代码用稠密编号保存计数，同时只遍历本层实际出现的状态，以降低常数。

AC 代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

const int mod = 998244353;

int power(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = 1LL * ans * a % mod;
    a = 1LL * a * a % mod;
    b >>= 1;
  }
  return ans;
}

void solve() {
  int n;
  cin >> n;

  int w = 2 * n + 3;
  int states = w * w;
  vector<int> dp[2][2], used[2][2], tag[2][2];
  for (int p = 0; p < 2; ++p) {
    for (int type = 0; type < 2; ++type) {
      dp[p][type].resize(states);
      tag[p][type].resize(states);
    }
  }

  int first = 1;
  int joined = 2 * w + 2;
  int split = w + 1;
  dp[first][0][joined] = 2;
  dp[first][1][split] = 1;
  tag[first][0][joined] = 1;
  tag[first][1][split] = 1;
  used[first][0].push_back(joined);
  used[first][1].push_back(split);

  auto add = [&](int p, int type, int id, int value, int stamp) {
    if (tag[p][type][id] != stamp) {
      tag[p][type][id] = stamp;
      dp[p][type][id] = 0;
      used[p][type].push_back(id);
    }
    dp[p][type][id] += value;
    if (dp[p][type][id] >= mod) dp[p][type][id] -= mod;
  };

  for (int col = 2; col <= n; ++col) {
    int p = (col - 1) & 1;
    int q = col & 1;
    used[q][0].clear();
    used[q][1].clear();

    for (int id : used[p][0]) {
      int value = dp[p][0][id];
      if (value == 0) continue;
      int s = id / w;
      int best = id % w;
      int next_s = s + 2;
      add(q, 0, next_s * w + max(best, next_s), value, col);
      next_s = s + 1;
      add(q, 1, next_s * w + max(best, next_s), value, col);
    }
    for (int id : used[p][1]) {
      int value = dp[p][1][id];
      if (value == 0) continue;
      int s = id / w;
      int best = id % w;
      int next_s = s + 2;
      add(q, 0, next_s * w + max(best, next_s), value, col);
      add(q, 0, 3 * w + max(best, 3), value, col);
    }
  }

  int p = n & 1;
  int sum = 0;
  for (int type = 0; type < 2; ++type) {
    for (int id : used[p][type]) {
      sum = (sum + 1LL * (id % w) * dp[p][type][id]) % mod;
    }
  }
  int ways = 3LL * power(2, n - 1) % mod;
  cout << 1LL * sum * power(ways, mod - 2) % mod << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

保留行方向的映射动态规划（通过子任务 1–12，共 60 分）

在 $n\le 100$ 时，可以使用更直接的前沿动态规划，不合并上下对称方向，并用有序映射只保存可达状态。

从左向右加入列。状态记录四个量：当前黑格所在行 $r$，活动连通块大小 $x,y$，以及此前出现过的最大块大小 $m$。若 $r$ 是外层行，当前两个白格相连，用 $x$ 保存这一块的大小并令 $y=0$；若 $r$ 是中间行，则 $x,y$ 分别表示顶部和底部活动块的大小。已经离开当前列的块不会再与未来相连，其影响保存在 $m$ 中。

初始有三个状态：黑格在顶部或底部时 $x=2,m=2$，黑格在中间时 $x=y=m=1$。转移直接按下一列黑格的位置合并白格：

• 当前黑格在顶部时，下一列黑格在中间会得到顶部单点和大小 $x+1$ 的底部块；下一列黑格在底部会把两个新白格并入原块，得到大小 $x+2$ 的相连块。
• 当前黑格在底部时完全对称。
• 当前黑格在中间时，下一列黑格在顶部会让底部块扩成 $y+2$，顶部块封闭；下一列黑格在底部则让顶部块扩成 $x+2$，底部块封闭。

每次用新活动块的大小更新 $m$，并把方案数加入对应的新状态。处理完全部列后按方案数加权累加 $m$，再除以 $3\cdot2^{n-1}$。

每层有 $O(n^2)$ 个可达状态，有序映射操作为 $O(\log n)$ 量级，因此时间复杂度为 $O(n^3\log n)$，空间复杂度为 $O(n^2)$。该写法概念直接，但红黑树状态维护的常数较大，适合 $n\le100$ 的测试点。

参考代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

const int mod = 998244353;

int power(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = 1LL * ans * a % mod;
    a = 1LL * a * a % mod;
    b >>= 1;
  }
  return ans;
}

void solve() {
  int n;
  cin >> n;
  map<array<int, 4>, int> dp, ndp;
  dp[{0, 2, 0, 2}] = 1;
  dp[{1, 1, 1, 1}] = 1;
  dp[{2, 2, 0, 2}] = 1;

  auto add = [&](array<int, 4> state, int value) {
    int &current = ndp[state];
    current += value;
    if (current >= mod) current -= mod;
  };

  for (int col = 2; col <= n; ++col) {
    ndp.clear();
    for (auto [state, value] : dp) {
      auto [black, x, y, best] = state;
      if (black == 0) {
        add({1, 1, x + 1, max(best, x + 1)}, value);
        add({2, x + 2, 0, max(best, x + 2)}, value);
      } else if (black == 2) {
        add({0, x + 2, 0, max(best, x + 2)}, value);
        add({1, x + 1, 1, max(best, x + 1)}, value);
      } else {
        add({0, y + 2, 0, max(best, y + 2)}, value);
        add({2, x + 2, 0, max(best, x + 2)}, value);
      }
    }
    dp.swap(ndp);
  }

  int sum = 0;
  for (auto [state, value] : dp) {
    sum = (sum + 1LL * state[3] * value) % mod;
  }
  int ways = 3LL * power(2, n - 1) % mod;
  cout << 1LL * sum * power(ways, mod - 2) % mod << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

枚举染色并维护连通块（通过子任务 1–8，共 40 分）

在 $n\le 20$ 时，可以直接枚举每一列黑格所在的行。第一列有 $3$ 种选择，以后每列都选择与上一列不同的两行之一，共有 $3\cdot 2^{n-1}$ 种方案。

为了在枚举过程中得到最大白色连通块，不必在每个叶子重新扫描整个网格。按列递归加入格子：激活当前列的两个白格，合并同列竖直相邻的白格，再与上一列同行的白格合并。并查集同时维护当前最大的集合大小。

递归一个分支前记录修改栈的长度，返回时撤销此后发生的激活和合并。并查集按大小合并且不做路径压缩，所以每次修改都能恢复；撤销后恰好回到加入本列之前的连通状态。到达第 $n$ 列后，当前最大集合大小就是这一染色方案的 $X$，将它加入总和。

最后用最大块大小总和除以方案数，模意义下乘方案数的逆元即可。时间复杂度为 $O(2^n\log n)$，空间复杂度为 $O(n)$。

参考代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

const int mod = 998244353;

int power(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = 1LL * ans * a % mod;
    a = 1LL * a * a % mod;
    b >>= 1;
  }
  return ans;
}

struct RollbackDsu {
  struct Change {
    int kind;
    int a;
    int b;
    int old_size;
    int old_best;
  };

  vector<int> parent, size;
  vector<Change> history;
  int best = 0;

  explicit RollbackDsu(int n) : parent(n, -1), size(n) {}

  int find(int x) {
    while (parent[x] != x) x = parent[x];
    return x;
  }

  void add(int x) {
    history.push_back({0, x, -1, 0, best});
    parent[x] = x;
    size[x] = 1;
    best = max(best, 1);
  }

  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (size[x] < size[y]) swap(x, y);
    history.push_back({1, x, y, size[x], best});
    parent[y] = x;
    size[x] += size[y];
    best = max(best, size[x]);
  }

  void rollback(int snapshot) {
    while ((int)history.size() > snapshot) {
      Change change = history.back();
      history.pop_back();
      best = change.old_best;
      if (change.kind == 0) {
        parent[change.a] = -1;
        size[change.a] = 0;
      } else {
        parent[change.b] = change.b;
        size[change.a] = change.old_size;
      }
    }
  }
};

void solve() {
  int n;
  cin >> n;
  RollbackDsu dsu(3 * n);
  i64 sum = 0;
  i64 ways = 0;

  auto dfs = [&](auto &&self, int col, int last_black) -> void {
    if (col == n) {
      sum += dsu.best;
      ++ways;
      return;
    }
    for (int black = 0; black < 3; ++black) {
      if (black == last_black) continue;
      int snapshot = dsu.history.size();
      for (int row = 0; row < 3; ++row) {
        if (row != black) dsu.add(3 * col + row);
      }
      for (int row = 0; row + 1 < 3; ++row) {
        if (row != black && row + 1 != black) {
          dsu.unite(3 * col + row, 3 * col + row + 1);
        }
      }
      if (col > 0) {
        for (int row = 0; row < 3; ++row) {
          int cur = 3 * col + row;
          int pre = cur - 3;
          if (dsu.parent[cur] != -1 && dsu.parent[pre] != -1) {
            dsu.unite(cur, pre);
          }
        }
      }
      self(self, col + 1, black);
      dsu.rollback(snapshot);
    }
  };

  dfs(dfs, 0, -1);
  cout << sum % mod * power(ways % mod, mod - 2) % mod << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}