洛谷P3390矩阵快速幂

【模板】矩阵快速幂

题目背景概述

一个 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，它们之间可以进行乘法运算，所得结果是一个大小为 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