51Nod_1242 斐波那契数列的第N项

本文主要是介绍51Nod_1242 斐波那契数列的第N项，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

                                   51Nod_1242 斐波那契数列的第N项

                                           http://www.51nod.com/Challenge/Problem.html#!#problemId=1242

 

 

题目

斐波那契数列的定义如下：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

分析

矩阵快速幂

C++程序

#include<iostream>
#include<cstdio> 
#include<vector>using namespace std;typedef long long LL;
typedef vector<LL>vec;
typedef vector<vec>mat;
const LL MOD=1000000009;//矩阵乘法
mat mul(mat a,mat b)
{mat c(a.size(),vec(b[0].size()));for(int i=0;i<a.size();i++)for(int j=0;j<b[0].size();j++)for(int k=0;k<a[0].size();k++)c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MOD;return c;
}//矩阵的快速模幂法 
mat solve_pow(mat a,LL n)
{mat b(a.size(),vec(a.size()));for(LL i=0;i<a.size();i++)b[i][i]=1;while(n){if(n&1)b=mul(b,a);a=mul(a,a);n>>=1;}return b;
}int main()
{LL n;mat a(2,vec(2));scanf("%lld",&n);a[0][0]=1,a[0][1]=1;a[1][0]=1,a[1][1]=0;a=solve_pow(a,n);printf("%d\n",a[1][0]);return 0;
}

 

这篇关于51Nod_1242 斐波那契数列的第N项的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---