首页 > 代码库 > POJ 3070 Fibonacci
POJ 3070 Fibonacci
Sol:就是求第N项的斐波那契数。矩阵乘法+快速幂
#include <cstdio> #include <cstring> #include <cmath> #include <iostream> using namespace std; #define LL long long struct Mat{ LL f[2][2]; }; LL MOD = 10000; Mat mul(Mat a,Mat b) { LL i,j,k; Mat c; memset(c.f,0,sizeof(c.f)); for(i=0;i<2;i++) for(j=0;j<2;j++) for(k=0;k<2;k++) c.f[i][j]=(c.f[i][j]+a.f[i][k]*b.f[k][j])%MOD;//可以改为不%MOD return c; } Mat pow_mod(Mat e,LL b) { Mat s; s.f[0][0]=s.f[1][1]=1; s.f[0][1]=s.f[1][0]=0; while(b) { if(b&1) s=mul(s,e); e=mul(e,e); b=b>>1; } return s; } int main() { LL a,b,n,m; //while(~scanf("%lld%lld%lld%lld",&a,&b,&n,&m)) // while(~scanf("%I64d%I64d%I64d%I64d",&a,&b,&n,&m)) while(~scanf("%I64d",&n),n+1) { if(n==0) { printf("0\n"); continue; } n--; LL ans; Mat e; e.f[0][0]=1;e.f[0][1]=1; e.f[1][0]=1;e.f[1][1]=0; e=pow_mod(e,n-1); ans=((e.f[0][0]+e.f[1][0])%MOD+MOD)%MOD; //可能负数结果 //printf("%lld\n",ans); printf("%I64d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。