你写的斐波那契是O(N)的？我的可是O(logN)的

斐波那契作为动态规划入门题，大家肯定都会写，毕竟题目都把递推公式给出了，直接一个循环就结束了。

但是直接使用循环，时间复杂度是 O(N) 的，在数据量很大的情况下，也是会超时的。那能不能用 O(logN) 的做法来完成呢？可以！具体怎么做，接着看吧。

对于数列递推问题，可以使用矩阵快速幂进行加速。

矩阵快速幂用于求解一般性问题：给定大小为 n*n 的矩阵 M，求答案矩阵 M^k^，并对答案矩阵中每个元素对 MOD 取模。

对于本题而言，某个 f(n) 是从 f(n-1) 和 f(n-2) 推导而来的，即 f(n) = f(n-1) + f(n-2)，可以将其依赖的状态存成列向量：$\begin{bmatrix} f(n-1) \ f(n-2) \end{bmatrix}$

那么目标值 f(n) 所在的矩阵为：$\begin{bmatrix} f(n) \ f(n-1) \end{bmatrix}$

根据矩阵乘法可以得出：$\begin{bmatrix} f(n) \ f(n-1) \end{bmatrix} = \begin{bmatrix} 1 & 1 \ 1 & 0 \end{bmatrix} \ast \begin{bmatrix} f(n-1) \ f(n-2) \end{bmatrix}$

于是乎，可以令 $mat = \begin{bmatrix} 1 & 1 \ 1 & 0 \end{bmatrix}$

初始状态下，存在矩阵 $\begin{bmatrix} f(1) \ f(0) \end{bmatrix}$，根据斐波那契递推式可以得出：

$\begin{bmatrix} f(n) \ f(n-1) \end{bmatrix} = \underbrace{ mat \ast mat \ast \cdots \ast mat }_{n-1} \ast \begin{bmatrix} f(1) \ f(0) \end{bmatrix}$

由于矩阵乘法具有「结合律」，最终可以得出：

$\begin{bmatrix} f(n) \ f(n-1) \end{bmatrix} = mat^{n-1} \ast \begin{bmatrix} f(1) \ f(0) \end{bmatrix}$

由此，我们只需要计算 $mat^{n-1}$ 就可以求解出最终答案，这个过程可以使用矩阵快速幂来解决。

class Solution {
    static final int MOD = (int)1e9 + 7;

    public int fib(int n) {
        if(n <= 1) return n;

        long[][] mat = {
            {1, 1},
            {1, 0}
        };

        long[][] ans = new long[][] {
            {1}, // f(1)
            {0}  // f(0)
        };

        int x = n - 1; // 需要计算的轮次
        while(x != 0) {
            if((x & 1) != 0) {
                ans = mul(mat, ans); // 需要注意顺序， (2*2) * (2*1)
            }
            mat = mul(mat, mat);
            x >>>= 1;
        }
        return (int)(ans[0][0] % MOD);
    }

    // 矩阵乘法 (r*z) * (z*c) => (r*c)
    long[][] mul(long[][] a, long[][] b) {
        int r = a.length, c = b[0].length, z = b.length;
        long[][] ans = new long[r][c];
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                for(int k = 0; k < z; k++) {
                    ans[i][j] += a[i][k] * b[k][j];
                    ans[i][j] %= MOD;
                }
            }
        }
        return ans;
    }
}

时间复杂度：O(logN)
空间复杂度：O(1)

PS: 如果不想在乎传入 mul() 方法的参数顺序，可以将 ans 初始化成：
long[][] ans = new long[][] {
    {1, 0}, // f(1)
    {0, 0}  // f(0)
};
结果保持不变。

类似题目：1137. 第 N 个泰波那契数

class Solution {
    public int tribonacci(int n) {
        if(n == 0) return 0;
        if(n == 1 || n == 2) return 1;

        int[][] ans = {
            {1}, // f(2)
            {1}, // f(1)
            {0}  // f(0)
        };

        int[][] mat = {
            {1, 1, 1},
            {1, 0, 0},
            {0, 1, 0}
        };

        int x = n - 2;
        while(x != 0) {
            if((x & 1) != 0) {
                ans = mul(mat, ans);
            }
            mat = mul(mat, mat);
            x >>>= 1;
        }

        return ans[0][0];
    }

    // 矩阵乘法 (r*z) * (z*c) => (r*c)
    int[][] mul(int[][] a, int[][] b) {
        int r = a.length, c = b[0].length, z = b.length;
        int[][] ans = new int[r][c];
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                for(int k = 0; k < z; k++) {
                    ans[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        return ans;
    }
}