分数: 600 点
问题陈述
有一个网格 H 行和 W 列,其中每个方格都有一个字符
上面写着 X 和 Y 。
让 (i, j) 表示位于 i从顶部开始的第行和 j左起第 列。
网格上的字符给出为 H 字符串 S_1, S_2, \dots, S_H: j- 第一个字符 S_i 是方块上的字符 (i, j).
对于路径 P 来自广场 (1, 1) 到正方形 (H, W) 通过反复向下或向右移动到相邻的方格获得, 分数 树的 定义如下。
- 让 \mathrm{str}(P) 是长度的字符串 (H + W - 1) 通过连接所访问的方格上的字符获得 P 按访问顺序排列。
- 的分数 P 是 数字的平方 对连续
Ys 在 \mathrm{str}(P).
有 \displaystyle\binom{H + W - 2}{H - 1} 这样的路径。求所有这些路径的分数总和,取模 998244353.
什么是 \binom{N}{K}?
\displaystyle\binom{N}{K} 是二项式系数,代表选择的方式数量 K 来自 N 不同的元素。约束
- 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 2 YY XY
示例输出 1
4
有两种可能的路径 P: (1, 1) \to (1, 2) \to (2, 2) 和 (1, 1) \to (2, 1) \to (2, 2).
- 对于 (1, 1) \to (1, 2) \to (2, 2),我们有 \mathrm{str}(P) = {}
YYY,有两对连续Y位于位置 1, 2 和 2, 3,所以分数是 2^2 = 4. - 对于 (1, 1) \to (2, 1) \to (2, 2),我们有 \mathrm{str}(P) = {}
YXY,没有连续的对Ys ,所以得分为 0^2 = 0.
因此,求和为 4 + 0 = 4.
示例输入 2
2 2 XY YY
示例输出 2
2
对于两个可能的路径之一 P,我们有 \mathrm{str}(P) = {}XYY,得分为 1^2 = 1.
示例输入 3
10 20 YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY YYYYYYYYYYYYYYYYYYYY
示例输出 3
423787835
打印分数的模数总和 998244353.