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 ??????????????????