【学习笔记】【自学】【模板】矩阵快速幂

题目描述：给定 $n \times n$ 的矩阵 $A$，求 $A^k$。

矩阵：一个 $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{.} $$
矩阵乘法：两个大小分别为 $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} \text{    ($1 \le i \le m$, $1 \le j \le p$).} $$
矩阵的幂：一个大小为 $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}$。

快速幂：将 $x^y$ 分解为 $x^{\left\lfloor\frac{y}{2}\right\rfloor}\cdot x^{\left\lfloor\frac{y}{2}\right\rfloor} \cdot x^{y\mod 2}$。在 $y$ 较小时直接算出 $x^y$。

矩阵快速幂，顾名思义，就是将矩阵进行快速幂。

将 $A^k$ 分解为 $A^{\left\lfloor\frac{k}{2}\right\rfloor}\cdot A^{\left\lfloor\frac{k}{2}\right\rfloor} \cdot A^{k\mod 2}$ 即可求出结果。