#P4000. [TJOI2015]棋盘

[TJOI2015]棋盘

题目描述

给定一个 nn 行 mm 列的棋盘,每格至多放一枚棋子。棋子共用一个 3×p3\times p 的二值攻击模板。模板行列均从 00 编号,模板第 11 行(中间一行)第 kk 列对准棋子本身的位置。

若棋子位于棋盘的 (r,c)(r,c),则模板中值为 11 的位置 (i,j)(i,j) 对应它能攻击的格子 (r+i−1,c+j−k)(r+i-1,c+j-k),超出棋盘的格子忽略。模板对准棋子自身的位置一定为 11。判断摆放是否合法时,只考虑两枚不同的棋子,只要其中任一枚能攻击到另一枚,该摆法就不合法。

求合法的摆放方案数对 2322^{32} 取模的结果。空棋盘也算一种方案。

输入格式

第一行两个整数 n,mn,m,表示棋盘的行数和列数。第二行两个整数 p,kp,k,表示模板列数和棋子在模板中的列号。接下来三行,每行 pp 个由空格分隔的整数,每个整数为 00 或 11。

评测数据满足 1≤n≤1061\le n\le10^6,1≤m≤61\le m\le6,1≤p≤m1\le p\le m,0≤k<p0\le k<p。下面的原题样例中 p=3>mp=3>m,按同一坐标映射规则计算即可。

输出格式

输出一个整数,表示合法的摆放方案数对 2322^{32} 取模的余数。

样例

2 2
3 1
0 1 0
1 1 1
0 1 0
7

NOI 2015 天津队选拔赛第二试原题