矩阵快速幂

矩阵的快速幂是用来高效地计算矩阵的高次方的。将朴素的o（n）的时间复杂度，降到log（n）。

其算法本身，利用了之前运算的结果，让整个的运算过程呈现出一种二叉树从底层向上进行收拢的效果。

具体来说，当我们要计算A⁸的时候，我们朴素的算法是依次计算A*A*A*A*A*A*A*A，即第一步先算出A²然后算式变为A²*A*A*A*A*A*A*A，再变为A³*A*A*A*A*A，依次类推，最终得出A⁸的值。

而矩阵快速幂的算法则是，先算出A²再利用其结果进行下一步运算，即A*A*A*A*A*A*A*A会先变成A²*A²*A²*A²,之后在计算出A⁴，将算式变为A⁴*A⁴，之后算出A⁸，这样整个过程只进行了log(8)次，大大减少了运算过程。

这样的运算过程就像刚刚所说，是一种类似于二叉树从底层向上收拢的感觉。实际实现过程借助了计算机中数的二进制表示。使用位运算则可以很好地得出结果。

51nod中的1242（戳我）即矩阵快速幂的模板题，大家可以用来练习

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

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示例

Output示例

89


AC代码：

#include <stdio.h>
#include <cstring>
#include <iostream>
using namespace std;

const long long INF=1000000009;

struct node{
    long long c[2][2];
}t;

node mult(node a,node b){
    node c={0};
    for(int i=0;i<2;i++)
    for(int j=0;j<2;j++)
    for(int k=0;k<2;k++){
        c.c[i][j]+=(a.c[i][k]*b.c[k][j])%INF;
        c.c[i][j]%=INF;
    }
    return c;    
}

node pow(long long n){
    node pt=t;
    if(n < 0) return pt;
    while(n){
        if(n & 1){
            pt=mult(pt,t); 
        }
        t=mult(t,t);
        n=n>>1;        
    }
    return pt;
}


int main(){
    long long n;

    scanf("%lld",&n);
    t.c[0][0]=1;
    t.c[0][1]=1;
    t.c[1][0]=1;
    t.c[1][1]=0;
    node ans=pow(n-2);
    printf("%lld
", ans.c[0][0] * 1);
    return 0;
}