大家都知道,斐波那契数列是满足如下性质的一个数列:
请你求出
的值。
一行一个正整数 n
输出一行一个整数表示答案。
输入 #1
5
输出 #1
5
输入 #2
10
输出 #2
55
【数据范围】
题意很简单求斐波那契数列的第nnn项,但是坑点在于n的范围特别大,最大能达到
,O(n)级别的递归会导致超时。
斐波那契数列的递归公式:
。我们以矩阵的角度来看待这个递推式。
可发现每次矩阵乘一下
即可实现一次递推。设
那么,求第n项,即成为求
对应的第一个值。问题就变成了解决求
,我们可以采用矩阵快速幂的方式在
的时间复杂度内完成。
#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.