51nod1242 斐波那契数列 矩阵快速幂

1242 斐波那契数列的第N项

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

#include<stdio.h>

#define mod 1000000009

 struct node{

    long long int c[][];

} t;

long long int n;

node mul(node a,node b){//矩阵乘法

    node c;

    int i,j,k;

    for(i=;i<;i++){

        for(j=;j<;j++){

            c.c[i][j]=;

            for(k=;k<;k++)

                c.c[i][j]+=(a.c[i][k]*b.c[k][j])%mod;

        c.c[i][j]=c.c[i][j]%mod;

        }

    }

    return c;

}

node kuaisumi(long long int n){

   node res = t;

    if(n<)

        return res;

    while(n){

        if(n&)

            res=mul(res,t);

        t=mul(t,t);

        n=n>>;

    }

    return res;

}

int main(){

    while(~scanf("%lld",&n)){

        t.c[][] = ;

        t.c[][] = ;

        t.c[][] = ;

        t.c[][] = ;

        node res=kuaisumi(n-);

        printf("%lld\n",res.c[][]);

    }

}

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

 

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