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>
using namespace std;
struct node {
long long  t[2][2];
} p;
struct node  mutl( struct node a,struct node b)//矩阵相乘
{
    struct node c;
    c.t[0][0]=c.t[0][1]=c.t[1][0]=c.t[1][1]=0;
    for (int i=0;i<2;i++)
    {
        for (int j=0;j<2;j++)
        {
            c.t[i][j]=0;
            for (int k=0;k<2;k++)
            {
                c.t[i][j]+=(a.t[i][k]*b.t[k][j])%1000000009;
            }
            c.t[i][j]%=1000000009;
        }
    }
    return c;
}
struct node expo (long long n)
{
    struct node temp=p;
    if (n<0)
    {
        return temp;
    }
    while(n)
    {
        if (n&1)
        {
            temp=mutl(temp,p);
            n--;
        }
        p=mutl(p,p);
        n=n>>1;
    }
    return temp;
}
int main()
{
    long long n;
    cin>>n;
    p.t[0][0]=1;
    p.t[0][1]=1;
    p.t[1][0]=1;
    p.t[1][1]=0;
    struct node aa = expo(n-2);
    cout<<aa.t[0][0];
    return 0;
}