wns9778.com_威尼斯wns.9778官网

热门关键词: wns9778.com,威尼斯wns.9778官网
wns9778.com > 计算机教程 > 洛谷P1962 斐波那契数列,p1962斐波那契数列

原标题:洛谷P1962 斐波那契数列,p1962斐波那契数列

浏览次数:67 时间:2019-11-10

洛谷P1962 斐波那契数列,p1962斐波那契数列

题目背景

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

• 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)范围内。

 

 

裸的矩阵快速幂

需要特判0,1两种情况

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #define LL long long 
 6 using namespace std;
 7 const int MAXN=200000001;
 8 const int mod=1000000007;
 9 inline LL read()
10 {
11     char c=getchar();LL flag=1,x=0;
12     while(c<'0'||c>'9')    {if(c=='-')    flag=-1;c=getchar();}
13     while(c>='0'&&c<='9')    x=x*10 c-48,c=getchar();    return x*flag;
14 }
15 LL n;
16 struct Matrix
17 {
18     LL a[5][5];
19     Matrix()
20     {
21         memset(a,0,sizeof(a));
22     }
23 };
24 Matrix Matrix_Mul(Matrix a,Matrix b)
25 {
26     Matrix c;
27     for(LL k=1;k<=2;k  )    
28         for(LL i=1;i<=2;i  )
29             for(LL j=1;j<=2;j  )
30                 c.a[i][j] =(a.a[i][k]*b.a[k][j])%mod;
31     return c;
32 }
33 inline void WORK()
34 {
35     Matrix bg,tmp;
36     bg.a[1][1]=1;bg.a[1][2]=1;
37     
38     tmp.a[1][1]=0;tmp.a[1][2]=1;
39     tmp.a[2][1]=1;tmp.a[2][2]=1;
40     while(n) 
41     { 
42         if(n&1)    bg=Matrix_Mul(bg,tmp);
43         tmp=Matrix_Mul(tmp,tmp);
44         n>>=1;
45     } 
46     printf("%lld",bg.a[1][2]%mod);
47 }
48 int main()
49 {
50     n=read();n=n-2;
51     if(n==-1||n==-2)    
52     {
53         printf("1");
54         return 0;
55     }
56         
57     
58     WORK();
59     return 0;
60 }

 

http://www.bkjia.com/cjjc/1230353.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1230353.htmlTechArticle洛谷P1962 斐波那契数列,p1962斐波那契数列 题目背景 大家都知道,斐波那契数列是满足如下性质的一个数列: f(1) = 1 f(2) = 1 f(n) = f(n-1) ...

本文由wns9778.com发布于计算机教程,转载请注明出处:洛谷P1962 斐波那契数列,p1962斐波那契数列

关键词: wns9778.com

上一篇:wns9778.com:[教程]在 CoreOS 上构建你的第一个应用

下一篇:没有了