hdu 6185

题意：有4*n的空地，问用1*2的瓷砖铺满不重叠，方案数
思路：a[n]=a[n-1]+5*a[n-2]+a[n-3]-a[n-4]，矩阵快速幂搞搞
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const LL MOD=1e9+7;
 5 struct Matrix
 6 {
 7     LL a[4][4];
 8     Matrix()
 9     {
10         memset(a,0,sizeof(a));
11     }
12     void init()
13     {
14         for(int i=0;i<4;i++)
15             for(int j=0;j<4;j++)
16                 a[i][j]=(i==j);
17     }
18     Matrix operator + (const Matrix &B)const
19     {
20         Matrix C;
21         for(int i=0;i<4;i++)
22             for(int j=0;j<4;j++)
23                 C.a[i][j]=(a[i][j]+B.a[i][j])%MOD;
24         return C;
25     }
26     Matrix operator * (const Matrix &B)const
27     {
28         Matrix C;
29         for(int i=0;i<4;i++)
30             for(int k=0;k<4;k++)
31                 for(int j=0;j<4;j++)
32                     C.a[i][j]=(C.a[i][j]+1LL*a[i][k]*B.a[k][j])%MOD;
33         return C;
34     }
35     Matrix operator ^ (const LL &t)const
36     {
37         Matrix A=(*this),res;
38         res.init();
39         LL p=t;
40         while(p)
41         {
42             if(p&1)res=res*A;
43             A=A*A;
44             p>>=1;
45         }
46         return res;
47     }
48 };
49 Matrix base;
50 void init()
51 {
52 
53        base.a[0][0]=0;base.a[0][1]=0;base.a[0][2]=0;base.a[0][3]=-1;
54        base.a[1][0]=1;base.a[1][1]=0;base.a[1][2]=0;base.a[1][3]=1;
55        base.a[2][0]=0;base.a[2][1]=1;base.a[2][2]=0;base.a[2][3]=5;
56        base.a[3][0]=0;base.a[3][1]=0;base.a[3][2]=1;base.a[3][3]=1;
57 }
58 LL query(LL x)
59 {
60     if(x==1)return 1;
61     if(x==2)return 5;
62     if(x==3)return 11;
63     if(x==4)return 36;
64     Matrix ans=base^(x-4);
65     return ((36*ans.a[3][3]+11*ans.a[2][3]+5*ans.a[1][3]+ans.a[0][3])%MOD+MOD)%MOD;
66 }
67 int main()
68 {
69     init();
70     LL n;
71     while(~scanf("%lld",&n))
72     {
73         printf("%lld
",query(n));
74     }
75     return 0;
76 }