/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
表示言語
/ /Score : 100 points
Problem Statement
Cenix wants to fill an N \times M grid using the following six types of square tiles. There are plenty of each type of tile, and they can be rotated before placement. When placing tiles, every edge connected to a path must touch an edge connected to a path on a neighboring tile. However, not all paths need to be connected.
While filling the grid, Cenix realized that the task was too easy. Cenix now intends to fill the remaining cells using only tiles that connect one side and tiles that connect three sides.
A grid with some cells already filled with tiles is given as follows.
- The type of tile placed in the i-th row and j-th column of the grid is denoted by A_{i,j}.
- If no tile is placed in that cell, A_{i,j} is -1.
- If a tile is placed in that cell, A_{i,j} is the sum of 1 (if the tile is connected to the top edge), 2 (if connected to the bottom edge), 4 (if connected to the left edge), and 8 (if connected to the right edge).
Find the number of ways to fill the remaining cells using only these two types of tiles.
Constraints
- 1 \le N, M \le 500\,000
- 1 \le NM \le 500\,000
- -1 \le A_{i,j} \le 15
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
A_{1,1} A_{1,2} \dots A_{1,M}
A_{2,1} A_{2,2} \dots A_{2,M}
\vdots
A_{N,1} A_{N,2} \dots A_{N,M}
Output
Output the number of ways to fill the grid, modulo 998\,244\,353.
Sample Input 1
3 3 10 -1 6 -1 -1 -1 9 -1 -1
Sample Output 1
2
Sample Input 2
1 3 -1 -1 -1
Sample Output 2
0
Sample Input 3
5 5 -1 -1 0 0 0 -1 -1 0 0 0 0 0 -1 0 -1 0 0 3 0 3 0 0 -1 0 -1
Sample Output 3
2
表示言語
/ /점수 : 100 점
문제
세닉스는 다음 6종류의 정사각형 타일을 이용해 N \times M 크기의 격자판을 채우려 한다. 각 타일은 충분히 많으며 회전해서 놓을 수 있다. 타일을 놓을 때는 길이 연결된 모든 변이 이웃한 타일의 길이 연결된 변과 맞닿아야 한다. 모든 길이 하나로 연결될 필요는 없다.
세닉스는 격자판을 채우다가 격자판을 채우는 게 너무 쉽다는 생각이 들었다. 세닉스는 남은 칸을 한 변에 길이 연결된 타일과 세 변에 길이 연결된 타일만을 이용해 전부 채우려 한다.
일부 칸을 타일로 채운 격자판이 다음과 같이 주어진다.
- 격자판의 위에서부터 i번째, 왼쪽에서부터 j번째 칸에 놓인 타일의 종류는 A_{i,j}다.
- 해당 칸에 타일이 놓여 있지 않다면 A_{i,j}는 -1이다.
- 해당 칸에 타일이 놓여 있다면 A_{i,j}는 그 타일의 윗변에 길이 연결된 경우 1, 아랫변에 길이 연결된 경우 2, 왼변에 길이 연결된 경우 4, 오른변에 길이 연결된 경우 8을 모두 더한 값이다.
남은 칸을 두 종류의 타일로 모두 채우는 방법의 수를 구해 보자.
제한
- 1 \le N, M \le 500\,000
- 1 \le NM \le 500\,000
- -1 \le A_{i,j} \le 15
- 입력으로 주어지는 수는 모두 정수이다.
입력
입력은 다음 형식으로 표준 입력으로 주어진다.
N M
A_{1,1} A_{1,2} \dots A_{1,M}
A_{2,1} A_{2,2} \dots A_{2,M}
\vdots
A_{N,1} A_{N,2} \dots A_{N,M}
출력
격자판을 채우는 방법의 수를 998\,244\,353으로 나눈 나머지를 출력한다.
입력 예 1
3 3 10 -1 6 -1 -1 -1 9 -1 -1
출력 예 1
2
입력 예 2
1 3 -1 -1 -1
출력 예 2
0
입력 예 3
5 5 -1 -1 0 0 0 -1 -1 0 0 0 0 0 -1 0 -1 0 0 3 0 3 0 0 -1 0 -1
출력 예 3
2
表示言語
/ /配点 : 100 点
問題文
セニックスは、以下の6種類の正方形タイルを使って、N \times Mサイズの格子盤を埋めようとしている。各タイルは十分にあり、回転させて配置することができる。タイルを配置する際は、道が接続されたすべての辺が、隣接するタイルの道が接続された辺と接していなければならない。すべての道が一つにつながっている必要はない。
セニックスは格子盤を埋めているうちに、格子盤を埋めるのがあまりにも簡単だと感じた。セニックスは、残りのマスを一辺のみをつなぐタイルと三辺をつなぐタイルのみを利用してすべて埋めようとしている。
一部のマスをタイルで埋めた格子盤が以下のように与えられる。
- 格子盤の上から数えてi番目、左から数えてj番目のマスに置かれたタイルの種類はA_{i,j}である。
- 該当するマスにタイルが置かれていない場合、A_{i,j}は-1である。
- 該当するマスにタイルが置かれている場合、A_{i,j}はそのタイルの上辺に道が接続されている場合は1、下辺に道が接続されている場合は2、左辺に道が接続されている場合は4、右辺に道が接続されている場合は8をすべて足した値である。
残りのマスを2種類のタイルで全て埋める方法の数を求めよ。
制約
- 1 \le N, M \le 500\,000
- 1 \le NM \le 500\,000
- -1 \le A_{i,j} \le 15
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる．
N M
A_{1,1} A_{1,2} \dots A_{1,M}
A_{2,1} A_{2,2} \dots A_{2,M}
\vdots
A_{N,1} A_{N,2} \dots A_{N,M}
出力
格子盤を埋める方法の数を998\,244\,353で割った余りを出力する。
入力例 1
3 3 10 -1 6 -1 -1 -1 9 -1 -1
出力例 1
2
入力例 2
1 3 -1 -1 -1
出力例 2
0
入力例 3
5 5 -1 -1 0 0 0 -1 -1 0 0 0 0 0 -1 0 -1 0 0 3 0 3 0 0 -1 0 -1
出力例 3
2