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 <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <queue>
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;
}