【luogu 1962】斐波那契数列

2018-06-17 21:47:30来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目背景

大家都知道,斐波那契数列是满足如下性质的一个数列:

• 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 }

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:(笔记):构造函数之初始化列表

下一篇:C++继承汇总(单继承、多继承、虚继承、菱形继承)