#2293. 棋盘
棋盘
棋盘
题目描述
NOI 2015天津市代表队选拔赛day2 B 棋盘 • 输入输出文件: chessboard.in/chessboard.out • 源文件名: chessboard.cpp/chessboard.c/chessboard.pas • 时间限制: 1s 内存限制: 128M 题目描述 为了提高智商,ZJY去新世界旅游了。可是旅游过后的ZJY杯具的发现, 要打开通往原来世界的门,必须要解开门上面画的谜题。谜题是这样的:有 一个n行m列的棋盘,棋盘上可以放许多特殊的棋子。每个棋子的攻击范围 是3行,p列。输入数据用一个3 × p的矩阵给出了棋子攻击范围的模板,棋子被 默认为模板中的第1行,第k列,则棋子能攻击到的位置是1,不能攻击到的位 置是0。1 ≤p ≤m,0 ≤k < p,输入数据保证第1行第k列的位置是1。打开门 的密码就是,在要求棋子互相不能攻击到的前提下,摆放棋子的方案数。注意 什么棋子都不摆放也算作一种可行方案。由于方案数可能很大,而密码为32位 的二进制密码,所以ZJY仅需要知道方案数对2的32次方取余数的结果即可。 输入 输入数据的第一行为两个整数n和m,表示棋盘的大小。第二行为两个整 数p和k,表示接下来的攻击范围模板的大小,以及棋子在模板中的位置。接下 来三行,每行有p个数,表示攻击范围的模版。每个数字后有一个空格。 输出 输出数据仅有一行,一个整数,表示可行的方案数模232的余数。 样例输入 2 2 3 1 0 1 0 1 1 1 0 1 0 样例输出 7 4
NOI 2015天津市代表队选拔赛day2 数据范围 对于10%的数据,1 ≤n ≤5,1 ≤m ≤5 对于50%的数据,1 ≤n ≤1000,1 ≤m ≤6 对于100%的数据,1 ≤n ≤1000000,1 ≤m ≤6 5
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
2 2
3 1
0 1 0
1 1 1
0 1 0
7