Poj Solution 3233

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

//* @author: 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main{
 static int n, k, m;
 static int[][] matrix;
 static int[][] result;

 /**
  * ������a��Ԫ�ظ��Ƶ�����һ������
  * 
  * @param a
  * @return
  */
 static int[][] copy(int[][] a) {
       int[][] re = new int[n][n];
       for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
         re[i][j] = a[i][j];
       return re;
 }

 /**
  * ���}������Ͳ�ȡ��%m
  * 
  * @param a
  * @param b
  */
 static void add(int[][] a, int[][] b) {
       for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
         a[i][j] += b[i][j];
         a[i][j] %= m;
        }
 }

 /**
  * ����}����Ļ�ȡ��%m
  * 
  * @param a
  * @param b
  * @return
  */
 static int[][] mul(int[][] a, int[][] b) {
       int[][] re = new int[n][n];
       for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
         long t = 0;
         for (int k = 0; k < n; k++) {
          t += 1L * a[i][k] * b[k][j];
         }
         re[i][j] = (int) (t % m);
        }
       return re;
 }

 /**
  * ����matrix��p����%m
  * 
  * @param p
  * @return
  */
 static int[][] powm(int p) {
       if (p == 1)
        return matrix;
       int[][] re = powm(p / 2);
       re = mul(re, re);
       if (p % 2 == 1)
        re = mul(re, matrix);
       return re;
 }

 /**
  * ����A + A2 + A3 + �� + Ak�ĺ�%m
  * 
  * @param lk
  * @return
  */
 static int[][] calc(int lk) {
       if (lk == 1)
        return copy(matrix);
       int mid = lk / 2;
       if (lk % 2 == 1)
        mid++;
  
       //����A + A2 + A3 + �� +Ai
       int[][] re1 = calc(lk / 2);
  
       //����Ai
       int[][] fac = powm(mid);
  
       int[][] re = mul(fac, re1);
  
       add(re, re1);
       if (lk % 2 == 1)
        add(re, fac);
       return re;
 }

 public static void main(String[] args) throws Exception {
       BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
       PrintWriter out = new PrintWriter(System.out);
       // ��ȡn,k,m
       String s = cin.readLine();
       String[] sa = s.split(" ");
       n = Integer.parseInt(sa[0]);
       k = Integer.parseInt(sa[1]);
       m = Integer.parseInt(sa[2]);
       matrix = new int[n][n];
       result = new int[n][n];
       for (int i = 0; i < n; i++) {
        s = cin.readLine().trim();
        sa = s.split(" ");
        for (int j = 0; j < n; j++)
         matrix[i][j] = Integer.parseInt(sa[j]);
       }
       int[][] re = calc(k);
       for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
         out.print(re[i][j] + " ");
        }
        out.println();
       }
       out.flush();
       out.close();
 }
}