首页 > 专题系列 > Java解POJ > POJ 3233 Matrix Power Series [解题报告] Java
2013
11-12

POJ 3233 Matrix Power Series [解题报告] Java

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.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();
 }
}

  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