AT_abc334_g [ABC334G] Christmas Color Grid 2

题目描述

本题与问题 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

输入 #1

3 3
##.
#.#
#..

输出 #1

598946614

输入输出样例 #2

输入 #2

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

输出 #2

199648872

输入输出样例 #3

输入 #3

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

输出 #3

399297744

说明/提示

约束条件

• $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 翻译