模快

【模板】矩阵快速幂

题目背景概述

【一个 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} 均为整数。

当两个矩阵 A 和 B 的尺寸分别为 m \times n 和 n \times p 时，它们之间可以进行乘法运算，结果将形成一个尺寸为 m \times p 的新矩阵。设该结果矩阵为 C，则其任意位置上的元素满足如下表达式：

c_{i j} = \sum_{k = 1}^{n} a_{i k} b_{k j} \text{,\qquad(1 \le i \le m, 1 \le j \le p).}

然而，若矩阵 A 的列数与矩阵 B 的行数不一致，则无法执行乘法操作。

通过验