题目描述
大家都知道，斐波那契数列是满足如下性质的一个数列：
Fn =1 (n <=2)
Fn =F(n-1)+F(n-2) (n>=3)
请你求出 Fn mod 10^9 + 7 的值。
输入格式
一行一个正整数 n
输出格式
输出一行一个整数表示答案。
样例 #1
样例输入 #1
5
样例输出 #1
5
样例 #2
样例输入 #2
10
样例输出 #2
55
提示
【数据范围】
对于 60% 的数据，1<= n <= 92；
对于 100% 的数据，1<= n < 2^63。
1. //示例代码 2. #include <bits/stdc++.h> 3. using namespace std; 4. typedef long long LL; 5. const int M=1e9+7; 6. struct matrix{//矩阵结构体 7. LL c[3][3]; 8. matrix(){memset(c,0,sizeof(c));}//初始化矩阵 9. }A,res; 10. LL n; 11. matrix operator*(matrix &a,matrix &b){//原算符重载 * 12. matrix t; 13. for(int i=1;i<=2;i++) 14. for(int j=1;j<=2;j++) 15. for(int k=1;k<=2;k++)//矩阵乘法 16. t.c[i][j]=(t.c[i][j]+a.c[i][k]*b.c[k][j])%M; 17. return t; 18. } 19. void quickpow(LL n){//快速幂 20. A.c[1][1]=A.c[1][2]=A.c[2][1]=1;//初始化A矩阵 21. res.c[1][1]=res.c[1][2]=1;//初始化单位矩阵 22. while(n){ 23. if(n&1) res=res*A; 24. A=A*A; 25. n>>=1; 26. } 27. } 28. int main() 29. { 30. scanf("%lld",&n); 31. if(n<3){printf("1");return 0;} 32. quickpow(n-2);//运算 33. printf("%lld",res.c[1][1]); 34. return 0; 35. }
1. #示例代码 Python版 2. 3. # -*- coding:utf-8 -*- 4. import numpy as np 5. M=10**9+7 6. base=np.array([1,1],dtype=np.int64) 7. a=np.array([[1,1],[1,0]],dtype=np.uint64) 8. n=int(input()) 9. if n<=2: 10. print(1) 11. else: 12. k=n-2 13. res=np.array([[1,0],[0,1]],dtype=np.int64) 14. while k>0: 15. if k&1: 16. res=(np.matmul(res,a)%M).astype(np.int64) 17. a= (np.matmul(a,a)%M).astype(np.int64) 18. k>>=1 19. base = (np.matmul(base,res)%M).astype(np.int64) 20. print(base[0])
