题目背景
大家都知道，斐波那契数列是满足如下性质的一个数列：
• f(1) = 1
• f(2) = 1
• f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数)
题目描述
请你求出 f(n) mod 1000000007 的值。
输入输出格式
输入格式：
·第 1 行：一个整数 n
输出格式：
第 1 行： f(n) mod 1000000007 的值
输入输出样例
输入样例#1：
5
输出样例#1：
5
输入样例#2：
10
输出样例#2：
55
说明
对于 60% 的数据： n ≤ 92
对于 100% 的数据： n在long long(INT64)范围内。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #define ll long long 6 using namespace std; 7 const ll Mod=1000000007; 8 ll n; 9 struct matrix{ll m[5][5];}a; 10 matrix multiply(matrix a,matrix b){ 11 matrix t; 12 for(int i=1;i<=2;i++) 13 for(int j=1;j<=2;j++){ 14 t.m[i][j]=0; 15 for(int k=1;k<=2;k++) 16 t.m[i][j]=(t.m[i][j]+a.m[i][k]*b.m[k][j])%Mod; 17 } 18 return t; 19 } 20 matrix fast(matrix a,ll p){ 21 matrix ans=a;p--; 22 while(p>0){ 23 if(p&1) ans=multiply(ans,a); 24 a=multiply(a,a); 25 p>>=1; 26 } 27 return ans; 28 } 29 int main(){ 30 a.m[1][2]=a.m[2][1]=a.m[2][2]=1; 31 scanf("%lld",&n); 32 matrix tmp=fast(a,n); 33 printf("%lld",tmp.m[1][2]); 34 return 0; 35 }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
