<>

<转载于 >

题目大意：

让你用1*2规格的地毯去铺4*n规格的地面，告诉你n，问有多少种不同的方案使得地面恰好被铺满且地毯不重叠。答案对1000000007取模。

解题分析：

看到题目所给n的数据这么大，就知道肯定存在递推公式，至于递推公式的具体的分析过程  >>>。求出递推公式后，由于数据太大，所以我们利用矩阵快速幂来加速。当然，如果比赛的时候想不到递推公式，我们也可以通过搜素得到前面的几组数据，然后在通过高斯消元来得到符合这些数据的公式的通解，最后再利用矩阵快速幂来求解。

 

#include 
     
       #include 
      
       #include 
       
        using namespace std; #define LL long long const int mod=1000000007; struct matrix{    LL x[4][4];};matrix mutimatrix(matrix a,matrix b){    matrix temp;     memset(temp.x,0,sizeof(temp.x));        for(int i=0;i<4;i++)    for(int j=0;j<4;j++)    for(int k=0;k<4;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,0,sizeof(temp.x));    for(int i=0;i<4;i++)    temp.x[i][i]=1;    while(n)    {        if(n&1)        temp=mutimatrix(temp,a);        a=mutimatrix(a,a);        n>>=1;    }    return temp;} int main(){        LL n;        while(scanf("%lld",&n)!=EOF)        {            //前面四个手算下            if(n==1)            {                printf("1\n");                continue;            }            if(n==2)            {                printf("5\n");                continue;            }            if(n==3)            {                printf("11\n");                continue;            }            if(n==4)            {                printf("36\n");                continue;            }        matrix st;        memset(st.x,0,sizeof(st.x));        st.x[0][0]=1;        st.x[1][0]=5;        st.x[2][0]=1;        st.x[3][0]=-1;        st.x[0][1]=1;        st.x[1][2]=1;        st.x[2][3]=1;        matrix init;//初始矩阵        memset(init.x,0,sizeof(init.x));        init.x[0][0]=36;        init.x[0][1]=11;        init.x[0][2]=5;        init.x[0][3]=1;        st=k_powmatrix(st,n-4);//经过n-4次相乘        st=mutimatrix(init,st);//然后再乘上初始矩阵        printf("%lld\n",(st.x[0][0]+mod)%mod);    }    return 0; }
       
      
     

 

2018-08-09