思路：考虑全部铺满时，前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=;
struct Martix
{
ll mp[][];
ll r,c;
};
Martix mul(Martix a,Martix b)
{
Martix c;
c.r=a.r;
c.c=b.c;
for(int i=;i<a.r;i++)
{
for(int j=;j<b.c;j++)
{
c.mp[i][j]=;
for(int k=;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,,sizeof(ans.mp));
ans.r=;
ans.c=;
ans.mp[][]=;
ans.mp[][]=;
ans.mp[][]=;
ans.mp[][]=; a.r=a.c=;
memset(a.mp,,sizeof(a.mp));
a.mp[][]=;
a.mp[][]=;
a.mp[][]=;
a.mp[][]=-;
a.mp[][]=a.mp[][]=a.mp[][]=;
}
Martix pow(Martix x,ll k)
{
Martix temp;
temp.r=temp.c=x.r;
memset(temp.mp,,sizeof(temp.mp));
for(int i=;i<x.r;i++) // 单位矩阵
{
for(int j=;j<x.c;j++) if(i==j) temp.mp[i][j]=;
}
while(k)
{
if(k&) temp=mul(x,temp);
k/=;
x=mul(x,x);
}
return temp;
}
int main()
{
ll n; while(cin>>n)
{
init();
if(n==)
{
cout<<<<endl;
continue;
}
if(n==)
{
cout<<<<endl;
continue;
}
if(n==)
{
cout<<<<endl;
continue;
}
if(n==)
{
cout<<<<endl;
continue;
}
if(n==)
{
cout<<<<endl;
continue;
}
a=pow(a,n-);//
ans=mul(a,ans);
cout<<ans.mp[][]%mod<<endl;
}
return ;
}