AT_arc157_c [ARC157C] YY Square

题目描述

在一个 $H$ 行 $W$ 列的网格中，每个格子上写有字符 X 或 Y。从上往下第 $i$ 行，从左往右第 $j$ 列的格子记作 $(i, j)$。网格中的字符由 $H$ 个字符串 $S_1, S_2, \dots, S_H$ 给出，第 $i$ 个字符串 $S_i$ 的第 $j$ 个字符表示格子 $(i, j)$ 上的字符。

从格子 $(1, 1)$ 出发，每次只能向下或向右移动，最终到达格子 $(H, W)$。对于一条这样的路径 $P$：

• 用 $\mathrm{str}(P)$ 表示按照路径 $P$ 经过的格子上的字符依次拼接得到的、长度为 $H + W - 1$ 的字符串；
• 定义路径 $P$ 的得分为 $\mathrm{str}(P)$ 中相邻的 Y 字符对的个数的平方。

所有可能的路径 $P$ 的数量为 $\displaystyle\binom{H + W - 2}{H - 1}$。请计算所有可能路径的得分之和，并对 $998244353$ 取模。

其中，$\displaystyle\binom{N}{K}$ 表示从 $N$ 个不同元素中选出 $K$ 个的组合数（二项式系数）。

输入格式

输入按以下格式从标准输入给出：

$H$ $W$
$S_1$
$S_2$
$\vdots$
$S_H$

输出格式

输出所有可能路径的得分之和对 $998244353$ 取模的结果。

样例 1

输入

2 2
YY
XY

输出

4

样例 2

输入

2 2
XY
YY

输出

2

样例 3

输入

10 20
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY

输出

423787835

说明/提示

限制条件

• $1 \leq H \leq 2000$
• $1 \leq W \leq 2000$
• $S_i$（$1 \leq i \leq H$）是仅由 X 和 Y 组成的、长度为 $W$ 的字符串。

样例解释 1

所有可能的路径 $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，第 $1, 2$ 个字符和第 $2, 3$ 个字符各有一对相邻的 Y，共 $2$ 处，因此得分为 $2^2 = 4$。
• 对于 $(1, 1) \to (2, 1) \to (2, 2)$，$\mathrm{str}(P) =$YXY，没有相邻的 Y，得分为 $0^2 = 0$。

所以总和为 $4 + 0 = 4$。

样例解释 2

两条路径的 $\mathrm{str}(P)$ 都是 XYY，得分均为 $1^2 = 1$。

样例解释 3

请输出所有路径得分之和对 $998244353$ 取模的结果。

由 ChatGPT 4.1 翻译