← 返回题目列表

AtCoder · arc157_c

C. YY广场

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

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