poj 3734 Blocks

从左边开始染色，到第$i$个方块为止，红绿都是偶数的方案数为$a_i$，红绿恰有一个是偶数的方案为$b_i$，红绿都是奇数的方案为$c_i$，从而有如下状态转移方程：

$a_{i+1} = 2 imes a_i + b_i$

$b_{i+1} = 2 imes a_i + 2 imes b_i + 2 imes c_i$

$c_{i+1} = b_i + 2 imes c_i$

从而可以用矩阵表示：

egin{equation} left( egin{array}{c} a_i \ b_i \ c_i end{array} ight) = left( egin{array}{ccc} 2 & 1 & 0 \ 2 & 2 & 2 \ 0 & 1 & 2 end{array} ight)^i left( egin{array}{c} 1\ 0\ 0\ end{array} ight) end{equation}

最终使用矩阵的快速幂即可求解。

 1 #define     MOD 10007
 2 #define     M 3
 3 #include  <cstdio>
 4 #include  <cstdlib>
 5 #include  <iostream>
 6 #include  <cstring>
 7 int N;
 8 using namespace std;
 9 class Matrix
10 {
11     public:
12         int a[M][M];
13         Matrix(bool init = 0)
14         {
15             memset(a, 0, sizeof(a));
16             if( init == 1 )
17             {
18                 for( int i = 0 ; i < M ; i++ )
19                 {
20                     a[i][i] = 1;
21                 }
22             }
23         }
24         int * operator [](int i)
25         {
26             return a[i];
27         }
28         const int * operator [](int i)const
29         {
30             return a[i];
31         }
32 };
33 Matrix A;
34 void add(int &a, int b)
35 {
36     a += b;
37     while( a >= MOD )
38     {
39         a -= MOD;
40     }
41 }
42 Matrix operator * (const Matrix &a, const Matrix &b)
43 {
44     Matrix c;
45     for( int i = 0 ; i < M ; i++ )
46     {
47         for( int j = 0 ; j < M ; j++ )
48         {
49             for( int k = 0 ; k < M ; k++ )
50             {
51                 add(c[i][k], 1ll * a[i][j] * b[j][k] %MOD);
52             }
53         }
54     }
55     return c;
56 }
57 Matrix quick_pow(Matrix m, int n)
58 {
59     Matrix ans(1);
60     while( n )
61     {
62         if( n & 1 )
63         {
64             ans = ans * m;
65         }
66         n = n>>1;
67         m = m * m;
68     }
69     return ans;
70 }
71 void solve()
72 {
73     Matrix ans;
74     ans = quick_pow(A, N);
75     printf ( "%d
", ans[0][0]);
76 }
77 int main(int argc, char *argv[])
78 {
79     int T;
80     scanf ( "%d", &T );
81     A[0][0] = 2, A[0][1] = 1;
82     A[1][0] = 2, A[1][1] = 2, A[1][2] = 2;
83     A[2][1] = 1, A[2][2] = 2;
84     while( T-- )
85     {
86         scanf ( "%d", &N );
87         solve();
88     }
89 }