Problem10983--洛谷P3390 -【模板】矩阵快速幂

10983: 洛谷P3390 -【模板】矩阵快速幂

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

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}$。

Output

输出 $A^k$

共 $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

HINT

洛谷P3390.

Source/Category