51nod 1242 斐波那契数列第n项

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

题目链接：传送门
矩阵快速幂
跟之前一道POJ差不多 传送门
把数据类型换成longlong在10^18依然跑的很快
代码如下：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define M 1000000009
struct rng{long long int m[2][2];
};
rng matlab(rng a,rng b){rng ans;int i,j,k;for(i=0;i<=1;i++)for(j=0;j<=1;j++){ans.m[i][j]=0;for(k=0;k<=1;k++){ans.m[i][j]=(M+a.m[i][k]*b.m[k][j]+ans.m[i][j])%M;}}return ans;
}
long long int fast_matlab(long long int n){rng base,r;base.m[0][0]=base.m[0][1]=base.m[1][0]=1;base.m[1][1]=0;r.m[0][0]=r.m[0][1]=1;r.m[1][0]=r.m[1][1]=0;while(n){if(n&1)r=matlab(r,base);base=matlab(base,base);n/=2;}return r.m[0][1];
}
int main(){long long int i;while(cin>>i){if(i==0) cout<<0<<endl;elsecout<<fast_matlab(i-1)<<endl;}return 0;
}

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

---