PS：本文章因篇幅有限，就不讲矩阵乘法和快速幂了。

题目：

$$F_n = \left{\begin{aligned} 1 \space (n \le 2) \ F_{n-1}+F_{n-2} \space (n\ge 3) \end{aligned}\right.$$

求 $F_n$。

定义一个矩阵$[Base]$，使：

$$\begin{bmatrix}F_n,F_{n+1}\end{bmatrix}\times\begin{bmatrix}Base\end{bmatrix}=\begin{bmatrix}F_{n+1},F_{n+2}\end{bmatrix}$$

那：

$$\begin{bmatrix}F_n,F_{n+1}\end{bmatrix}\times\begin{bmatrix}Base\end{bmatrix}^2=\begin{bmatrix}F_{n+2},F_{n+3}\end{bmatrix}$$

$$\begin{bmatrix}F_n,F_{n+1}\end{bmatrix}\times\begin{bmatrix}Base\end{bmatrix}^M=\begin{bmatrix}F_{n+M},F_{n+M+1}\end{bmatrix}$$

所以：

$$\begin{bmatrix}F_1,F_{2}\end{bmatrix}\times\begin{bmatrix}Base\end{bmatrix}^{n-1}=\begin{bmatrix}F_{n},F_{n+1}\end{bmatrix}$$

那我们只要找出 $\begin{bmatrix}Base\end{bmatrix}$ 就行了。

经过构造：

$$\begin{bmatrix}Base\end{bmatrix}=\begin{bmatrix}1,1\1,0\end{bmatrix}$$

$F_n$ 就是：

$$\begin{bmatrix}1,1\end{bmatrix}\times\begin{bmatrix}1,1\1,0\end{bmatrix}^{n-1}$$

我们只要得到了递推的公式，就可以找到 $[Base]$，从而加速递推。