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

1242 斐波那契数列的第N项

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

#include<stdio.h>
#define mod 1000000009
 struct node{
    long long int c[2][2];
} t;
long long int n;
node mul(node a,node b){//矩阵乘法
    node c;
    int i,j,k;
    for(i=0;i<2;i++){
        for(j=0;j<2;j++){
            c.c[i][j]=0;
            for(k=0;k<2;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<0)
        return res;
    while(n){
        if(n&1)
            res=mul(res,t);
        t=mul(t,t);
        n=n>>1;
    }
    return res;
}
int main(){
    while(~scanf("%lld",&n)){
        t.c[0][0] = 1;
        t.c[0][1] = 1;
        t.c[1][0] = 1;
        t.c[1][1] = 0;
        node res=kuaisumi(n-2);
        printf("%lld
",res.c[0][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