AT_abc334_g [ABC334G] Christmas Color Grid 2

[problemUrl]: https://atcoder.jp/contests/abc334/tasks/abc334_g **本题与问题 E 的设定类似。与问题 E 的不同之处已用红色字体标出。** 有一个 $H$ 行 $W$ 列的网格，每个格子被涂成红色或绿色。 网格中从上往下第 $i$ 行，从左往右第 $j$ 列的格子记作格子 $(i,j)$。 格子 $(i,j)$ 的颜色用字符 $S_{i,j}$ 表示，若 $S_{i,j} = \texttt{.}$，则格子 $(i,j)$ 被涂为红色；若 $S_{i,j} = \texttt{\#}$，则格子 $(i,j)$ 被涂为绿色。 在网格中，将所有被涂为绿色的格子作为顶点集合，将所有相邻的两个绿色格子之间连一条边，构成一个图。该图的连通分量个数称为**绿色连通分量数**。这里，两个格子 $(x,y)$ 和 $(x',y')$ 相邻，指的是 $|x-x'| + |y-y'| = 1$。 **随机等概率选择一个绿色格子，将其重新涂为红色后，网格中的绿色连通分量数的期望值是多少？请将答案对 $998244353$ 取模后输出。** “将期望值对 $998244353$ 取模后输出”是指，所求的期望值一定是有理数。在本题的约束下，设其值可表示为互质的两个整数 $P, Q$ 的分数 $\frac{P}{Q}$，则一定存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \leq R < 998244353$。请输出这个 $R$。

输入按以下格式从标准输入读入。 > $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}$

请输出答案。

### 约束条件 - $1 \leq H, W \leq 1000$ - $S_{i,j} = \texttt{.}$ 或 $S_{i,j} = \texttt{\#}$ - 至少存在一个 $(i,j)$ 使得 $S_{i,j} = \texttt{\#}$ ### 样例解释 1 将格子 $(1,1)$ 涂为红色后，绿色连通分量数为 $3$。 将格子 $(1,2)$ 涂为红色后，绿色连通分量数为 $2$。 将格子 $(2,1)$ 涂为红色后，绿色连通分量数为 $3$。 将格子 $(2,3)$ 涂为红色后，绿色连通分量数为 $1$。 将格子 $(3,1)$ 涂为红色后，绿色连通分量数为 $2$。 因此，随机等概率选择一个绿色格子，将其涂为红色后，绿色连通分量数的期望值为 $(3+2+3+1+2)/5 = 11/5$。 由 ChatGPT 4.1 翻译