http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1080. Fibonacci
时间限制:1.0s   内存限制:512.0MB  
总提交次数:1595   AC次数:486   平均分:42.75
将本题分享到:
   
 
问题描述
  Fibonacci数是组合数学中非常重要的一个数列,它的递推公式是:
  F(1)=F(2)=1
  F(n)=F(n-1)+F(n-2)
  当然,用这个公式来计算F(n)是非常慢的,当计算F(n)时需要从F(1)一直计算到F(n)。Fibonacci数列还满足一些其他的公式,如:
  F(a+b+1)=F(a+1)*F(b+1)+F(a)*F(b)
  利用这个公式,可以加速Fibonacci数的计算。我们考虑同时计算F(2n+1)和F(2n),则按照上面的公式:
  F(2n+1)=F(n+1)*F(n+1)+F(n)*F(n)
  F(2n)=F(n+1)*F(n)+F(n)*F(n-1)=F(n+1)*F(n)+F(n)*(F(n+1)-F(n))
  这样,F(2n+1)和F(2n)的计算变为了F(n+1)和F(n)的计算,即下标变为了原来的一半。重复利用这种方法,可以每次让下标变为原来的一半,总共需要大约log n次计算(以2为底)。
  当n较大时,后面的方法就比直接的递推要快得多,比如当n=1000000时,后面的方法大概需要20次计算,而直接递推的方法大概需要1000000次计算,现在请你用这种方法计算F(n)和F(n+1)。
  由于答案非常大,你只需要计算F(n)和F(n+1)除m的余数即可。
  注意,上述公式在除m的余数下仍是满足的,即令g(n)是F(n)除m的余数,则
  g(2n+1)=(g(n+1)*g(n+1)+g(n)*g(n))%m
  g(2n)=(g(n+1)*g(n)+g(n)*(g(n+1)-g(n)+m))%m
  在g(2n)的公式中多了一个+m,是为了在运算中不出现负数。
  参数保证n为正整数,m不大于10000。