<题目链接>
<转载于 >>> >
题目大意：
让你用1*2规格的地毯去铺4*n规格的地面，告诉你n，问有多少种不同的方案使得地面恰好被铺满且地毯不重叠。答案对1000000007取模。
解题分析：
看到题目所给n的数据这么大，就知道肯定存在递推公式，至于递推公式的具体的分析过程 >>>大牛博客。求出递推公式后，由于数据太大，所以我们利用矩阵快速幂来加速。当然，如果比赛的时候想不到递推公式，我们也可以通过搜素得到前面的几组数据，然后在通过高斯消元来得到符合这些数据的公式的通解，最后再利用矩阵快速幂来求解。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define LL long long
const int mod=;
struct matrix
{
LL x[][];
};
matrix mutimatrix(matrix a,matrix b)
{
matrix temp;
memset(temp.x,,sizeof(temp.x));
for(int i=;i<;i++)
for(int j=;j<;j++)
for(int k=;k<;k++)
{
temp.x[i][j]+=a.x[i][k]*b.x[k][j];
temp.x[i][j]%=mod;
}
return temp;
} matrix k_powmatrix(matrix a,LL n)//矩阵快速幂
{
matrix temp;
memset(temp.x,,sizeof(temp.x));
for(int i=;i<;i++)
temp.x[i][i]=; while(n)
{
if(n&)
temp=mutimatrix(temp,a); a=mutimatrix(a,a);
n>>=;
}
return temp;
} int main()
{
LL n;
while(scanf("%lld",&n)!=EOF)
{
//前面四个手算下
if(n==)
{
printf("1\n");
continue;
}
if(n==)
{
printf("5\n");
continue;
}
if(n==)
{
printf("11\n");
continue;
}
if(n==)
{
printf("36\n");
continue;
} matrix st;
memset(st.x,,sizeof(st.x));
st.x[][]=;
st.x[][]=;
st.x[][]=;
st.x[][]=-; st.x[][]=;
st.x[][]=;
st.x[][]=; matrix init;//初始矩阵
memset(init.x,,sizeof(init.x)); init.x[][]=;
init.x[][]=;
init.x[][]=;
init.x[][]=; st=k_powmatrix(st,n-);//经过n-4次相乘
st=mutimatrix(init,st);//然后再乘上初始矩阵 printf("%lld\n",(st.x[][]+mod)%mod);
}
return ;
}
2018-08-09