洛谷P3390题,矩阵快速幂模板题,Java代码本地调试没有问题,提交上去就是Runtime Error,有没有好心人帮忙解答一下~
链接:https://www.luogu.com.cn/problem/P3390
洛谷平台用的JDK8,不知道是不是不兼容~
我的代码:
import java.util.Scanner;
public class Main {
public static final long mod = 1000000007;
public static long[][] matrixMultiply(long[][] matrixA, long[][] matrixB) {
int n = matrixA.length, p = matrixB.length, m = matrixB[0].length;
if (p != matrixA[0].length)
return null;
long[][] ans = new long[n][m];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
for (int k = 0; k < p; k++)
ans[i][j] += (matrixA[i][k] % mod) * (matrixB[k][j] % mod) % mod;
return ans;
}
public static long[][] fastMatrixPow(long[][] matrix, long k) {
int len = matrix.length;
long[][] res = new long[len][len];
for (int i = 0; i < len; i++)
res[i][i] = 1;
while (k > 0) {
if ((k & 1) == 1)
res = matrixMultiply(res, matrix);
matrix = matrixMultiply(matrix, matrix);
k = k >> 1;
}
return res;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long k = sc.nextInt();
long[][] matrix = new long[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
matrix[i][j] = sc.nextInt();
sc.close();
long[][] res = fastMatrixPow(matrix, k);
for (int i = 0; i < n; i++) {
if (i != 0)
System.out.println("");
for (int j = 0; j < n; j++)
System.out.print(res[i][j] + " ");
}
}
}