poj3734 Blocks

思路：
递推 + 快速幂优化。
实现：
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <vector> 
 4 using namespace std;
 5 typedef vector<vector<int> > matrix;
 6 
 7 const int MOD = 10007;
 8 
 9 matrix multiply(matrix & a, matrix & b)
10 {
11     matrix c(a.size(), vector<int>(b[0].size()));
12     for (int i = 0; i < a.size(); i++)
13     {
14         for (int k = 0; k < a[0].size(); k++)
15         {
16             for (int j = 0; j < b[0].size(); j++)
17             {
18                 c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
19             }
20         }
21     }
22     return c;
23 }
24 
25 matrix pow(matrix & a, long long n)
26 {
27     matrix res(a.size(), vector<int>(a[0].size()));
28     for (int i = 0; i < a.size(); i++)
29     {
30         res[i][i] = 1;
31     }
32     while (n > 0)
33     {
34         if (n & 1)
35             res = multiply(res, a);
36         a = multiply(a, a);
37         n >>= 1;
38     }
39     return res;
40 }
41 int main()
42 {
43     int t;
44     long long n;
45     cin >> t;
46     while (t--)
47     {
48         scanf("%lld", &n);
49         matrix a(3, vector<int>(3));
50         a[0][0] = 2; a[0][1] = 1; 
51         a[1][0] = 2; a[1][1] = 2; a[1][2] = 2;
52                      a[2][1] = 1; a[2][2] = 2;
53         a = pow(a, n);
54         matrix b(3, vector<int>(1));
55         b[0][0] = 1;
56         b[1][0] = 0;
57         b[2][0] = 0;
58         a = multiply(a, b);
59         cout << a[0][0] << endl;
60     }
61     return 0;    
62 }