10983: 洛谷P3390 -【模板】矩阵快速幂
[Creator : ]
Description
题目背景
一个 $m \times n$ 的矩阵是一个由 $m$ 行 $n$ 列元素排列成的矩形阵列。即形如$ A = \begin{bmatrix} a_{1 1} & a_{1 2} & \cdots & a_{1 n} \\ a_{2 1} & a_{2 2} & \cdots & a_{2 n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m 1} & a_{m 2} & \cdots & a_{m n} \end{bmatrix} \text{.} $
本题中认为矩阵中的元素 $a_{i j}$ 是整数。
两个大小分别为 $m \times n$ 和 $n \times p$ 的矩阵 $A, B$ 相乘的结果为一个大小为 $m \times p$ 的矩阵。将结果矩阵记作 $C$,则
$ c_{i j} = \sum_{k = 1}^{n} a_{i k} b_{k j},\qquad (1 \le i \le m, 1 \le j \le p). $
而如果 $A$ 的列数与 $B$ 的行数不相等,则无法进行乘法。
可以验证,矩阵乘法满足结合律,即 $(A B) C = A (B C)$。
一个大小为 $n \times n$ 的矩阵 $A$ 可以与自身进行乘法,得到的仍是大小为 $n \times n$ 的矩阵,记作 $A^2 = A \times A$。进一步地,还可以递归地定义任意高次方 $A^k = A \times A^{k - 1}$,或称 $A^k = \underbrace{A \times A \times \cdots \times A}_{k \text{ 次}}$。
特殊地,定义 $A^0$ 为单位矩阵 $I = \begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{bmatrix}$。
题目描述
给定 $n\times n$ 的矩阵 $A$,求 $A^k$。Input
第一行两个整数 $n,k$。
接下来 $n$ 行,每行 $n$ 个整数,第 $i$ 行的第 $j$ 的数表示 $A_{i,j}$。
接下来 $n$ 行,每行 $n$ 个整数,第 $i$ 行的第 $j$ 的数表示 $A_{i,j}$。
Output
输出 $A^k$
共 $n$ 行,每行 $n$ 个数,第 $i$ 行第 $j$ 个数表示 $(A^k)_{i,j}$,每个元素对 $10^9+7$ 取模。
共 $n$ 行,每行 $n$ 个数,第 $i$ 行第 $j$ 个数表示 $(A^k)_{i,j}$,每个元素对 $10^9+7$ 取模。
Constraints
对于 $100\%$ 的数据,$1\le n \le 100$,$0 \le k \le 10^{12}$,$|A_{i,j}| \le 1000$。
Sample 1 Input
2 1
1 1
1 1
Sample 1 Output
1 1
1 1
Sample 2 Input
5 1000000000000
5 10 234 334 837 272
1 1 1 1 1
234 111 192 834 838
594 984 378 334 888
999 777 666 555 343
Sample 2 Output
153033615 103962150 238235028 490581577 797297861
164657115 635667007 912284278 376748444 178491345
174410773 930909606 479142900 628973486 382187436
636847469 320196604 110213881 612229356 165476326
251443310 693706474 535657980 19729666 604257244