【矩阵快速幂】POJ 3070 Fibonacci (大数 Fibonacci)(大二版
发布时间:2020-12-14 02:39:30 所属栏目:大数据 来源:网络整理
导读:【题目链接】 :click here~~ 【题目大意】: In the Fibonacci integer sequence, F 0 = 0, F 1 = 1,and F n = F n ? 1 + F n ? 2 for n ≥ 2. For example,the first ten terms of the Fibonacci sequence are: 0,1,2,3,5,8,13,21,34,… An alternative fo
【题目链接】:click here~~ 【题目大意】: In the Fibonacci integer sequence,F0 = 0,F1 = 1,andFn =Fn ? 1 + Fn ? 2 forn ≥ 2. For example,the first ten terms of the Fibonacci sequence are: 0,1,2,3,5,8,13,21,34,… An alternative formula for the Fibonacci sequence is .Given an integer n,your goal is to compute the last 4 digits of Fn. 【解题思路】 练习矩阵快速幂的基础题了,不说了,比较基础,初学快速幂的可以看这里 click here~~?? click here~~加深理解 本题注意取模mod的大小 代码: #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <math.h> using namespace std; const int mod[5]= {0,10,100,1000,10000}; const int MOD =10000; #define LL long long LL X,Y,N,M,i,j; struct Matrlc { int mapp[2][2]; } ans,base; Matrlc unit= {1,1}; Matrlc mult(Matrlc a,Matrlc b) { Matrlc c; for(int i=0; i<2; i++) for(int j=0; j<2; j++) { c.mapp[i][j]=0; for(int k=0; k<2; k++) c.mapp[i][j]+=(a.mapp[i][k]*b.mapp[k][j])%MOD;//mod[M]; c.mapp[i][j]%=MOD; } return c; } int pow(int n) { base.mapp[0][0] =base.mapp[0][1]=base.mapp[1][0]=1; base.mapp[1][1]=0; ans.mapp[0][0] = ans.mapp[1][1] = 1;// ans 初始化为单位矩阵 ans.mapp[0][1] = ans.mapp[1][0] = 0; while(n) { if(n&1) ans=mult(ans,base); base=mult(base,base); n>>=1; } return ans.mapp[0][1]; } int main() { int t; while(cin>>N&&N!=-1) { printf("%dn",pow(N)); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |