快速幂是一个非常常见的优化，其将$ O(n) $的乘法优化到了$ O(\log{n}) $的级别，加快了幂运算的速度，代码实现起来也非常简单。

fast_pow( a int, b int ) {
    ret := 1;
      for ( ; b; b >>= 1 ) {
        if ( b & 1 ) 
        ret *= a;
        a *= a;
    }
  
    return ret;
}

我们都知道，快速幂的原理是利用二进制拆分指数$b$，使其形成$a^b=a^1\times a^2\times a^4...$的形式从而减少了冗余的乘法运算，那么对于同样形式的矩阵乘法$A^b$，我们是否也能采用同样的方法减少运算次数呢？答案是可以的。

斐波那契数列

斐波那契数列形如$1,1,2,3...$，其从$n=3$开始的每一项都是前两项的和，通常情况下，计算前$n$项的时间复杂度为$O(n)$，这仍然具有优化的空间。

考虑下面两个个矩阵乘法：

$$ \left[\begin{matrix}1 & 1\\1 & 0\end{matrix}\right]\left[\begin{matrix}A\\B\end{matrix}\right]=\left[\begin{matrix}A+B\\A\end{matrix}\right] $$

$$ \left[\begin{matrix}1 & 1\\1 & 0\end{matrix}\right]\left[\begin{matrix}A+B\\A\end{matrix}\right]=\left[\begin{matrix}2A+B\\A+B\end{matrix}\right] $$

我们可以发现，只要不断对原矩阵左乘一个转移矩阵$A=\left[\begin{matrix}1 & 1\\1 & 0\end{matrix}\right]$，我们恰好就可以得到一个斐波那契数列，如果需要求第$b$项，我们要求的恰好就是$A^b$左乘原矩阵$\left[\begin{matrix}A\\B\end{matrix}\right]$。

矩阵快速幂

求矩阵幂？为什么我们不可以采用和快速幂一样的思路，将$A^b$拆分成$A^1\times A^2\times A^4...$的形式呢？

matrix_fast_pow( int a, int b ) {
    ret matrix
      for ( ; b; b >>= 1 ) {
        if ( b & 1 ) 
        ret := matrix_multiply(ret, a);
        a := matrix_multiply(a, a);
    }
  
    return ret;
}

由此，我们用矩阵快速幂将求斐波那契数列的时间复杂度降低到了$O(\log{n})$的级别。