Score : $525$ points

问题描述

存在一个 $N \times M$ 的网格，以及一名玩家站在该网格上。
令 $(i,j)$ 表示该网格从上到下第 $i$ 行、从左到右第 $j$ 列的方格。
该网格中的每个方格是黑色或白色，由长度为 $M$ 的 $N$ 个字符串 $S_1,S_2,\dots,S_N$ 如下表示：

• 如果 $S_i$ 的第 $j$ 个字符是 ., 方格 $(i,j)$ 为白色；
• 如果 $S_i$ 的第 $j$ 个字符是 #, 方格 $(i,j)$ 为黑色。

当满足以下条件时，该网格被称为 美丽 的。

• 对于每一对整数 $(i,j)$，使得 $1 \le i \le N, 1 \le j \le M$，如果方格 $(i,j)$ 是黑色的，则其正下方和右下角紧邻的方格（若存在）也必须是黑色。
• 正式地，需满足以下所有条件：
  • 如果方格 $(i,j)$ 是黑色且方格 $(i+1,j)$ 存在，则方格 $(i+1,j)$ 也是黑色。
  • 如果方格 $(i,j)$ 是黑色且方格 $(i+1,j+1)$ 存在，则方格 $(i+1,j+1)$ 也是黑色。

高桥可以将零个或多个白色方格涂成黑色，他的目的是通过这种方式使网格变得美丽。
求他能构造出的不同美丽网格的数量，结果对 $998244353$ 取模。
两个网格被认为是不同的，当存在一个在两个网格中颜色不同的方格时。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There is an $N \times M$ grid and a player standing on it.
Let $(i,j)$ denote the square at the $i$-th row from the top and $j$-th column from the left of this grid.
Each square of this grid is black or white, which is represented by $N$ strings $S_1,S_2,\dots,S_N$ of length $M$ as follows:

• if the $j$-th character of $S_i$ is ., square $(i,j)$ is white;
• if the $j$-th character of $S_i$ is #, square $(i,j)$ is black.

The grid is said to be beautiful when the following condition is satisfied.

• For every pair of integers $(i,j)$ such that $1 \le i \le N, 1 \le j \le M$, if square $(i,j)$ is black, the square under $(i,j)$ and the square to the immediate lower right of $(i,j)$ are also black (if they exist).
• Formally, all of the following are satisfied.
  • If square $(i,j)$ is black and square $(i+1,j)$ exists, square $(i+1,j)$ is also black.
  • If square $(i,j)$ is black and square $(i+1,j+1)$ exists, square $(i+1,j+1)$ is also black.

Takahashi can paint zero or more white squares black, and he will do so to make the grid beautiful.
Find the number of different beautiful grids he can make, modulo $998244353$.
Two grids are considered different when there is a square that has different colors in those two grids.

Constraints

• $1 \le N,M \le 2000$
• $S_i$ is a string of length $M$ consisting of . and #.

Input

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

$N$ $M$

$S_1$

$S_2$

$\vdots$

$S_N$

Output

Print the answer as an integer.

Sample Input 1

2 2
.#
..

Sample Output 1

3

He can make the following three different beautiful grids:

.#  .#  ##
.#  ##  ##

Sample Input 2

5 5
....#
...#.
..#..
.#.#.
#...#

Sample Output 2

92

Sample Input 3

25 25
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................

Sample Output 3

604936632

Find the count modulo $998244353$.

update @ 2024/3/10 08:51:43