1242 斐波那契数列的第N项 

基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题

 收藏

 关注

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

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

#include<iostream>

#include<algorithm>

#include<string.h>

#define inf 1000000009

#define ll long long

using namespace std;

struct node{

        ll t[2][2];

        node(){

                memset(t,0,sizeof(t));

        }

        node operator*(node p){

                node c;

                for(int i=0;i<2;i++)

                        for(int j=0;j<2;j++)

                                for(int k=0;k<2;k++)

                                c.t[i][j]=(c.t[i][j]%inf+t[i][k]*p.t[k][j]%inf)%inf;

                return c;

        }

};

node pow(ll n,node a){

        node b;

        b.t[0][0]=b.t[1][1]=1;//切记：对角线上一定要为1

        while(n){

                if(n&1)

                        b=a*b;

                a=a*a;

                n>>=1;

        }

        return b;

}

int main()

{

        ll n;

        scanf("%lld",&n);

        node a;

        a.t[0][0]=a.t[0][1]=a.t[1][0]=1;

        if(n==0||n==1)

                printf("%lld\n",n);

        else{

                ll d=pow(n-1,a).t[0][0];

                printf("%lld\n",d%inf);

        }

        return 0;

}