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)}}; } }
#include<bits/stdc++.h> #define ll long long #define p 1000000007 using namespace std; ll n; map<ll,ll> mp; ll calc(ll n){ if(mp[n])return mp[n]; ll tmp = n; n/=2; if (tmp%2) return mp[tmp]=calc(n)*calc(n)%p+calc(n+1)*calc(n+1)%p; else return mp[tmp]=(2*calc(n-1)%p+calc(n)%p)*calc(n)%p; } int main(){ scanf("%lld", &n); mp[1] = 1; mp[2] = 1; cout<<calc(n+1)%p; return 0; }
#include <bits/stdc++.h> using namespace std; const long long MOD=1e9+7; long long n; void mat_mul(long long a[2][2],long long b[2][2]){ long long tmp[2][2]; int i,j,k; memset(tmp,0,sizeof(tmp)); for(i=0;i<2;i++){ for(j=0;j<2;j++){ for(k=0;k<2;k++){ tmp[i][j]+=b[i][k]*a[k][j]%MOD; tmp[i][j]=tmp[i][j]%MOD; } } } memcpy(a,tmp,sizeof(tmp)); } long long slove(long long n){ long long ret[2][2]={{0,1},{1,1}}; long long dp[2][2]={{1,0},{2,0}}; while(n){ if(n&1) mat_mul(dp,ret); mat_mul(ret,ret); n>>=1; } return dp[1][0]; } int main(){ scanf("%lld",&n); printf("%lld",slove(n-2)); return 0; }
import java.util.*; public class Main{ static long modv = 1000000007; static long [][] mulMatrix(long [][] a, long [][] b){ int row = a.length; int col = b[0].length; /*(a,b)*(b,c) = (a,c)*/ int num = a[0].length; long [][] res = new long[row][col]; for(int i = 0;i < row;++i) for(int j = 0;j < col;++j){ res[i][j] = 0; // 这个可以不用java默认是0 for(int k = 0;k < num;++k) // a的行 * b的列 res[i][j] = (res[i][j]+( (a[i][k] % modv) * (b[k][j] % modv) ) % (modv))%modv; } return res; } static long [][] matrixPower(long [][] m,long p){ int num = m.length; long [][] res = new long[num][num]; for(int i = 0;i < num;++i) /*单位矩阵*/ res[i][i] = 1; long [][] tmp = m; // 注意这里 p >>= 1 不能用 p /= 2替代 for(;p > 0;p >>= 1){ // 如果是奇数,开始和结束会调用一次,偶数只有最后调用一次 if((p&1) == 1){ res = mulMatrix(res,tmp); } tmp = mulMatrix(tmp,tmp); } return res; } public static void main(String [] args){ Scanner input = new Scanner(System.in); long n = input.nextLong(); if(n == 2 || n == 1){ System.out.printf("%l\n",n); return; } long [][] t_m = {{1,1},{1,0}}; long [][] start = {{2},{1}}; long [][] tmp = matrixPower(t_m,n-2); tmp = mulMatrix(tmp,start); // System.out.println(tmp[0][0]); // Java中没有%ld 和 %d这种写法 System.out.printf("%d\n",tmp[0][0]); } }
求出二阶递推数列 的状态矩阵。
用矩阵快速幂求解矩阵幂。
注意到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); } }
package main import "fmt" type SQ struct { m,n int data [][]int } func mul(a SQ,b SQ) [][]int{ res := [][]int{} for i :=0;i<a.n;i++ { t := []int{} for j :=0;j<b.m;j++ { r := 0 for k:=0;k<a.m;k++ { r += a.data[i][k]*b.data[k][j] r=r%1000000007 } t = append(t, r) } res = append(res,t) } return res } func fibonacci(n int) int { sum:=SQ{ m:2, n:2, data:[][]int{ {1,0}, {0,1}, }, } a:=SQ{ m:2, n:2, data:[][]int{ {1,1}, {1,0}, }, } for n>0{ if n&1==1{ sum.data=mul(a,sum) } a.data=mul(a,a) n>>=1 } return sum.data[0][0] } func main(){ var n int fmt.Scan(&n) fmt.Println(fibonacci(n)) }
import java.util.Scanner; public class Main { /** * 矩阵乘法 * @param A * @param B * @return */ static long MAX = (long) (1e9 + 7); static long[][] dot(long[][] A, long[][] B) { assert (A[0].length == B.length); long tmp; long[][] R = 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 < A[0].length; k++) { R[i][j]+= A[i][k]* B[k][j]; } R[i][j] = (long) (R[i][j]%MAX); } } return R; } /** * 矩阵快速幂模 * @param a * @param b * @return */ public static long[][] quickMod(long[][] a, long b) { long[][] ans = new long[2][2]; b=b-2; //初始化为单位矩阵 for(int i=0;i<2 ;++i) { ans[i][i] = 1; } //计算矩阵乘法 while (b != 0) { if ((1 & b) == 1) { ans = dot(ans, a); } b >>= 1; a = dot(a , a) ; } return ans; } /** * 斐波那契通用公式: * {F(n),F(n-1)} = {{1, 0,1}, {1,0, 0},{0,1,0}}^(n-3) * {F(3),F(2),F(1)} * @param args */ public static void main(String[] args) { long[][] A = new long[][]{{1, 1}, {1, 0}}; long[][] B = new long[2][2]; Scanner scanner = new Scanner(System.in); long n = scanner.nextLong(); if (n > 2) { B= quickMod(A,n); long rs = (long) (2*B[0][0]+B[0][1])%MAX; System.out.println(rs); } else { System.out.println(n); } } }
#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+1,m) << endl; }