POJ.3233 Matrix Power Series

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

2.Idea
Binomial Power, DP

3.Source

 typedef vector<int> vec;  
 typedef vector<vec> mat;  
 int n, k, M;  
 mat A;  
 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;  
 }  
 void solve()  
 {  
      mat B(n * 2, vec(n * 2));  
      for (int i = 0; i < n; i++) {  
           for (int j = 0; j < n; j++) {  
                B[i][j] = A[i][j];  
           }  
           B[n + i][i] = B[n + i][n + i] = 1;  
      }  
      B = pow(B, k + 1);  
      for (int i = 0; i < n; i++) {  
           for (int j = 0; j < n; j++) {  
                int a = B[n + i][j] % M;  
                if (i == j) a = (a + M - 1) % M;  
                printf("%d%c", a, j + 1 == n ? '\n' : ' ');  
           }  
      }  
 }  
 int main()  
 {  
      cin >> n >> k >> M;  
      mat AA(n, vec(n));  
      for (int i = 0; i < n; i++) {  
           for (int j = 0; j < n; j++) {  
                int t;  
                scanf("%d", &t);  
                AA[i][j] = t;  
           }  
      }  
      A = AA;  
      solve();  
      return 0;  
 }