斐波那契数列的第N项
斐波那契数列的定义如下：
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的结果。
Sample Input
11
Sample Output
89
这道 题 我写的 代码 我自己 觉得 是我自己 写的 很 厉害 的 代码 之一 （至今为止），哇 感觉自己 厉害啦 ，哈哈 ！！好啦 不说 废话 啦 下面 给大家 好好的 解析解析 这道 题！
这是一个 很经典的 数列问题，经常会遇到 这样的 题 ，但是 我们当时 写这道题的时候 可没有 考虑到 n 会 那么 的 大 ，哈哈。
这道题 有三种 解法：
第一种就是 最容易想到的 递归啦，老师 在讲递归 的时侯 应该也 把斐波那契数列 当成典型的例子 f(n) = f(n-1) + f(n-2) 虽然 递归用着简单 但是 他是 很耗 内存的 弄不好 内存就 炸啦，而且 对于 这道题 用递归的的话 ，会 重复进行 许多 多余的 操作 时间 也会 比较长 。不太理解的话 看下面的 图 综合一下 。
第二种方法 是 在第一种方法的基础上 进行啦 些许 简单的优化。
第二种方法 使用的 循环 ，因为 用了循环之后 上面所说的 重复 操作 和 占用巨大的 内存资源 的问题 就会 的到解决，但是 呢 这道题的 n 的 范围 真是 太大啦 1e18 ， 所以 这种循环的方法在 n 的范围 比较小情况下 优先考虑啦！既简单 又 不慢！第三种 方法 是 解决这道题的 适用方法，他是 根据 线性代数 中的 矩阵的 运算 下面 大家 根据下面的 图 进行 理解把 很简单的。
大家 看了上面的图片 是不是已经 知道了 第三种方法的 思路啦！ 下面我 先简单的说一下 我代码 的 思路： 我 是用的 结构体 来 存储的 ，然后我把 求解快速幂的 函数 改成了 求解 一个 矩阵的 快速幂的 函数 ， 这其中呢 我还运用啦 operator 的 加载 的方法 简化啦 运算 ，这个 加载 的方法 我感觉很 好用 可以让结构体 变量 想 其他类型的 变量 一样 实现 各种 运算 ！<<（~”’.？.”’~）>>
代码 如下 ：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define mod 1000000009
#define LL long long
using namespace std;struct Matrix
{LL x1, x2;LL x3, x4;Matrix operator * (Matrix &o) // 加载 结构体乘法{Matrix ans;ans.x1 = (this->x1 * o.x1 + this->x2 * o.x3) % mod;ans.x2 = (this->x1 * o.x2 + this->x2 * o.x4) % mod;ans.x3 = (this->x3 * o.x1 + this->x4 * o.x3) % mod;ans.x4 = (this->x3 * o.x2 + this->x4 * o.x4) % mod;return ans;}
};LL Power(const Matrix a, LL b)
{Matrix ret;ret.x1 = 1; ret.x2 = 0;ret.x3 = 0; ret.x4 = 1;Matrix temp = a;while(b){if(b & 1) ret = ret * temp;temp = temp * temp;b /= 2;}return ret.x1;
}int main()
{LL n;while(scanf("%lld", &n) != EOF){Matrix temp;LL ans;temp.x1 = 1; temp.x2 = 1;temp.x3 = 1; temp.x4 = 0;if(n <= 2)ans = 1;elseans = Power(temp, n-1);printf("%lld\n", ans);}return 0;
}