AT_abc334_e [ABC334E] Christmas Color Grid 1

题目描述

本题与问题 G 的设定相似。与问题 G 的不同之处已用红字标出。

有一个 $H$ 行 $W$ 列的网格，每个格子被涂成红色或绿色。

网格中从上到下第 $i$ 行，从左到右第 $j$ 列的格子记作格子 $(i,j)$。

格子 $(i,j)$ 的颜色用字符 $S_{i,j}$ 表示，若 $S_{i,j} = .$，则格子 $(i,j)$ 被涂成红色；若 $S_{i,j} = \#$，则格子 $(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

499122178

输入输出样例 #2

输入 #2

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

输出 #2

598946613

输入输出样例 #3

输入 #3

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

输出 #3

285212675

说明/提示

约束

• $1 \leq H, W \leq 1000$
• $S_{i,j} = .$ 或 $S_{i,j} = \#$
• 存在至少一个 $(i,j)$ 使得 $S_{i,j} = .$

样例解释 1

将格子 $(1,3)$ 涂成绿色后，绿色连通分量数为 $1$。
将格子 $(2,2)$ 涂成绿色后，绿色连通分量数为 $1$。
将格子 $(3,2)$ 涂成绿色后，绿色连通分量数为 $2$。
将格子 $(3,3)$ 涂成绿色后，绿色连通分量数为 $2$。
因此，等概率随机选择一个红色格子并涂成绿色后，绿色连通分量数的期望值为 $(1+1+2+2)/4 = 3/2$。

由 ChatGPT 4.1 翻译