51nod:1242 斐波那契数列的第N项

51nod:1242 斐波那契数列的第N项

斐波那契数列的定义如下：

F(0) = 0

F(1) = 1

F(n) = F(n - 1) + F(n - 2) (n >= 2)

(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...)

给出n，求F(n)，由于结果很大，输出F(n) % 1000000009的结果即可。

Input

输入1个数n(1 <= n <= 10^18)。

Output

输出F(n) % 1000000009的结果。

Input示例

11

Output示例

89

题意很简单，斐波那契数列我们都很熟悉吧！f1=1 f2=1 然后后面的每一项都等于前两项的和，这便是斐波那契数列。

一般我们可以对斐波那契数列线性打表，时间复杂度为O（n）。

但在这道题目中，数据范围为[1,10^18]，这样的话，线性的时间复杂度到这时候也会超时啦！

其实，斐波那契数还有一种求法。也就是通过矩阵的乘法，二阶矩阵 (1 1 1 0) 可以经过幂次运算，然后得到相应第多少个斐波那契数，而在幂次运算中，我们可以采用快速幂运算，不会超时的矩阵连乘哦！

AC代码：

#include #include #include #include #include #include using namespace std;const __int64 mod=1000000009;struct node{ __int64 mp[2][2]; void init(__int64 a,__int64 b,__int64 c,__int64 d) { mp[0][0]=a; mp[0][1]=b; mp[1][0]=c; mp[1][1]=d; } void mult(node x,node y) //两矩阵乘法 { memset(mp,0,sizeof(mp)); for(__int64 i=0; i<2; i++) for(__int64 j=0; j<2; j++) for(__int64 k=0; k<2; k++) mp[i][j]=(mp[i][j]+x.mp[i][k]*y.mp[k][j])%mod; };} init;struct node expo(struct node x, __int64 k) //进行k次幂运算{ struct node tmp; tmp.init(1,0,0,1); //单位矩阵 while(k) //快速幂部分 { if(k&1)tmp.mult(tmp,x); x.mult(x,x); k>>=1; } return tmp;}int main(){ __int64 k; scanf("%I64d",&k); init.init(1,1,1,0); //初始化矩阵(1 1 1 0) printf("%I64d\n",expo(init,k).mp[0][1]%mod); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。