- 科技
- [java模板] 矩阵快速幂
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
;
}
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
];
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
;
}
}
