【Luogu1962】Fibonacci数列

来源和评测点

Luogu1962
Caioj1484

题目

【题目大意】
给定n,求第n个Fibonacci数mod 10^9+7的值。
注意第一个Fibonacci数为1
【输入格式】
仅一个整数n
【输出格式】
输出结果
【输入样例】
10
【输出样例】
5

分析

一题比一题水

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
//*******************全局常量*******************
const int MAXN=110;
//*******************全局定义*******************
typedef long long ll;
struct matrix
{
int row,col;
ll p[MAXN][MAXN];
matrix()
{
memset(p,0,sizeof(p));
}
};
//*******************全局变量*******************
ll mod=1000000007;
//*******************实现*******************
matrix cheng(matrix a,matrix b)
{
matrix c;
int n=a.row,m=a.col,p=b.col;
for(int i=1;i<=n;i++)
for(int j=1;j<=p;j++)
for(int k=1;k<=m;k++)
c.p[i][j]=(c.p[i][j]+a.p[i][k]*b.p[k][j]%mod)%mod;
c.row=n;c.col=p;
return c;
}
matrix jia(matrix a,matrix b)
{
matrix c;c.row=a.row;c.col=a.col;
for(int i=1;i<=c.row;i++)
for(int j=1;j<=c.col;j++)
c.p[i][j]=(a.p[i][j]+b.p[i][j])%mod;
return c;
}
matrix pre(int fn)
{
matrix c;
for(int i=1;i<=fn;i++) c.p[i][i]=1;
c.row=c.col=fn;
return c;
}
matrix power(matrix a,ll e)
{
matrix c=pre(a.row);
while(e>0)
{
if(e%2==1) --e,c=cheng(c,a);//a*c也行
a=cheng(a,a);e/=2;
}
return c;
}
//*******************主函数*******************
int main()
{
ll n;scanf("%lld",&n);
if(n==1) { printf("1");return 0; }
if(n==2) { printf("1");return 0; }
matrix f;f.row=2;f.col=2;
f.p[1][2]=1;f.p[2][1]=1;f.p[2][2]=1;
f=power(f,n-2);
matrix ans;ans.row=2;ans.col=1;
ans.p[1][1]=1;ans.p[2][1]=1;
ans=cheng(f,ans);
printf("%lld",ans.p[2][1]);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-01/Fibonacci数列.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%