No.2838 Diagonals
タグ : / 解いたユーザー数 68
作問者 :
milkcoffee
/ テスター :
Problem Statement
There is a grid with $N$ rows and $M$ columns. The cell at the $i$-th row and $j$-th column of the grid is called $(i,j)$.
If $S_{i,j}$ is #, there is a square at $(i,j)$; if it is ., there is no square at $(i,j)$.
Each square is a regular square, and the boundaries between different squares are separated by straight lines.
For every square, you choose exactly $1$ of the following $4$ operations.
- Draw $1$ diagonal connecting the upper-left and lower-right corners of the square.
- Draw $1$ diagonal connecting the lower-left and upper-right corners of the square.
- Draw both of the above $2$ diagonals.
- Draw no diagonal.
After the operation, each square looks like one of those in the figure below.
Let $k$ be the number of squares. There are $4^{k}$ ways in total to draw lines on the whole grid. Find the number of ways to draw lines that satisfy the following condition, modulo $998244353$.
- [Condition] It is possible to paint each figure enclosed by lines in one of the $2$ colors, white or black, so that adjacent figures (those sharing an edge) have different colors.
Input
$N$ $M$
$S_{1,1}S_{1,2}\ldots S_{1,M}$
$\vdots$
$S_{N,1}S_{N,2}\ldots S_{N,M}$
- $1 \leq N,M \leq 500$
- $N,M$ are integers.
- $S_{i,j}$ is
#or. - There is at least $1$
#.
Output
Output the answer as an integer.
Sample
Sample 1
Input
3 4 ###. .### .##.
Output
16384
The grid given in the input is the one shown in the left figure.
For example, if the diagonals are drawn as in the center figure, the regions can be painted white and black as in the right figure, so the condition is satisfied.
There are $4^8 = 65536$ ways in total to draw diagonals, of which $16384$ satisfy the condition.
Sample 2
Input
3 3 #.# .#. #.#
Output
1024
No squares are adjacent to each other. Therefore, all $4^5 = 1024$ ways of drawing satisfy the condition.
Sample 3
Input
10 30 ####.####..#######.######.#.#. ###.##.#.##.##.##.######.##..# .#.#.#.#..######.....#..##.##. ##.#..#.###.###..#.###.####### ##.##.#####.####.#..##.#..#### ..#####..###########.##.##.##. ######..#...#####..###..##..## .###..#.##..#..###..#####...## ###..###########.#..##.#...### #.##.#####.####.####.####.###.
Output
993502162
Find the answer modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。