牛客网 又见斐波那契（快速幂矩阵）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int mod=1000000007;
 4 struct qx
 5 {
 6    long long ma[6][6]=
 7     {
 8        {1,1,1,1,1,1},
 9        {1,0,0,0,0,0},
10        {0,0,1,3,3,1},
11        {0,0,0,1,2,1},
12        {0,0,0,0,1,1},
13        {0,0,0,0,0,1}
14     };
15 };
16 void create(qx &in)
17 {
18     in.ma[0][0]=1;
19     in.ma[1][0]=0;
20     in.ma[2][0]=8;
21     in.ma[3][0]=4;
22     in.ma[4][0]=2;
23     in.ma[5][0]=1;
24 }
25 qx qu(qx a,qx b,int g,int h,int p)
26 {
27     qx res;
28     for(int i=0;i<g;i++)
29     {
30         for(int j=0;j<p;j++)
31         {
32             res.ma[i][j]=0;
33             for(int k=0;k<h;k++)
34             {
35                 res.ma[i][j]+=(a.ma[i][k]*b.ma[k][j])%mod;
36             }
37             res.ma[i][j]%=mod;
38         }
39     }
40     return res;
41 }
42 qx pow11(long long  x)
43 {
44     qx b,res;
45     while(x)
46     {
47         if(x&1)
48         {
49            res=qu(res,b,6,6,6);
50         }
51         b=qu(b,b,6,6,6);
52         x=x>>1;
53     }
54     return res;
55 }
56 int main()
57 {
58     long long  T,n;
59     cin>>T;
60     for(int i=1;i<=T;i++)
61     {
62          cin>>n;
63          if(n==1||n==0)
64          {
65              cout<<n<<endl;
66              continue;
67          }
68          qx initial;
69          create(initial);
70          qx ans=qu(pow11(n-2),initial,6,6,1);
71          cout<<ans.ma[0][0]<<endl;
72     }
73     return 0;
74 }