102957: [Atcoder]ABC295 Ex - E or m
Description
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$.
Input
题意翻译
开始你有一个全 $0$ 矩阵，你可以随意执行如下操作： - 选择任意一行，将其从最左端开始的连续一段染成 $1$。 - 选择任意一列，将其从最上端开始的连续一段染成 $1$。 如果一个矩阵可以由此得到，那么这个矩阵被称为好的。 现在你有一个 `01?` 矩阵 $a$，你需要将所有 `?` 替换为 `0` 或 `1`，问得到的矩阵中有多少个是好的。答案对 $998244353$ 取模。 $1\le n,m\le 18$。Output
分数：600分
问题描述
我们有一个具有$N$行和$M$列的网格$A$。最初，每个方格都写有0。
让我们执行以下操作。
- 对于每个整数$i$，使得$1 \le i \le N$，在第$i$行中，将零个或多个最左边的数字变成1。
- 对于每个整数$j$，使得$1 \le j \le M$，在第$j$列中，将零个或多个最上面的数字变成1。
让我们将这样获得的网格集合记为$S$。
给你一个具有$N$行和$M$列的网格$X$，由0，1和?组成。
在将每个?替换为0或1时，可以得到$2^q$个网格，其中$q$是$X$中的?的数量。其中有多少个在$S$中？
这个计数可能非常大，所以求其模$998244353$的结果。
约束条件
- $N$和$M$是整数。
- $1 \le N,M \le 18$
- $X$是一个具有$N$行和$M$列的网格，由
0，1和?组成。
输入
输入通过标准输入给出以下格式：
$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
以下六个网格在$S$中。
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 ??????????????????