11339: [yosupo] Linear Algebra - Pow of Matrix
[Creator : ]
Description
Given $N \times N$ matrix $A = \lbrace a_{ij} \rbrace$ with entries in $\mathbb{Z}/998244353\mathbb{Z}$, and a non-negative integer $K$.
print $A^K = (b_{ij})_{i,j}$.
print $A^K = (b_{ij})_{i,j}$.
Input
$N$ $K$
$a_{11}$ $a_{12}$ ... $a_{1N}$
$a_{21}$ $a_{22}$ ... $a_{2N}$
:
$a_{N1}$ $a_{N2}$ ... $a_{NN}$
$a_{11}$ $a_{12}$ ... $a_{1N}$
$a_{21}$ $a_{22}$ ... $a_{2N}$
:
$a_{N1}$ $a_{N2}$ ... $a_{NN}$
Output
$b_{11}$ $b_{12}$ ... $b_{1N}$
$b_{21}$ $b_{22}$ ... $b_{2N}$
:
$b_{N1}$ $b_{N2}$ ... $b_{NN}$
$b_{21}$ $b_{22}$ ... $b_{2N}$
:
$b_{N1}$ $b_{N2}$ ... $b_{NN}$
Constraints
- $1 \leq N \leq 200$
- $0 \leq K \leq 10^{18}$
- $0 \leq a_{ij} < 998244353$
- $0 \leq K \leq 10^{18}$
- $0 \leq a_{ij} < 998244353$
Sample 1 Input
2 7
0 1
1 1
Sample 1 Output
8 13
13 21
Sample 2 Input
3 0
0 0 0
0 0 0
0 0 0
Sample 2 Output
1 0 0
0 1 0
0 0 1