POJ.3734 Blocks

1.Problem
http://poj.org/problem?id=3734

2.Idea
Using dp and fast power.

3.Source

 typedef vector<int> vec;  
 typedef vector<vec> mat;  
 const int M = 10007;  
 mat mul(mat &A, mat &B) {  
      mat C(A.size(), vec(B[0].size()));  
      for (int i = 0; i < A.size(); i++)  
           for (int k = 0; k < B.size(); k++)  
                for (int j = 0; j < B[0].size(); j++) {  
                     C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % M;  
                }  
      return C;  
 }  
 mat pow(mat A, ll n)  
 {  
      mat B(A.size(), vec(A[0].size()));  
      for (int i = 0; i < A.size(); i++) {  
           B[i][i] = 1;  
      }  
      while (n) {  
           if (n & 1) B = mul(B, A);  
           A = mul(A, A);  
           n >>= 1;  
      }  
      return B;  
 }  
 int N;  
 void solve()  
 {  
      mat A(3, vec(3));  
      A[0][0] = 2; A[0][1] = 1; A[0][2] = 0;  
      A[1][0] = 2; A[1][1] = 2; A[1][2] = 2;  
      A[2][0] = 0; A[2][1] = 1; A[2][2] = 2;  
      A = pow(A, N);  
      cout << A[0][0] << endl;  
 }  
 int main()  
 {  
      int t;  
      cin >> t;  
      while (t--) {  
           cin >> N;  
           solve();  
      }  
      return 0;  
 }