[javaテンプレート]マトリクス高速べき乗
15301 ワード
import java.util.Scanner;
public class {
static int[][] a;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
a = new int[sc.nextInt()][sc.nextInt()];
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[i].length; j++) {
a[i][j] = sc.nextInt();
}
}
int[][] c = matrix_pow(a, 200, 100);
for (int i = 0; i < c.length; i++) {
for (int j = 0; j < c.length; j++) {
System.out.print(c[i][j] + " ");
}
System.out.println();
}
}
/*
*
*/
static int[][] matrix_mul(int[][] a, int[][] b, int mod) {
if (a[0].length != b.length) {
//
return null;
}
//n m
int an = a.length, bm = b[0].length, am = a[0].length;
int[][] res = new int[an][bm];
for (int i = 0; i < an; i++) {
for (int j = 0; j < bm; j++) {
for (int k = 0; k < am; k++) {
res[i][j] = (res[i][j] + a[i][k] * b[k][j] % mod) % mod;
}
}
}
return res;
}
/*
*
*/
static int[][] matrix_pow(int[][] a, int p, int mod) {
int[][] res = new int[a.length][a.length];
// res
for (int i = 0; i < a.length; i++) {
res[i][i] = 1;
}
//
while (p != 0) {
if ((p & 1) == 1) {
res = matrix_mul(res, a, mod);
}
a = matrix_mul(a, a, mod);
p /= 2;
}
return res;
}
}