AT_abc295_h [ABC295Ex] E or m

题目描述

有一个 $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$。
将 $X$ 中的每个 ? 替换为 0 或 1，一共可以得到 $2^q$ 个不同的网格（$q$ 为 $X$ 中 ? 的总数）。
在这些网格中，有多少个属于 $S$？
由于答案可能非常大，请输出答案对 $998244353$ 取模的结果。

输入格式

输入通过标准输入给出，格式如下：

$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

输入 #1

2 3
0?1
?1?

输出 #1

6

输入输出样例 #2

输入 #2

5 3
101
010
101
010
101

输出 #2

0

输入输出样例 #3

输入 #3

18 18
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????

输出 #3

462237431

说明/提示

限制条件

• $N, M$ 为整数
• $1 \le N, M \le 18$
• $X$ 是由 0、1、? 组成的 $N$ 行 $M$ 列的网格

样例解释 1

满足条件的网格共有如下 $6$ 个：

011  011  001
010  011  110

001  011  011
111  110  111

样例解释 2

即使 $X$ 中没有 ?，答案也有可能为 $0$。

样例解释 3

请注意，答案需要对 $998244353$ 取模。

由 ChatGPT 4.1 翻译