#P18661. LaLa and Magic Stone

    ID: 17997 传统题 1000ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3000省选/NOI-直接模拟暴力枚举双射计数乘法原理

LaLa and Magic Stone

LaLa and Magic Stone

一天,拉拉发现魔法工具使用的魔法石部件用完了。你可以把这种部件理解为我们世界中的电池。她赶紧去附近的商店买了一整块魔法石。

拉拉想把这块魔法石切成部件。石板由 N×M 个小格构成,其中有些格子不适合她的魔法工具使用。

需要的部件是由 7 个小格组成的 U 形,形状如下。允许对该形状作90度整数倍旋转。

原题的七格U形部件

拉拉忘了购买魔法石胶水,因此不能把切下来的更小碎片粘起来组成所需形状。她也不愿浪费魔法石:当且仅当每一个可用格都属于一个所需形状的部件时,她才满意。每个部件仅包含可用格,不同部件不能重叠。

请计算让拉拉满意的切割方案数,答案对 998244353 取模。两个方案不同,当且仅当存在两个可用格,它们在一个方案里属于同一个部件,在另一个方案里属于不同部件。

输入格式

单组输入,格式为:

N M
S0
S1
...
S(N-1)

N 为行数,M 为列数。每个 Si 是长度为 M 的二进制字符串。从上到下、从左到右分别以0为起点编号;Si 的第 j 个字符为 1 当且仅当格子(i,j)不可用,为 0 则表示可用。

所有输入满足:N、M 为整数,3≤N,M≤1000。

输出格式

输出一个整数,表示满足要求的切割方案数对998244353取模的结果。

样例输入 1

4 4
0001
0000
0000
1000

样例输出 1

2

样例输入 2

5 4
0001
0101
0000
1010
1000

样例输出 2

1

样例说明

第一组样例的两种切割方式如下(原PDF插图):

第一组样例切法一

第一组样例切法二

第二组样例唯一的切割方式如下(原PDF插图):

第二组样例唯一切法