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<bits/stdc++.h>  
using namespace std;  
#define MOD 1000000009  
#define ll long long int  
const int N=2;  
long long tmp[N][N];  
void multi(ll a[][N],ll b[][N],ll n,ll m)   //矩阵运算   
{  
    memset(tmp,0,sizeof(tmp));  
    for(int i=0;i<m;i++)  
    for(int j=0;j<m;j++)  
    for(int k=0;k<m;k++)  
    {  
        tmp[i][j]=((a[i][k]*b[k][j])%MOD+tmp[i][j])%MOD;  
    }  
    for(int i=0;i<m;i++)  
    for(int j=0;j<m;j++)  
    {  
        a[i][j]=tmp[i][j];  
    }  
}   
ll res[N][N];//存放结果的数组   
void Pow(ll a[][N],ll n,ll m)  
{  
    memset(res,0,sizeof res);       //n是幂，m是矩阵大小      
    for(int i=0;i<m;i++) res[i][i]=1;  //单位矩阵   
    while(n)  
    {  
        if(n%2==1)  
        {  
            multi(res,a,n,m);//res=res*a;复制直接在multi里面实现了；      
        }  
        multi(a,a,n,m);//a=a*a   
        n=n/2;  
    }  
}  
int main()  
{  
    ll nn=2,mm;  
    scanf("%lld",&mm);//nn为矩阵大小，mm为幂。
    mm=mm-1;
	if(mm==0)
	{
		printf("0\n");
	} 
	else if(mm==1)
	{
		printf("1\n");   
	}
	else
	{
		ll aa[2][2]={1,1,1,0};   
   		Pow(aa,mm,nn);
    	printf("%lld",res[0][0]);
	}
    
    return 0;  
}