题目大意
问讲一个大小为4*n的棋盘用无数1*2的骨牌不重叠覆盖有多少种方案。
分析
我们考虑可以将长为n的棋盘分为两块，一个大小为n-i，另一个大小为i，而为了避免对于不同的i构造出相同的情况，我们必须使长为i的那一半棋盘是一种不可分离的情况，即对于这种情况去掉其中的任意一行均不合法。我们设对于长为n的棋盘方案数为f(n)，长为n的棋盘的不可分离棋盘的数量为a[n]。我们自己画一画可以得到a[1]=1,a[2]=4,a[3]=2,a[4]=3,a[5]=2,a[6]=3，不难发现当n>=2是如果n为奇数a[n]=2，否则a[n]=3。
所以我们可以得到
f(n)=f(n-1)+4f(n-2)+2f(n-3)+3f(n-4)+2f(n-5)+3f(n-6)......
我们发现
f(n-3)+4f(n-4)+2f(n-5)+3f(n-6)......=f(n-2)
所以我们可以把公式变为
f(n)=f(n-1)+5f(n-2)+f(n-3)-f(n-4)
然后我们便可以推出矩阵了。详见代码。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
int n,m;
struct mat {
int g[][];
};
inline mat operator * (const mat a,const mat b){
mat c;
for(int i=;i<=;i++)
for(int j=;j<=;j++){
int x=;
for(int k=;k<=;k++)
x=(x+a.g[i][k]*b.g[k][j]%m)%m;
c.g[i][j]=x;
}
return c;
}
inline int pw(int p){
mat a,res;
for(int i=;i<=;i++)
for(int j=;j<=;j++)
a.g[i][j]=;
a.g[][]=a.g[][]=a.g[][]=a.g[][]=a.g[][]=;
a.g[][]=;a.g[][]=-;
res=a;
while(p){
if(p&)res=res*a;
a=a*a;
p>>=;
}
int ans=((res.g[][]*%m+m)%m+(res.g[][]*%m+m)%m+
(res.g[][]*%m+m)%m+(res.g[][]%m+m)%m)%m;
return ans;
}
int main(){
scanf("%d%d",&n,&m);
while(n&&m){
if(n<=){
if(n==)cout<<%m<<endl;
else if(n==)cout<<%m<<endl;
else if(n==)cout<<%m<<endl;
else cout<<%m<<endl;
}else printf("%d\n",pw(n-));
scanf("%d%d",&n,&m);
}
return ;
}