Blocks 推出矩阵公式。矩阵快速密

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Blocks

设涂到第I块时,颜色A，B都为偶数的数量为ai,一奇一偶的数量为bi,都为奇数为ci，那么涂到第i+1快时有

a[i+1]=2*a[i]+b[i]+0*c[i];

b[i+1]=2*a[i]+2*b[i]+2*c[i];

C[i+1]=0*a[i]+b[i]+2*c[i];

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <string>
 7 #include <vector>
 8 #include <set>
 9 #include <map>
10 #include <stack>
11 #include <queue>
12 #include <sstream>
13 #include <iomanip>
14 using namespace std;
15 typedef long long LL;
16 const int INF=0x4fffffff;
17 const double EXP=1e-5;
18 const int MS=10;
19 const int SIZE=1000;
20 
21 const int mod=10007;
22 
23 typedef vector<vector<int> > mat;
24 
25 
26   //  calc   A*B
27 
28 mat mul(mat &A,mat &B)
29 {
30   mat C(A.size(),vector<int>(B[0].size()));
31 
32   for(int i=0;i<A.size();i++)
33   {
34         for(int k=0;k<B.size();k++)
35         {
36               for(int j=0;j<B[0].size();j++)
37               {
38                     C[i][j]=(C[i][j]+(LL)A[i][k]*B[k][j])%mod;    //  note   overflow
39               }
40         }
41   }
42   return C;
43 }
44 
45   //   calc  A^n
46 
47 
48   mat pow(mat A,LL n)
49   {
50         mat B(A.size(),vector<int>(A[0].size()));
51         for(int i=0;i<A.size();i++)
52             B[i][i]=1;
53         while(n>0)
54         {
55               if(n&1)
56                   B=mul(B,A);
57               A=mul(A,A);
58               n>>=1;
59         }
60         return B;
61   }
62 
63   LL n;
64 void solve()
65 {
66       mat A(3,vector<int>(3));
67       A[0][0]=2;A[0][1]=1;A[0][2]=0;
68       A[1][0]=2;A[1][1]=2;A[1][2]=2;
69       A[2][0]=0;A[2][1]=1;A[2][2]=2;
70       A=pow(A,n);
71       printf("%d
",A[0][0]);
72 }
73 
74 int main()
75 {
76       int T;
77       scanf("%d",&T);
78       while(T--)
79       {
80             scanf("%lld",&n);
81             solve();
82       }
83       return 0;
84 }