斐波那契数列问题的递归和动态规划3

归纳递推数组 ,

代入初始值，求解状态矩阵 。

所以， 。

用快速幂将时间复杂度降到 。

import java.util.*;
public class Main {

    public static final int mod = 1_000_000_007;

    public static long[][] multiply(long[][] matrix1, long[][] matrix2) {
        long[][] res = new long[matrix1.length][matrix1.length];

        for (int i = 0; i < matrix1.length; i++) {
            for (int j = 0; j < matrix1.length; j++) {
                long sum = 0;
                for (int k = 0; k < matrix1.length; k++)
                    sum = (sum + (matrix1[i][k] * matrix2[k][j]) % mod) % mod;
                res[i][j] = sum;
            }
        }
        return res;
    }

    public static long[][] powerN(long N, long[][] matrix) {
        long[][] res = new long[matrix.length][matrix.length];
        for (int i = 0; i < res.length; i++) 
            res[i][i] = 1;
        while (N != 0) {
            if ((N & 1) == 1) {
                res = multiply(res, matrix);
            }
            matrix = multiply(matrix, matrix);
            N = N >>> 1;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        sc.close();
        if (N < 1) {
            System.out.println(0);
            return;
        }
        if (N == 1 || N == 2 || N == 3) {
            System.out.println(N);
            return;
        }
        long[][] matrix = {{1, 1, 0}, {0, 0, 1}, {1, 0, 0}};
        long[][] res = powerN(N - 3, matrix);
        System.out.println((3 * res[0][0] + 2 * res[1][0] + res[2][0]) % mod);
    }
}