/ 
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
N 行 M 列のグリッド A があり、はじめ全てのマスに 0 が書き込まれています。
ここに以下の操作を行います。
- 1 \le i \le N を満たす各整数 i に対して、 A の i 行目の左から 0 個以上のマスの数字を 1 にする。
- 1 \le j \le M を満たす各整数 j に対して、 A の j 列目の上から 0 個以上のマスの数字を 1 にする。
この手続きによって作ることのできる A の集合を S とします。
0, 1, ? からなる N 行 M 列のグリッド X が与えられます。
? を 0 か 1 に置き換えて得られるグリッドは X に含まれる ? の総数を q とすると 2^q 個ありますが、このうち S の要素であるものはいくつありますか？
答えは非常に大きくなる場合があるので、 998244353 で割った余りを求めてください。
制約
- N,M は整数
- 1 \le N,M \le 18
- X は
0,1,?からなる N 行 M 列のグリッド
入力
入力は以下の形式で標準入力から与えられる。
N M X_{1,1} X_{1,2} \dots X_{1,M} X_{2,1} X_{2,2} \dots X_{2,M} \vdots X_{N,1} X_{N,2} \dots X_{N,M} 出力
答えを整数として出力せよ。
入力例 1
2 3 0?1 ?1?
出力例 1
6
条件を満たすグリッドは以下の 6 つです。
011 011 001 010 011 110 001 011 011 111 110 111
入力例 2
5 3 101 010 101 010 101
出力例 2
0
X に ? が存在しない場合も、答えが 0 である場合もあります。
入力例 3
18 18 ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ??????????????????
出力例 3
462237431
答えを 998244353 で割った余りを求めることに注意してください。
Score : 600 points
Problem Statement
We have a grid A with N rows and M columns. Initially, 0 is written on every square.
Let us perform the following operation.
- For each integer i such that 1 \le i \le N, in the i-th row, turn the digits in zero or more leftmost squares into 1.
- For each integer j such that 1 \le j \le M, in the j-th column, turn the digits in zero or more topmost squares into 1.
Let S be the set of grids that can be obtained in this way.
You are given a grid X with N rows and M columns consisting of 0, 1, and ?.
There are 2^q grids that can be obtained by replacing each ? with 0 or 1, where q is the number of ? in X. How many of them are in S?
This count can be enormous, so find it modulo 998244353.
Constraints
- N and M are integers.
- 1 \le N,M \le 18
- X is a grid with N rows and M columns consisting of
0,1, and?.
Input
The input is given from Standard Input in the following format:
N M X_{1,1} X_{1,2} \dots X_{1,M} X_{2,1} X_{2,2} \dots X_{2,M} \vdots X_{N,1} X_{N,2} \dots X_{N,M} Output
Print an integer representing the answer.
Sample Input 1
2 3 0?1 ?1?
Sample Output 1
6
The following six grids are in S.
011 011 001 010 011 110 001 011 011 111 110 111
Sample Input 2
5 3 101 010 101 010 101
Sample Output 2
0
X may have no ?, and the answer may be 0.
Sample Input 3
18 18 ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ?????????????????? ??????????????????
Sample Output 3
462237431
Be sure to find the count modulo 998244353.