分数: 450 点
问题陈述
此问题与问题 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“是什么意思?
可以证明,所求的期望值总是有理数。 此外,这个问题的约束保证如果该值表示为 \frac{P}{Q} 使用两个互质整数 P 和 Q,恰好有一个整数 R 这样 R \times Q \equiv P \pmod{998244353} 和 0 \leq R < 998244353。打印此内容 R.约束
- 1 \leq H,W \leq 1000
- S_{i,j} =
.or S_{i,j} =#. - 至少有一个 (i,j) 这样 S_{i,j} =
..
输入
输入由标准输入按以下格式给出:
H W
S_{1,1}S_{1,2}\ldotsS_{1,W}
S_{2,1}S_{2,2}\ldotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\ldotsS_{H,W}
输出
打印答案。
示例输入 1
3 3 ##. #.# #..
示例输出 1
499122178
如果细胞 (1,3) 被重新漆成绿色,绿色连通分量的数量变成 1.
如果细胞 (2,2) 被重新漆成绿色,绿色连通分量的数量变成 1.
如果细胞 (3,2) 被重新漆成绿色,绿色连通分量的数量变成 2.
如果细胞 (3,3) 被重新漆成绿色,绿色连通分量的数量变成 2.
因此,随机均匀选择一个红色单元格并将其重新涂成绿色后,绿色连通分量的数量的期望值为 (1+1+2+2)/4 = 3/2.
示例输入 2
4 5 ..#.. .###. ##### ..#..
示例输出 2
598946613
示例输入 3
3 4 #... .#.# ..##
示例输出 3
285212675