201573: [AtCoder]ARC157 D - YY Garden

Memory Limit:1024 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $600$ points

Problem Statement

There is a grid with $H$ rows and $W$ columns where each square has one of the characters X and Y written on it. Let $(i, j)$ denote the square at the $i$-th row from the top and $j$-th column from the left. The characters on the grid are given as $H$ strings $S_1, S_2, \dots, S_H$: the $j$-th character of $S_i$ is the character on square $(i, j)$.

You can set up fences across the grid between adjacent rows and columns. Fences may intersect. After setting up fences, a block is defined as the set of squares reachable from some square by repeatedly moving up, down, left, or right to the adjacent square without crossing fences. (See also Sample Output 1.)

There are $2^{H-1} \times 2^{W-1}$ ways to set up fences. How many of them satisfy the following condition, modulo $998244353$?

Condition: Each block has exactly two squares with Y written on it.

Constraints

  • $1 \leq H \leq 2000$
  • $1 \leq W \leq 2000$
  • $S_i \ (1 \leq i \leq H)$ is a string of length $W$ consisting of X and Y.

Input

The input is given from Standard Input in the following format:

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

Output

Print the number of ways to set up fences to satisfy the condition, modulo $998244353$.


Sample Input 1

2 3
XYY
YXY

Sample Output 1

2

Below are the eight ways to set up fences.

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

For instance, if a fence is set up between the $2$-nd and $3$-rd columns, the blocks are:

XY
YX
Y
Y

Each of these blocks has exactly two Ys, so the condition is satisfied.

If a fence is set up between the $1$-st and $2$-nd rows and the $1$-st and $2$-nd columns, the blocks are:

X
YY
Y
XY

These blocks, except the second, do not have exactly two Ys, so the condition is not satisfied.


Sample Input 2

2 3
XYX
YYY

Sample Output 2

0

There is no way to set up fences to satisfy the condition.


Sample Input 3

2 58
YXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXY
YXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXY

Sample Output 3

164036797

Print the number of ways modulo $998244353$.

Input

题意翻译

Feyn 有一个 $H$ 行 $W$ 列的矩阵,矩阵里面的元素均为字符 $X$ 或 $Y$。Feyn 想要在矩阵中放一些栅栏,栅栏要么放在横着的两行之间,要么放在竖着的两列之间,必须放完整行或整列。容易知道,在不限制栅栏数量的前提下,有 $2^{H-1}\times 2^{W-1}$ 种放栅栏的方案。Feyn 有一些特殊的癖好:他希望栅栏分割出的每个连通块内,都有**恰好**两个字符 $Y$。请输出上述所有方案中符合条件的方案数,对 $998244353$ 取模。 (translated by 342873)

加入题单

上一题 下一题 算法标签: