Poj Solution 3233

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

//* @author:
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);

if (lk % 2 == 1)
return re;
}

public static void main(String[] args) throws Exception {
PrintWriter out = new PrintWriter(System.out);
// ��ȡn,k,m
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++) {
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();
}
}

This entry was posted in poj. Bookmark the permalink.