#P4000. [TJOI2015]棋盘
[TJOI2015]棋盘
题目描述
给定一个 行 列的棋盘,每格至多放一枚棋子。棋子共用一个 的二值攻击模板。模板行列均从 编号,模板第 行(中间一行)第 列对准棋子本身的位置。
若棋子位于棋盘的 ,则模板中值为 的位置 对应它能攻击的格子 ,超出棋盘的格子忽略。模板对准棋子自身的位置一定为 。判断摆放是否合法时,只考虑两枚不同的棋子,只要其中任一枚能攻击到另一枚,该摆法就不合法。
求合法的摆放方案数对 取模的结果。空棋盘也算一种方案。
输入格式
第一行两个整数 ,表示棋盘的行数和列数。第二行两个整数 ,表示模板列数和棋子在模板中的列号。接下来三行,每行 个由空格分隔的整数,每个整数为 或 。
评测数据满足 ,,,。下面的原题样例中 ,按同一坐标映射规则计算即可。
输出格式
输出一个整数,表示合法的摆放方案数对 取模的余数。
样例
2 2
3 1
0 1 0
1 1 1
0 1 0
7