51 Nod 1242 斐波那契数列的第N项(矩阵快速幂模板题)

1242 斐波那契数列的第N项 51 Nod 1242 斐波那契数列的第N项(矩阵快速幂模板题)

基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题

51 Nod 1242 斐波那契数列的第N项(矩阵快速幂模板题) 收藏

51 Nod 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的结果即可。

Input

输入1个数n(1 <= n <= 10^18)。

Output

输出F(n) % 1000000009的结果。

Input示例

11

Output示例

89
#include<iostream>
#include<algorithm>
#include<string.h>
#define inf 1000000009
#define ll long long
using namespace std;
struct node{
ll t[2][2];
node(){
memset(t,0,sizeof(t));
}
node operator*(node p){
node c;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
c.t[i][j]=(c.t[i][j]%inf+t[i][k]*p.t[k][j]%inf)%inf;
return c;
}
};
node pow(ll n,node a){
node b;
b.t[0][0]=b.t[1][1]=1;//切记:对角线上一定要为1
while(n){
if(n&1)
b=a*b;
a=a*a;
n>>=1;
}
return b;
}
int main()
{
ll n;
scanf("%lld",&n);
node a;
a.t[0][0]=a.t[0][1]=a.t[1][0]=1;
if(n==0||n==1)
printf("%lld\n",n);
else{
ll d=pow(n-1,a).t[0][0];
printf("%lld\n",d%inf);
}
return 0;
}
上一篇:wget 断点续传 & nginx文件服务器


下一篇:Struts2,Spring, Hibernate三大框架SSH的整合步骤