103115: [Atcoder]ABC311 F - Yet Another Grid Task
Description
Score : $525$ points
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$.
Input
Output
分数：$525$分
问题描述
有一个$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)$是黑色的。
当满足以下条件时，网格被认为是< strong>美丽的。
- 对于每一对整数$(i,j)$，满足$1 \le i \le N, 1 \le j \le M$，如果方格$(i,j)$是黑色的，则方格$(i,j)$下方的方格和$(i,j)$右下方的方格也是黑色的（如果存在）。
- 正式来说，满足以下所有条件：
- 如果方格$(i,j)$是黑色的并且方格$(i+1,j)$存在，则方格$(i+1,j)$也是黑色的。
- 如果方格$(i,j)$是黑色的并且方格$(i+1,j+1)$存在，则方格$(i+1,j+1)$也是黑色的。
Takahashi可以将零个或多个白色方格涂成黑色，他会这样做以使网格变得美丽。
找出他可以制作的不同美丽网格的数量，模$998244353$。
当两个网格中有正方形具有不同的颜色时，认为这两个网格是不同的。
约束条件
- $1 \le N,M \le 2000$
- $S_i$是由
.和#组成的长度为$M$的字符串。
输入
输入以标准输入的以下格式给出：
$N$ $M$ $S_1$ $S_2$ $\vdots$ $S_N$
输出
打印一个整数作为答案。
样例输入1
2 2 .# ..