矩阵快速幂算法

矩阵快速幂的介绍

　　先说说和矩阵快速幂在思想上一致的快速幂算法：对于计算函数 $\displaystyle F(x)=a^{x}$ 的某个函数值，我们不必让计算机去进行 $x$ 次乘法，而是可以通过将其拆解为两个相同的部分的乘积(也就是某个数的平方)，从而减少不必要的计算。比如要计算 $2^8$ 的值，完全没有必要通过 $2*2*2*…*2$ 依次得出 $2^1,2^2,2^3,…,2^8$的值。而是可以转换为 $(((2^1)^2)^2)^2$ ，与前者不同的是，后者进行平方运算时只需要知道 $2^1,2^2,2^4,2^8$ 这少数的几个值。不难看出，快速幂算法快就快在它避免了不必要的计算，将一个表达式尽可能拆解为两个相同的数的积，当得到了其中一方的值时就不需要再去计算另一方了。如果无法拆解，那么在这一层当中可以单独抽离出一份来做乘法，比如 $2^9$ 可以写为 $(2^4)^2 * 2^1$。
　　同样的，对于矩阵的幂运算，也可以用这样的方式来进行优化，当然，前提是这个矩阵的行列条件可以执行幂运算。如果你还不清楚什么是矩阵，矩阵如何做运算，那么可以先去了解一点线性代数相关的内容。
　　在平时遇到的算法题当中，需要用到快速幂的地方通常一眼就能够看出来，毕竟很多题你看一看就意识到哪里要进行幂运算了。但是矩阵快速幂则有点不同，虽然二者思想一致，实现起来也都不算难，但是没有一定经验的人或许根本就看不出来某个地方居然还可以用矩阵来运算，更不用提矩阵快速幂了。
　　因此我个人认为，要在算法中利用到矩阵快速幂，关键点并不在于算法本身，而是你能否将一个问题转换为矩阵的幂运算的问题。

经典例子——斐波那契数列

　　斐波那契数列就是前两项为 $1$ ，从第 $3$ 项开始的任意第 $i$ 项的值都等于 第 $i-1$ 和第 $i-2$ 项之和的数列。由于前两项是固定值，那么后面的所有项其实也都是固定值。当然，某些题目中可能会让前两项变为其他的值，不过我们现在要谈论的东西不会因为前两项是什么值而受到影响，我们要关注的只是它这个 “从第三项开始的每一项都等于前两项之和”的特性。
　　假设现在有这样一个编程问题，给定一个具有斐波那契数列性质的数列 $A = a_1,a_2,a_3…$ ，不过 $a_1$ 和 $a_2$ 的值不会在题目中就告诉你，而是在程序执行后输入到程序中。那么，你如何设计程序得到某个指定位置的项 $a_n$ (这个 $n$ 也是在输入中给出)的值？
　　当这个 $n$ 不会很大时，完全可以开一个足够大的数组，然后把前两项的值写进去，剩余的项依次推导得到，直到计算得到第 $n$ 项的值。如果再有一点节省内存的意识，完全可以只开几个变量来存储需要用到的前 $2$ 项和待计算项，就不用开个这么大的数组了。
　　但是，有的时候问题会比这个还更加刁钻，会给出一个比较大的 $n$ (可能达到 $10^{18}$ 这个数量级)，并且还要求你能够在数秒之内给出结果，不过，由于答案很大，这样的题目一般会让我们对结果的数值对一个数取余数。取余数的目的是让我们不用花心思在“如何存储一个超出了基本变量所能存储的最大值的数”这样的问题上，毕竟高精度计算不是这道题考察的重点。回到题目本身，如果依然使用递推的方式来一项一项地推导，根据当前计算机的算力，是没办法在数秒之内给出结果的(本句话写于2023年)。因此，需要一些手段来更快地计算出结果，这个手段正是矩阵快速幂。这题看上去只看得到它有计算，看不出来哪里有矩阵，不过它确实可以通过构造出矩阵来进行计算得到相同的效果。
我们构造这样一个矩阵 $T$ ：

$$
\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}
$$

再拿目前已经知道的前两项 $a_1, a_2$ 构造出另一个矩阵 $B$ ：

$$
\begin{bmatrix}
a_2\\
a_1
\end{bmatrix}
$$

然后我们让它们两个相乘(注意矩阵乘法的两方不能交换位置)：

$$
\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}
\begin{bmatrix}
a_2\\
a_1
\end{bmatrix}
\text{=}
\begin{bmatrix}
a_1+a_2\\
a_2
\end{bmatrix}
\Rightarrow
\begin{bmatrix}
a_3\\
a_2
\end{bmatrix}
$$

这样，我们就得出了 $a_3$ 的值，同样的，如果我们要得到 $a_4$ 的值，就只需要再左乘一次矩阵 $T$ 即可。如果我们希望计算到 $a_n$ ，就是用矩阵 $B$ 左乘 $n-2$ 次矩阵 $T$ ，也就是 $T^{n-2} B$ 。如果止步于此，那么这只会是个比之前的递推还要更复杂且费时间的算法，但是现在它已经符合了矩阵快速幂的条件，我们可以用矩阵快速幂来加快计算 $T^{n-2}$ 过程，得到结果之后再去右乘矩阵 $B$ ，就得出了 $a_n$ 的值。