题目链接：
http://www.51nod.com/Challenge/Problem.html#problemId=1242
1242 斐波那契数列的第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的结果即可。
收起
输入
输入1个数n(1 <= n <= 10^18)。输出
输出F(n) % 1000000009的结果。输入样例
11输出样例
89
矩阵快速幂模板整理
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<sstream>
#include<stack>
#include<string>
#include<set>
#include<vector>
using namespace std;
#define PI acos(-1.0)
#define pppp cout<<endl;
#define EPS 1e-8
#define LL long long
#define ULL unsigned long long //1844674407370955161
#define INT_INF 0x3f3f3f3f //1061109567
#define LL_INF 0x3f3f3f3f3f3f3f3f //4557430888798830399
// ios::sync_with_stdio(false);
// 那么cin, 就不能跟C的 scanf，sscanf, getchar, fgets之类的一起使用了。
const int dr[]={0, 0, -1, 1, -1, -1, 1, 1};
const int dc[]={-1, 1, 0, 0, -1, 1, -1, 1};
inline int read()//输入外挂
{int ret=0, flag=0;char ch;if((ch=getchar())=='-')flag=1;else if(ch>='0'&&ch<='9')ret = ch - '0';while((ch=getchar())>='0'&&ch<='9')ret=ret*10+(ch-'0');return flag ? -ret : ret;
}
LL l,r,k;
LL mod=1000000009;
bool Find(LL mid)
{if(r/mid-(l-1)/mid >= k)return true;return false;
}
struct node
{LL n,m,a[7][7];node(){memset(a,0,sizeof(a));}
};
node mul(node aa, node bb, LL n, LL m, LL k)
{node cc;cc.n=n;cc.m=k;for(int i=0;i<n;i++)for(int j=0;j<k;j++)for(int k=0;k<m;k++)cc.a[i][j]=(cc.a[i][j]+aa.a[i][k]*bb.a[k][j]%mod)%mod;return cc;
}
node power(node a, LL m)
{node d;d.n=d.m=a.n;for(int i=0;i<d.n;++i)d.a[i][i]=1;while(m){if(m&1)d=mul(d,a,d.n,d.m,a.m);m>>=1;a=mul(a,a,a.n,a.n,a.n);}return d;
}
int main()
{LL maxx;cin>>maxx;if(maxx<=2)//表示斐波那契的前两项printf("%lld\n",1LL%mod);else{node x;//系数矩阵x.n=2;x.m=2;x.a[0][0]=1;x.a[0][1]=1;x.a[1][0]=1;x.a[1][1]=0;node tmp;//初始值矩阵tmp.n=2;tmp.m=1;tmp.a[0][0]=1;tmp.a[1][0]=1;node ans=power(x,maxx-2);//计算系数ans=mul(ans,tmp,ans.n,ans.m,tmp.m);printf("%lld\n",ans.a[0][0]);}return 0;
}