← 返回题目列表

AtCoder · abc334_g

G. 圣诞彩格2

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

配点 : 650 点

問題文

这个问题与问题E的设定相似。问题文中不同的地方用红字标出。

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

从网格的上方 i 第几行,从左边 j 第几列的格子记作格子 (i,j) 表示。

马斯 (i,j) 颜色用文字表示 S_{i,j} 表示,S_{i,j} = . 当时格子 (i,j) 被涂成红色,S_{i,j} = # 当时格子 (i,j) 被涂成绿色。

在网格中,将绿色涂画的格子作为边界集合,将相邻的绿色格子之间的所有边作为边集合所构成的图中的连通分支的数量称为 2 绿色连通分支数。 但是, 两个格子2 相邻是指 (x,y) 和 我讨厌 (x',y') 的情况。|x-x'| + |y-y'| = 1 从涂有的格子中均匀随机选择

緑色个, 1 改为涂上赤色后,请将涂色后网格的绿色连通分支数的期望值 \text{mod } 998244353 输出。

“输出期望值” \text{mod } 998244353 的意思是 所求的期望值可以证明一定是有理数。 此外,在该问题的否定情况下,可用互质的 2 整数 P, Q 表示该值。 \frac{P}{Q} 时,满足 R \times Q \equiv P\pmod{998244353} 和 0 \leq R \lt 998244353 的整数只有 R 仅仅是 1 可以证明存在。 R 请输出这个。