POJ.3420 Quad Tiling

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

2.Idea
DP + Fast Power
Credit

3.Source

 typedef long long ll;  
 typedef vector<ll> vec;  
 typedef vector<vec> mat;  
 int n, M;  
 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)) % 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 main()  
 {  
      int T[6][6] = {  
           { 1, 1, 1, 1, 0, 1 },  
           { 1, 0, 0, 1, 0, 0 },  
           { 1, 0, 0, 0, 1, 0 },  
           { 1, 1, 0, 0, 0, 0 },  
           { 0, 0, 1, 0, 0, 0 },  
           { 1, 0, 0, 0, 0, 0 }  
      };  
      mat A(6, vec(6, 0));  
      for (int i = 0; i < 6; i++) {  
           for (int j = 0; j < 6; j++) {  
                A[i][j] = T[i][j];  
           }  
      }  
      int Base[6][1] = {  
           { 1 },  
           { 1 },  
           { 1 },  
           { 1 },  
           { 0 },  
           { 1 },  
      };  
      mat B(6, vec(1, 0));  
      for (int r = 0; r < 6; r++)  
           B[r][0] = Base[r][0];  
      while (scanf("%d %d", &n, &M)) {  
           if (n == 0 && M == 0) break;  
           mat res = mul(pow(A, n - 1), B);  
           printf("%lld\n", res[0][0]);  
      }  
      return 0;  
 }