[toggle hide="yes" title="题目" color=""]

Input

输入数据的第一行为两个整数N,M表示棋盘大小。第二行为两个整数P,K,
表示攻击范围模板的大小,以及棋子在模板中的位置。接下来三行,
每行P个数,表示攻击范围的模版。每个数字后面一个空格。

Output

 一个整数,表示可行方案Mod 2 ^32

Sample Input

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

Sample Output

7

HINT

 1<=N<=10^6,1<=M<=6

[/toggle]

题目描述不是很清楚,实际上就是给你一个矩阵表示每个点的攻击范围,若下标均从1开始,点在第2行第p+1列,求放棋子的可行方案。

实际上是状压DP的水题,枚举行,枚举上一行状态,枚举本行状态即可,但是这题的行数开的比较大,实测普通的DP只能得70分,观察式子发现,合法的状态并不多,每行撑死也就64种,而且式子是一个齐次递推数列,所以矩阵轻松搞。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974