Score : $600$ points

问题描述

我们有一个 $N$ 行和 $M$ 列的网格 $A$。最初，每个格子上都写有数字 $0$。

• 对于满足 $1 \le i \le N$ 的每个整数 $i$，在第 $i$ 行中，将左侧零个或多个格子中的数字变为 $1$。
• 对于满足 $1 \le j \le M$ 的每个整数 $j$，在第 $j$ 列中，将顶部零个或多个格子中的数字变为 $1$。

令 $S$ 为通过上述方式可以获得的所有网格集合。

给定一个由 0、1 和 ? 组成的 $N$ 行和 $M$ 列的网格 $X$。

其中包含 $q$ 个 ?，通过将每个 ? 替换为 0 或 1，可以得到 $2^q$ 个不同的网格。请问，在这些网格中有多少个属于集合 $S$？

由于这个计数可能非常大，请计算它对 $998244353$ 取模的结果。

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

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$.

update @ 2024/3/10 12:17:21