PKU 3735 Training little cats

http://poj.org/problem?id=3735
与えられた条件でシミュレーションしろというような問題。

愚直にやると大きいmで絶対に終わらないので、愚直を回避するためになんとかする。
どの操作も行列の掛け算で置き換えることができるので、k回のシミュレーションをまとめて表す行列を作り、繰り返し二乗法を適用しました。
ただし、C++だとどうしてもTLEを回避出来なかったので、javaに逃げさせてもらいました。
それでも結構ギリギリになりました。
0msとなるもっと簡潔な方法があるようなので、それを調べたいです。

import java.util.*;

class Main{
    public static void main(String[] args){
        new Main().run();
    }
    int n,m,k;

    long mat[][]=new long[110][110];
    long tmp[][]=new long[110][110];
    long tmp2[][]=new long[110][110];

    void matpow(long in[][],int m){
        if(m==0){
            for(int i=0;i<n+1;++i){
                Arrays.fill(in[i],0);
                in[i][i]=1;
            }
            return;
        }
        if(m==1)return;

        if((m&1)==1)for(int i=0;i<n+1;++i)tmp2[i]=(long[])in[i].clone();
        matpow(in,m/2);

        for(int i=0;i<n+1;++i){
            for(int j=0;j<n+1;++j){
                long t=0;
                for(int k=0;k<n+1;++k)t+=in[i][k]*in[k][j];
                tmp[i][j]=t;
            }
        }

        if((m&1)==1){
            for(int i=0;i<n+1;++i){
                for(int j=0;j<n+1;++j){
                    long t=0;
                    for(int k=0;k<n+1;++k)t+=tmp[i][k]*tmp2[k][j];
                    in[i][j]=t;
                }
            }
            return;
        }
        for(int i=0;i<n+1;++i)in[i]=(long[])tmp[i].clone();
    }

    
    void run(){
        Scanner cin=new Scanner(System.in);
        while(true){
            n=cin.nextInt();
            m=cin.nextInt();
            k=cin.nextInt();
            if(0==(n|m|k))break;

            String c;
            int s,t;
            for(int i=0;i<n+1;++i){
                Arrays.fill(mat[i],0);
                mat[i][i]=1;
            }

            for(int i=0;i<k;++i){
                c=cin.next();
                if(c.charAt(0)=='g'){
                    s=cin.nextInt()-1;
                    ++mat[s][n];
                }else if(c.charAt(0)=='e'){
                    s=cin.nextInt()-1;
                    Arrays.fill(mat[s],0);
                }else{
                    s=cin.nextInt()-1;
                    t=cin.nextInt()-1;
                    long[] tt=mat[s];
                    mat[s]=mat[t];
                    mat[t]=tt;
                }
            }
            matpow(mat,m);
            for(int i=0;i<n;++i)System.out.print(mat[i][n]+" ");
            System.out.println();
        }
    }
}