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

import java.util.*;
public class Main {
    private static final int MOD = 1000000007;

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()) {
            long n = scanner.nextLong();
            long[][] ret = matrixN(new long[][]{{1,1},{1,0}}, n - 2);
            long printRes = (ret[0][0] % MOD + ret[0][1] %MOD) %MOD;
            System.out.println(printRes);
        }
    }

    public static long[][] matrixN(long[][]a, long n) {
        long[][] ret = new long[a.length][a[0].length];
        for(int i = 0;i < ret.length;i++) {
            ret[i][i] = 1;
        }
        long[][]tmp = a;
        for(;n > 0; n >>= 1) {
            if ((n & 1) != 0) {
                ret = matrixMulti(ret, tmp);
            }
            tmp = matrixMulti(tmp, tmp); 
        }
        return ret;
    }

    public static long[][] matrixMulti(long[][]a, long[][]b) {
        long[][] ret = new long[a.length][b[0].length];
        for(int i = 0;i < a.length;i++) {
            for(int j = 0;j < b[0].length;j++) {
                for(int k = 0; k < b.length;k++) {
                    ret[i][j] = (ret[i][j] % MOD + a[i][k] % MOD * b[k][j] ) % MOD;
                }
            }
        }
        return ret;
    }


}

测试数据会超过int型，所以记得全部切换成long型即可，另外为防止long型溢出，需要按照(a+b)%c=(a%c+b%c)%c控制结果范围。