Christmas Color Grid 2

题目描述

这个问题与问题 E 的设定相似。问题陈述中的差异以红色标出。 有一个 $H$ 行 $W$ 列的网格，每个格子被涂成红色或绿色。 令 $(i,j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的格子。 格子 $(i,j)$ 的颜色由字符 $S_{i,j}$ 表示，其中 $S_{i,j} =$ $.$ 表示格子 $(i,j)$ 为红色，且 $S_{i,j} =$ # 表示格子 $(i,j)$ 为绿色。 网格中绿色连通分量的数量是指在图中绿色格子为顶点集合、边集为连接两个相邻绿色格子的边时的连通分量个数。这里，当 $|x-x'| + |y-y'| = 1$ 时，认为格子 $(x,y)$ 和 $(x',y')$ 是相邻的。 考虑以均匀随机的方式选择一个绿色格子并将其重新涂成红色。打印在重新涂色后网格中绿色连通分量数量的期望值，对 $998244353$ 取模。

输入格式

输入由标准输入给出，格式如下： $H$ $W$ $S_{1,1}$$S_{1,2}$$\ldots$$S_{1,W}$ $S_{2,1}$$S_{2,2}$$\ldots$$S_{2,W}$ $\vdots$ $S_{H,1}$$S_{H,2}$$\ldots$$S_{H,W}$

输出格式

输出答案。

3 3
##.
#.#
#..

598946614

4 5
..#..
.###.
#####
..#..

199648872

3 4
#...
.#.#
..##

399297744

提示

$1 \leq H,W \leq 1000$ $S_{i,j} =$ $.$ 或 $S_{i,j} =$ #. 至少存在一个 $(i,j)$ 使得 $S_{i,j} =$ #.如果将格子 $(1,1)$ 重新涂成红色，绿色连通分量的数量变为 $3$。 如果将格子 $(1,2)$ 重新涂成红色，绿色连通分量的数量变为 $2$。 如果将格子 $(2,1)$ 重新涂成红色，绿色连通分量的数量变为 $3$。 如果将格子 $(2,3)$ 重新涂成红色，绿色连通分量的数量变为 $1$。 如果将格子 $(3,1)$ 重新涂成红色，绿色连通分量的数量变为 $2$。 因此，以均匀随机的方式选择一个绿色格子并将其重新涂成红色后，绿色连通分量数量的期望值为 $(3+2+3+1+2)/5 =11/5$.

标签: AtCoder|abc334G

来源

AtCoder|abc334G