第26节 单调栈（续）、由斐波那契数列讲述矩阵快速幂技巧

10的75次方计算如何最快？

75 -> 二进制表示位-> 1001011 -> 最高位是8

long minci = 18;
long t = 10;
long ans = 1;
while(minci != 0){
    if((minci & 1) == 1){
        ans *= t;
    }
    t = t * t;
    minci >>= 1;
}
System.out.printf("%e", (double)ans);

斐波那契数列推导公式

1）斐波那契数列的线性求解（O(N)）的方式非常好理解

2）同时利用线性代数，也可以改写出另一种表示

| F(N) , F(N-1) | = | F(2), F(1) | * 某个二阶矩阵的N-2次方

3）求出这个二阶矩阵，进而最快求出这个二阶矩阵的N-2次方

类似斐波那契数列的递归优化

如果某个递归，除了初始项之外，具有如下的形式

F(N) = C1 * F(N) + C2 * F(N-1) + … + Ck * F(N-k) ( C1…Ck 和k都是常数)

并且这个递归的表达式是严格的、不随条件转移的

那么都存在类似斐波那契数列的优化，时间复杂度都能优化成O(logN)

假设 , 而 表示 的整数部分, 设:

显见， 当 时， 有 . 对于所有 , 则 是一个非减函数.

当 及 时， 则有:

\left[ \begin{matrix} 1 \end{matrix} \right]

[F_n,F_n-1] = [F_n,F_n-1]\times\left[\begin{matrix}1 & 1 \\1 & 0\end{matrix}\right]^{n-2}

$$ [F_n,F_n-1] = [F_n,F_n-1]\times\left[\begin{matrix}1 & 1 \1 & 0\end{matrix}\right]^{n-2} $$