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;
}