题目描述

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

Fn={1 (n2)Fn1+Fn2 (n3)F_n = \left\{\begin{aligned} 1 \space (n \le 2) \\ F_{n-1}+F_{n-2} \space (n\ge 3) \end{aligned}\right.

请你求出 Fnmod109+7F_n \bmod 10^9 + 7的值。

输入格式

一行一个正整数 n

输出格式

输出一行一个整数表示答案。

输入输出样例

输入 #1

5

输出 #1

5

输入 #2

10

输出 #2

55

说明/提示

【数据范围】
对于 60% 的数据,1n921\le n \le 92
对于 100% 的数据,1n<2631\le n < 2^{63}

题目分析

题意很简单求斐波那契数列的第nn项,但是坑点在于n的范围特别大,最大能达到2632^{63}O(n)O(n)级别的递归会导致超时。

斐波那契数列的递归公式:Fn=Fn1+Fn2F_{n}=F_{n-1}+F_{n-2} 。我们以矩阵的角度来看待这个递推式。

[fn2fn1]×[0111]=[fn1fn2+fn1]=[fn1fn]\begin{bmatrix} f_{n-2} & f_{n-1} \end{bmatrix} \times \begin{bmatrix} 0 & 1\\ 1 & 1 \end{bmatrix} = \begin{bmatrix} f_{n-1} & f_{n-2}+f_{n-1} \end{bmatrix}= \begin{bmatrix} f_{n-1} & f_n \end{bmatrix}

可发现每次矩阵乘一下

[0111]\begin{bmatrix} 0 & 1\\ 1 & 1 \end{bmatrix}

即可实现一次递推。设

A=[0111]A=\begin{bmatrix} 0 & 1\\ 1 & 1 \end{bmatrix}

那么,求第n项,即成为求 [01]×An\begin{bmatrix} 0 & 1\\ \end{bmatrix} \times A^n 对应的第一个值。问题就变成了解决求AnA^n ,我们可以采用矩阵快速幂的方式在O(logn)O(logn) 的时间复杂度内完成。

代码实现

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=5;
const int M=1e9+7;
struct node{
	ll a[N][N]={0};
	int row,col;
};
node I;//单位矩阵

node matrixMins(node a,node b){//矩阵乘法
	node c;//答案矩阵
	c.row=a.row;
	c.col=b.col;
	int n=c.row,p=c.col,m=a.col;
	//计算矩阵乘法
	for(int i=1;i<=n;i++){
		for(int j=1;j<=p;j++){
			for(int k=1;k<=m;k++){
				c.a[i][j]+=a.a[i][k]*b.a[k][j]%M;
				c.a[i][j]%=M;
			}
		}
	}
	return c;
}
node matrixPow(node a,ll k){//矩阵的幂次方
	if(k==0){// 0次方
		return I;//矩阵的0次方是单位矩阵
	}
	node t=matrixPow(a,k/2);//求 a^{n/2} 次方
	if(k&1){//判断k是否是奇数
		return matrixMins(matrixMins(t,t),a);
	}else{//k是偶数
		return matrixMins(t,t);
	}
}
int main(){
	node a;
	ll n;
	cin>>n;
	//处理斐波那契数列 递推矩阵
	a.col=a.row=2;
	a.a[1][1]=0;
	a.a[1][2]=a.a[2][1]=a.a[2][2]=1;
	//处理 单位矩阵
	I.col=I.row=2;
	I.a[1][1]=I.a[2][2]=1;
	I.a[1][2]=I.a[2][1]=0;
	//处理斐波那契数列初始值 [0 1]
	node tt;
	tt.row=1;tt.col=2;
	tt.a[1][1]=0;
	tt.a[1][2]=1;
	
	node tmp=matrixPow(a,n);//计算A^n
	node ans=matrixMins(tt,tmp);
	cout<<ans.a[1][1];
	return 0;
}

Q.E.D.


( ノ^ω^)ノ゚ 稻 花 香 里 说 丰 年 , 听 取 WA 声 一 片 。(╥╯^╰╥)