思路：考虑全部铺满时，前2列的放法。有如下5种情况：（转自http://blog.csdn.net/elbadaernu/article/details/77825979 写的很详细 膜一下） 
假设f（n）表示列数为n时的方案数，那么这五种情况合法的方案数相加即f（n）。这里n大于2.
第一种的方案数即f（n-1），第二种的方案数即f（n-2）。
第三种：接下来有两种方案可以选择，一是用一块毛毯去填补第二列的空缺部分，那么此时接下来填补的方案数为f（n-2），二是用两块毛毯去填补，这样的话第三列又会形成一个新的空缺，如下图所示： 
所以我们又可以像之前那样去填补，所以第三种的方案数为f（n-2）+f（n-3）+f（n-4）+……+f（0）,f（0）=1
第四种：情况与第三种类似，方案数与其相同。
第五种：开始的选择也是两种，一是选择一块毯子去填，这样接下来填补的方案数为f（n-2），或者选择两块去填，然后，为了使它铺满，我们还得用两块毛毯去铺上下两个空缺的地方，这时的空缺形成了之前的情况，如下图所示： 
以此类推，所以第五种的方案数为f（n-2）+f（n-4）+f（n-6）+……+f（1）或者f（0）（偶数0，奇数1）
所以总的方案数
f（n）=f（n-1）+f（n-2）+2*（f（n-2）+f（n-3）+……+f（0））+f（n-2）+f（n-4）+f（n-6）+……+f（1）或者f（0）
然后将n=n-2代入上式，然后用f（n）减去f（n-2），
化简得f（n）=f（n-1）+5*f（n-2）+f（n-3）-f（n-4）。
然后自己的矩阵快速幂也换了一个较为通用的写法：
#include <cstdio> #include <iostream> #include <cstring> #include <queue> #include <algorithm> using namespace std; typedef long long ll; const ll mod=1000000007; struct Martix { ll mp[5][5]; ll r,c; }; Martix mul(Martix a,Martix b) { Martix c; c.r=a.r; c.c=b.c; for(int i=0;i<a.r;i++) { for(int j=0;j<b.c;j++) { c.mp[i][j]=0; for(int k=0;k<a.c;k++) { c.mp[i][j]=(a.mp[i][k]*b.mp[k][j]+c.mp[i][j]+mod)%mod; c.mp[i][j]%=mod; } } } return c; } Martix ans; Martix a;// 系数矩阵 void init() { memset(ans.mp,0,sizeof(ans.mp)); ans.r=2; ans.c=1; ans.mp[0][0]=36; ans.mp[1][0]=11; ans.mp[2][0]=5; ans.mp[3][0]=1; a.r=a.c=4; memset(a.mp,0,sizeof(a.mp)); a.mp[0][0]=1; a.mp[0][1]=5; a.mp[0][2]=1; a.mp[0][3]=-1; a.mp[1][0]=a.mp[2][1]=a.mp[3][2]=1; } Martix pow(Martix x,ll k) { Martix temp; temp.r=temp.c=x.r; memset(temp.mp,0,sizeof(temp.mp)); for(int i=0;i<x.r;i++) // 单位矩阵 { for(int j=0;j<x.c;j++) if(i==j) temp.mp[i][j]=1; } while(k) { if(k&1) temp=mul(x,temp); k/=2; x=mul(x,x); } return temp; } int main() { ll n; while(cin>>n) { init(); if(n==0) { cout<<1<<endl; continue; } if(n==1) { cout<<1<<endl; continue; } if(n==2) { cout<<5<<endl; continue; } if(n==3) { cout<<11<<endl; continue; } if(n==4) { cout<<36<<endl; continue; } a=pow(a,n-4);// ans=mul(a,ans); cout<<ans.mp[0][0]%mod<<endl; } return 0; }
原文：http://www.cnblogs.com/z1141000271/p/7747781.html