[POJ] 3070 Fibonacci

2018-07-03 01:01:33来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

http://poj.org/problem?id=3070

求fib第n项

 

裸矩阵快速幂,练手

 

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

const int MOD=10000;

inline int rd(){
  int ret=0,f=1;char c;
  while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
  while(isdigit(c))ret=ret*10+c-'0',c=getchar();
  return ret*f;
}

struct Mat{
  int a[2][2];
  Mat(){memset(a,0,sizeof(a));}
  Mat operator*(const Mat &rhs){
    Mat ret;
    for(int k=0;k<=1;k++){
      for(int i=0;i<=1;i++){
    for(int j=0;j<=1;j++){
      ret.a[i][j]+=a[i][k]*rhs.a[k][j];
      ret.a[i][j]%=MOD;
    }
      }
    }
    return ret;
  }
  Mat operator^(int x){
    Mat ret,base=*this;
    ret.a[0][0]=ret.a[1][1]=1;
    while(x){
      if(x&1) ret=ret*base;
      base=base*base;
      x>>=1;
    }
    return ret;
  }
};

int main(){
  int T,n;
  while(1){
    n=rd();
    if(n==-1) return 0;
    Mat e,st;
    e.a[0][1]=e.a[1][0]=e.a[1][1]=1;
    st.a[0][0]=0;st.a[0][1]=1;
    st=st*(e^n);
    printf("%d\n",st.a[0][0]);
  }
  return 0;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:vs2017中的scanf_s

下一篇:BZOJ1432: [ZJOI2009]Function(找规律)