f(n) = f(n-1) + f(n-2) f(n-1) = f(n-1) 矩阵: [ f(n) ] = [ 1*f(n-1) + 1*f(n-2) ] = [ 1 1 ] * [ f(n-1) ] [ f(n-1) ] [ 1*f(n-1) + 0*f(n-2) ] [ 1 0 ] [ f(n-2) ] 显然: [ f(2) ] = [ 1 ] [ f(1) ] [ 1 ] 假设: mul = [ 1 1 ] [ 1 0 ] 那么: [ f(n) ] = mul * [ f(n-1) ] = mul * mul * [ f(n-2) ] = ... = mul^(n-2) * [ f(2) ] [ f(n-1) ] [ f(n-2) ] [ f(n-3) ] [ f(1) ] 转变为快速幂问题: 快速求 mul^(n-2) 的值即可
#include <cstring> using std::memcpy; using std::memset; #include <iostream> using std::ostream; using std::endl; template<typename T> /** * 矩阵类 * @tparam T 类型参数 */ class matrix { public: int row;//行 int column;//列 T **data;//数据 public: matrix(int r, int c) : row(r), column(c) { data = new T *[r]; for (int i = 0; i < r; ++i) { data[i] = new T[c]; memset(data[i], 0, column * sizeof(*data[i])); } } matrix(const matrix &m) : row(m.row), column(m.column) { data = new T *[row]; for (int i = 0; i < row; ++i) { data[i] = new T[column]; memcpy(data[i], m.data[i], column * sizeof(*data[i])); } } matrix(int r, int c, T **m) : row(r), column(c) { data = new T *[row]; for (int i = 0; i < row; ++i) { data[i] = new T[column]; memcpy(data[i], m[i], column * sizeof(*data[i])); } } matrix &operator=(const matrix &m) { if (&m == this) { return *this; } for (int i = 0; i < row; ++i) { delete[] data[i]; } delete[] data; row = m.row; column = m.column; data = new T *[row]; for (int i = 0; i < row; ++i) { data[i] = new T[column]; memcpy(data[i], m.data[i], column * sizeof(*data[i])); } return *this; } bool operator==(const matrix &m) const { if (row != m.row || column != m.column) { return false; } for (int r = 0; r < row; ++r) { for (int c = 0; c < column; ++c) { if (m[r][c] != data[r][c]) { return false; } } } return true; } inline bool operator!=(const matrix &m) const { return !operator==(m); } inline matrix operator*(const matrix &m) { return multiply(m); } inline matrix &operator*=(const matrix &m) { *this = multiply(m); return *this; } /** * 矩阵乘法 * @param m 被乘数 * @return 结果 */ matrix multiply(const matrix &m) { matrix<T> c(row, m.column); for (int i = 0; i < row; ++i) { for (int k = 0; k < m.row; ++k) { for (int j = 0; j < m.column; ++j) { c[i][j] = (c[i][j] + data[i][k] * m[k][j]); } } } return c; } /** * 矩阵乘法 * @param m 被乘数 * @param mod 结果太大的时候求mod * @return 结果 */ matrix multiply(const matrix &m, T mod) { matrix<T> c(row, m.column); for (int i = 0; i < row; ++i) { for (int k = 0; k < m.row; ++k) { for (int j = 0; j < m.column; ++j) { c[i][j] = (c[i][j] + data[i][k] * m[k][j]) % mod; } } } return c; } /** * 求矩阵m的n次幂 * 注意m.row == m.column * @param n n次幂 * @return 结果 */ matrix pow(unsigned long long n) { matrix<T> m = *this; matrix<T> res(m.row, m.row); for (int i = 0; i < m.row; ++i) { res[i][i] = 1; } while (n > 0) { if (n & (unsigned)1) { res = res.multiply(m); } m = m.multiply(m); n >>= 1; } return res; } /** * 求矩阵m的n次幂 * 注意m.row == m.column * @param n n次幂 * @param mod 结果太大的时候求mod * @return 结果 */ matrix pow(unsigned long long n, T mod) { matrix<T> m = *this; matrix<T> res(m.row, m.row); for (int i = 0; i < m.row; ++i) { res[i][i] = 1; } while (n > 0) { if (n & (unsigned)1) { res = res.multiply(m, mod); } m = m.multiply(m, mod); n >>= 1; } return res; } ~matrix() { for (int i = 0; i < row; ++i) { delete[] data[i]; } delete[] data; } T *&operator[](int r) const { return data[r]; } friend ostream &operator<<(ostream &os, const matrix &m) { os << "matrix : "; for (int i = 0; i < m.row; ++i) { if (i != 0) { os << " "; } for (int j = 0; j < m.column; ++j) { os << m[i][j] << " "; } os << endl; } return os; } }; template<typename T> T fast_fibonacci(unsigned long long n, T mod) { matrix<T> m(2, 2); m[0][0] = 1; m[0][1] = 1; m[1][0] = 1; m[1][1] = 0; m = m.pow(n, mod); return m[1][0]; } #include <iostream> using std::cout; using std::cin; unsigned long long m = 1e9 + 7; int main(){ unsigned long long n = 0; cin >> n; cout << fast_fibonacci(n,m) << endl; }
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 <= 2){ System.out.println(1); // 小于等于2直接输出 }else{ long p = n - 2; 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((res[1][0] + res[1][1]) % mod); } }
本题的输入非常大,需要将左神的代码转为大数类型
import java.math.BigInteger; import java.util.Scanner; public class Main { static int mod = 1000000007; static long n; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextLong(); BigInteger res = f(n); System.out.println(res); } private static BigInteger f(long n) { if (n <= 2) return BigInteger.ONE; BigInteger[][] base = {{BigInteger.ONE, BigInteger.ONE}, {BigInteger.ONE, BigInteger.ZERO}}; BigInteger[][] res = matrixPower(base, n - 2); return (res[0][0].add(res[1][0])).mod(new BigInteger(String.valueOf(mod))); } private static BigInteger[][] matrixPower(BigInteger[][] m, long p) { BigInteger[][] res = new BigInteger[m.length][m[0].length]; //初始化res for (int i = 0; i < res.length; i++) { for (int j = 0; j < res[0].length; j++) { if (i == j) { res[i][j] = BigInteger.ONE; } else { res[i][j] = BigInteger.ZERO; } } } BigInteger[][] tmp = m; while (p > 0) { if ((p & 1) == 1) res = muliMatrix(res, tmp); tmp = muliMatrix(tmp, tmp); p >>= 1; } return res; } private static BigInteger[][] muliMatrix(BigInteger[][] m1, BigInteger[][] m2) { BigInteger[][] res = new BigInteger[m1.length][m2[0].length]; for (int i = 0; i < res.length; i++) { for (int j = 0; j < res[0].length; j++) { res[i][j] = BigInteger.ZERO; } } for (int i = 0; i < m1.length; i++) { for (int j = 0; j < m2[0].length; j++) { for (int k = 0; k < m2.length; k++) { res[i][j] = (res[i][j].add(m1[i][k].multiply(m2[k][j]))).mod(new BigInteger(String.valueOf(mod))); } } } return res; } }