import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { final static int MOD = 1000000007; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); long n = Long.parseLong(br.readLine()); long[][] base = {{1, 1}, {1, 0}}; long[][] res = {{1, 0}, {0, 1}}; // 单位矩阵 if(n <= 3){ System.out.println(n); // 小于等于3直接输出 }else{ long p = n - 1; for(; p != 0; p >>= 1){ if((p & 1) != 0) res = multiMat2D(res, base); base = multiMat2D(base, base); } System.out.println((res[0][0] + res[1][0]) % MOD); } } private static long[][] multiMat2D(long[][] A, long[][] B) { return new long[][]{{(A[0][0] * B[0][0] % MOD) + (A[0][1] * B[1][0] % MOD), (A[0][0] * B[0][1] % MOD) + (A[0][1] * B[1][1] % MOD)}, {(A[1][0] * B[0][0] % MOD) + (A[1][1] * B[1][0] % MOD), (A[1][0] * B[0][1] % MOD) + (A[1][1] * B[1][1] % MOD)}}; } }
求出二阶递推数列 的状态矩阵。
用矩阵快速幂求解矩阵幂。
注意到N的范围 ,用8个字节整数表示。
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) { System.out.println(1); return; } long[][] matrix = {{1, 1}, {1, 0}}; long[][] res = powerN(N - 1, matrix); System.out.println((2 * res[0][1] + res[1][1]) % mod); } }