首页 > 代码库 > 【poj3070】 Fibonacci
【poj3070】 Fibonacci
http://poj.org/problem?id=3070 (题目链接)
题意：用矩阵乘法求fibonacci数列的第n项。
Solution
矩乘入门题啊，题目把题解已经说的很清楚里= =。
矩乘其实很简单，通过自己YY或者是搜索对于一个递推公式求出它所对应的矩阵，然后套个快速幂就可以迅速求解第n项。
代码：
// poj3070#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;int n,a[2][2],b[2][2];void mul(int a[2][2],int b[2][2],int ans[2][2]) { int t[2][2]; for (int i=0;i<2;i++) for (int j=0;j<2;j++) { t[i][j]=0; for (int k=0;k<2;k++) t[i][j]=(t[i][j]+a[i][k]*b[k][j])%10000; } for (int i=0;i<2;i++) for (int j=0;j<2;j++) ans[i][j]=t[i][j];}void pow(int k) { while (k) { if (k&1) mul(a,b,b); k>>=1; mul(a,a,a); }}int main() { while (scanf("%d",&n)!=EOF) { if (n==-1) break; a[0][0]=a[0][1]=a[1][0]=1;a[1][1]=0; b[0][0]=b[1][1]=1; b[1][0]=b[0][1]=0; pow(n); printf("%d\n",b[1][0]); } return 0;}
【poj3070】 Fibonacci
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。