POJ.3735 Training little cats

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

2.Idea
Fast Power of Matrix.
Good blog:http://area.hateblo.jp/entry/2013/03/18/013421
3.Source

 int N;  
 ll A[101][101], B[101][101], C[101][101];  
 void mat_mul(ll a[][101], ll b[][101], ll dst[][101]) {  
      int i, j, k;  
      memset(C, 0, sizeof(C));  
      for (i = 0; i < N + 1; i++)  
           for (k = 0; k < N + 1; k++)  
                if (a[i][k])  
                     for (j = 0; j < N + 1; j++)  
                          C[i][j] += a[i][k] * b[k][j];  
      for (i = 0; i < N + 1; i++)  
           for (j = 0; j < N + 1; j++)  
                dst[i][j] = C[i][j];  
 }  
 void mat_pow(ll A[][101], ll n) {  
      int i;  
      memset(B, 0, sizeof(B));  
      for (i = 0; i < N + 1; i++) {  
           B[i][i] = 1;  
      }  
      while (n > 0) {  
           if (n & 1) mat_mul(B, A, B);  
           mat_mul(A, A, A);  
           n >>= 1;  
      }  
 }  
 int main()  
 {  
      ll n, m, k;  
      while (scanf("%lld%lld%lld", &n, &m, &k)) {  
           if (n + m + k == 0) break;  
           N = n;  
           memset(A, 0, sizeof(A));  
           for (int i = 0; i <= n; i++) A[i][i] = 1;  
           char a[5];  
           int b, c;  
           for (int i = 0; i < k; i++) {  
                scanf("%s", &a);  
                if (a[0] == 'g') {  
                     scanf("%d", &b);  
                     A[n][b - 1]++;  
                }  
                else if (a[0] == 'e') {  
                     scanf("%d", &b);  
                     for (int i = 0; i <= n; i++) A[i][b - 1] = 0;  
                }  
                else {  
                     scanf("%d%d", &b, &c);  
                     for (int i = 0; i <= n; i++) swap(A[i][b - 1], A[i][c - 1]);  
                }  
           }  
           mat_pow(A, m);  
           for (int i = 0; i < n; i++) {  
                printf("%lld%c", B[n][i], (i == n - 1) ? '\n' : ' ');  
           }  
      }  
      return 0;  
 }