P1962-洛谷-斐波那契数列

发表于
字数统计: 476字 | 阅读时长 ≈ 2分钟

题目：P1962

题目背景

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

• f(1) = 1 ， f(2) = 1 ， f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数)

输入格式： 第 1 行：一个整数 n

输出格式： 第 1 行： f(n) mod 1000000007 的值

输入样例#1:

1
5

输出样例#1：

1
5

输入样例#2：

1
10

输出样例#2：

1
55

说明
对于 60% 的数据： n ≤ 92
对于 100% 的数据： n在long long(INT64)范围内
​

根据数据范围这个题用打表或递归方法显然是超时的，所以就用到了矩阵快速幂，这一题难点就在于怎样构造矩阵，关于矩阵快速幂可以参考上篇博客矩阵快速幂纯模板这次主要讲述怎样构造矩阵，

对于 f(n)=f(n-1)+f(n-2)…这道题目的关键之处在于构造初始矩阵，矩阵快速幂是核心所在。

如何构造：各种构造方法点此处

代码如下：

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
struct st{
	ll a[3][3];
};
st Martrix(st x,st y){
	st ans;
	memset(ans.a,0,sizeof(ans.a));
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++)
			{
				ans.a[i][j]=(ans.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
			}
	return ans;
}
st fast_power(st s,ll n)
{
	st res;
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
		{
			if(i==j) res.a[i][j]=1;
			else res.a[i][j]=0;
		}
	while(n)
	{
		if(n&1) res=Martrix(res,s);
		s=Martrix(s,s);
		n>>=1;
	}
	return res;
}
int main()
{
	ll n;
	st s;
	scanf("%lld",&n);
	if(n==1||n==2)puts("1");
	else
	{
		memset(s.a,0,sizeof(s.a));
		s.a[0][0]=1;s.a[0][1]=1;s.a[1][0]=1;
		s=fast_power(s,n-2);
		printf("%lld\n",(s.a[0][0]+s.a[0][1])%mod);
	}
	
	return 0;
}
hey!baby,站住，点它!