← 返回题目列表

AtCoder · abc334_e

H. 圣诞色网格1

中文机器翻译题面 查看原题

分数: 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