学习笔记 - 矩阵快速幂

· · 算法·理论

矩阵乘法

设 A 为 P \times M 的矩阵，B 为 M \times Q 的矩阵，设矩阵 C 为矩阵 A 与 B 的乘积，有 C_{i,j} = \sum_{k=1}^M A_{i,k}B_{k,j}。即 C 的每一位等于 A 中同一行的与 B 中同一列的诸乘积的和。（记忆：“左行右列”。）

矩阵乘法满足结合律，且在信息学竞赛中矩阵一般为方阵，于是可以直接用快速幂优化。

应用之例

已知 f_i 等于一个多项式，构造矩阵要将该多项式中的每个带变量的项置于矩阵中（如 f_i-1, i^2 等，有时常数项也要置 1）。

已知 f_i = f_{i - 1} + f_{i - 2} 且 f_1 = f_2 = 1，求 f_n。

f_i & f_{i-1} \end{bmatrix}$ 为 $\begin{bmatrix} f_{i-1} & f_{i-2} \end{bmatrix}$ 乘以某矩阵 $X$ 的积，要求 $X$。 由 $X$ 的行数必须与左边的列数相等为（即“左行”相反），列数必须与结果相等（即“右列”），于是确定 $X$ 为 $2 \times 2$ 的矩阵。 使用待定系数法，设 $X = \begin{bmatrix} a & b\\ c & d \end{bmatrix}$，代入原式，则有 $f_n = f_{n-1}*a + f{n-2} * c$ 且 $f_{n-1} = f_{n-1}*b + f_{n-2}*d$，解得 $a = 1, b = 1, c = 1, d = 0 1 & 1\\ 1 & 0 \end{bmatrix}

那么通过 \begin{bmatrix} f_2 & f_1 \end{bmatrix} 乘以 X^{n-2} 即可快速求得 f_n