题目：

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

分析：

一般我们数据小， 可以直接模拟递推过去， 这里 n 达到 10 ^ 18 很大， 时间， 空间都过不去了。

需要优化。

我们可以发现 Fn = Fn-1 + Fn-2的；

Fn = 1 1 * Fn-1

Fn-1 0 1 Fn-2

由此可构造矩阵了优化了。

实现：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL MOD = 1000000009;

struct Martix {

    LL data[2][2];

    Martix() {

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

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

            data[i][j] = 0;

    }

    Martix(int a, int b, int c, int d) {

        data[0][0] = a;

        data[0][1] = b;

        data[1][0] = c;

        data[1][1] = d;

    }

    Martix operator * (const Martix a) const {

        Martix tmp;

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

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

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

                tmp.data[i][j] = (tmp.data[i][j] + this->data[i][k] * a.data[k][j] % MOD) % MOD;

        return tmp;

    }

    void Print() {

        cout << "Ma : \n";

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

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

            cout << this->data[i][j] << " ";

            cout << endl;

        }

    }

};

const Martix E = Martix(1,0,0,1);

const Martix Be = Martix(1,1,1,0);

Martix Ma_Pow(Martix a, LL n) {

    Martix ret = E;

    while(n) {

        if(n & 1) ret = ret * a;

        a = a * a;

        n >>= 1;

    }

    return ret;

}

int main() {

    LL n;

    while(cin >> n) {

        if (n == 0) cout << 0 <<endl;

        else if (n == 1) cout << 1 << endl;

        else {

            Martix ans = Ma_Pow(Be, n-1);

            cout << ans.data[0][0] <<endl;

        }

    }

}