2013
11-12

# Matrix Power Series

Given a n × n matrix A and a positive integer k, find the sum S = A + A2 + A3 + … + Ak.

The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 109) and m (m < 104). Then follow n lines each containing n nonnegative integers below 32,768, giving A’s elements in row-major order.

Output the elements of S modulo m in the same way as A is given.

2 2 4
0 1
1 1

1 2
2 3

//* @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();
}
}

1. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

2. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge