#P13455. [ABC295Ex] E or m

    ID: 12639 传统题 4000ms 1024MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2600状压DP前缀和模运算队列字符串动态规划计数DP

[ABC295Ex] E or m

AT_abc295_h [ABC295Ex] E or m

时间限制4.00s 内存限制1.00GB

题目描述

有一个 NN 行 MM 列的网格 AA,初始时所有格子上的数字都是 00。
接下来进行如下操作:

  • 对于每个满足 1≤i≤N1 \le i \le N 的整数 ii,可以将 AA 的第 ii 行从左边起连续的 00 个或更多格子的数字变为 11。
  • 对于每个满足 1≤j≤M1 \le j \le M 的整数 jj,可以将 AA 的第 jj 列从上边起连续的 00 个或更多格子的数字变为 11。

通过上述操作能够得到的所有 AA 的集合记为 SS。

现在给定一个由 0、1、? 组成的 NN 行 MM 列的网格 XX。
将 XX 中的每个 ? 替换为 0 或 1,一共可以得到 2q2^q 个不同的网格(qq 为 XX 中 ? 的总数)。
在这些网格中,有多少个属于 SS?
由于答案可能非常大,请输出答案对 998244353998244353 取模的结果。

输入格式

输入通过标准输入给出,格式如下:

NN MM
X1,1 X1,2 … X1,MX_{1,1}\ X_{1,2}\ \dots\ X_{1,M}
X2,1 X2,2 … X2,MX_{2,1}\ X_{2,2}\ \dots\ X_{2,M}
⋮\vdots
XN,1 XN,2 … XN,MX_{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,MN, M 为整数
  • 1≤N,M≤181 \le N, M \le 18
  • XX 是由 0、1、? 组成的 NN 行 MM 列的网格

样例解释 1

满足条件的网格共有如下 66 个:

011  011  001
010  011  110

001  011  011
111  110  111

样例解释 2

即使 XX 中没有 ?,答案也有可能为 00。

样例解释 3

请注意,答案需要对 998244353998244353 取模。