题目背景
大家都知道, 斐波那契数列是满足如下性质的一个数列:
- 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) 范围内
Solution:
本题算是矩阵加速的模板题, 而矩阵加速我好像写过博客, 这里稍微提一下我的理解首先求出线性通项递推式, 然后构造矩阵, 套用快速幂的思想, 便能快速求出第 n 项了复杂度是 O(r2logn), 其中 r 为矩阵的边长, 显然 r 越小越好, 几乎可以当作一个常数
好了说说斐波拉契的递推式: F[n]=F[n-1]+F[n-2],F[1]=F[2]=1
于是可以构造初始矩阵
\begin{bmatrix} F[2]=1 & F[1]=1\end{bmatrix} 以及
中间矩阵 \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix}
最后就是输出特判一下就 ok 了
代码:
- #include<bits/stdc++.h>
- #define il inline
- #define ll long long
- #define debug printf("%d %s\n",__LINE__,__FUNCTION__)
- using namespace std;
- const int mod=1e9+7;
- ll n;
- struct mat{ll a[2][2],r,c;};
- il mat mul(mat x,mat y)
- {
- mat p;
- memset(&p,0,sizeof(p));
- for(int i=0;i<x.r;i++)
- for(int j=0;j<y.c;j++)
- for(int k=0;k<x.c;k++)
- p.a[i][j]=(p.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
- p.r=x.r,p.c=y.c;
- return p;
- }
- il void fast(ll k)
- {
- mat p,ans;
- memset(&p,0,sizeof(p));
- memset(&ans,0,sizeof(ans));
- p.r=p.c=2;
- p.a[0][0]=p.a[0][1]=p.a[1][0]=1;
- ans.r=1,ans.c=2;
- ans.a[0][0]=ans.a[0][1]=1;
- int cnt=0;
- while(k){
- if(k&1){ans=mul(ans,p);}
- p=mul(p,p);
- k>>=1;
- }
- cout<<ans.a[0][0];
- }
- int main()
- {
- ios::sync_with_stdio(0);
- cin>>n;
- if(n<=2)cout<<1;
- else fast(n-2);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2543369.html