分数: 600 点
问题陈述
有一个网格 H 行和 W 列,其中每个方格都有一个字符
上面写着 X 和 Y 。
让 (i, j) 表示 i从顶部开始的第行和 j左起第 列。
网格上的字符给出为 H 字符串 S_1, S_2, \dots, S_H: j- 第一个字符 S_i 是方块上的字符 (i, j).
您可以在相邻行和列之间的网格上设置栅栏。 栅栏可能相交。 设置好围栏后, 块 被定义为从某个方格重复向上、向下、向左或向右移动到相邻方格而不跨越栅栏可到达的方格集合。 (另请参见示例输出 1。)
有 2^{H-1} \times 2^{W-1} 设置围栏的方法。其中有多少满足以下条件,取模 998244353?
条件: 每个块正好有两个正方形 Y 。
约束
- 1 \leq H \leq 2000
- 1 \leq W \leq 2000
- S_i \ (1 \leq i \leq H) 是一个长度为的字符串 W 组成
X和Y.
输入
输入由标准输入按以下格式给出:
H W S_1 S_2 \vdots S_H
输出
打印满足条件的设置围栏的方式数,模数 998244353.
示例输入 1
2 3 XYY YXY
示例输出 1
2
以下是设置围栏的八种方法。
X Y Y X|Y Y X Y|Y X|Y|Y
| | | |
Y X Y Y|X Y Y X|Y Y|X|Y
X Y Y X|Y Y X Y|Y X|Y|Y
----- -+--- ---+- -+-+-
Y X Y Y|X Y Y X|Y Y|X|Y
例如,如果在 2-nd 和 3-rd 列,块是:
XY YX
Y Y
每个块都有两个 Ys,因此满足条件。
如果在 1-st 和 2-nd 行和 1-st 和 2-nd 列,块是:
X
YY
Y
XY
这些块,除了第二个之外,没有恰好两个 Ys,所以条件不满足。
示例输入 2
2 3 XYX YYY
示例输出 2
0
无法设置围栏来满足条件。
示例输入 3
2 58 YXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXY YXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXY
示例输出 3
164036797
打印模数的方式数 998244353.