[TJOI2015] 棋盘

Description

为了提高智商,ZJY去新世界旅游了。可是旅游过后的ZJY杯具的发现要打开通往原来世界的门,必须要解开门上面画的谜题。谜题是这样的:有个\(n\)行\(m\)列的棋盘,棋盘上可以放许多特殊的棋子。每个棋子的攻击范围是\(3\)行,\(p\)列。输入数据用一个\(3\times p\)的矩阵给出了棋子攻击范围的模板,棋子被默认为模板中的第\(1\)行,第\(k\)列,则棋子能攻击到的位置是\(1\),不能攻击到的位置是\(0\)。\(1\leq p\leq m,0\leq k。输入数据保证第\(1\)行第\(k\)列的位置是\(1\)。打开门的密码就是,在要求棋子互相不能攻击到的前提下,摆放棋子的方案数。注意什么棋子都不摆放也算作一种可行方案。由于方案数可能很大,而密码为\(32\)位的二进制密码,所以ZJY仅需要知道方案数对\(2^{32}\)取余数的结果即可。

Input

输入数据的第一行为两个整数\(n\)和\(m\),表示棋盘的大小。第二行为两个整数\(p\)和\(k\),表示接下来的攻击范围模板的大小,以及棋子在模板中的位置。接下来三行,每行有\(P\)个数,表示攻击范围的模版。每个数字后有一个空格。

Output

输出数据仅有一行,一个整数,表示可行的方案数模\(2^{32}\)的余数。

Range

对于\(10\%\)，\(1 \leq n \leq 5,1 \leq m \leq 5\)

对于\(50\%\)，\(1 \leq n \leq 1000,1 \leq m \leq 6\)

对于\(100\%\)，\(1\leq n\leq 1000000,1\leq m\leq 6\)

Solution

恶心题。
被这题卡了一天。

首先注意到它的行和列是从 \(0\) 开始标号的，所以第 \(1\) 行第 \(p\) 列其实是中间一行的某一列。

预处理出所有能摆放和两行之间能转移的情况。
这里要用位运算，最开始拿数组模拟每位弄了半天还是错的，用位运算一下就出来了。

观察到转移可以用矩阵加速，于是一个矩阵快速幂敲上去就行了。

注意最后求答案矩阵的时候要新开一个数组不能直接在 \(f\) 数组上面求！

Code

#include
#include
#include
#define int unsigned long longint maxn;
int mp[5];
int n,m,p,k;
bool vis[105];
int f[70][70];
const int mod=4294967296;struct Matrix{int a[100][100];void clear(){memset(a,0,sizeof a);}void init(){for(int i=0;i>(p-k+1-i)))!=(1ll<>(p-k+1-i))))return 0;}}if(y&(1<>(p-k+1-i))))return 0;}}}return 1;
}Matrix ksm(Matrix a,int b,int c){Matrix ans; ans.init();while(b){if(b&1)ans=ans*a;a=a*a;b>>=1;}return ans;
}void mul(int a[70][70],int b[70][70],int c[70][70])
{int ret[70][70];memset(ret,0,sizeof ret);for(int i=0;i>=1;}
}signed main(){read(n),read(m),read(p),read(k); k++;maxn=1<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！