10299 Problem A: Modular Fibonacci(斐波那契的矩阵快速幂)

Problem A: Modular Fibonacci

The Fibonacci numbers (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...) are defined by the recurrence:

F0 = 0

F1 = 1

Fi = Fi-1 + Fi-2 for i>1

Write a program which calculates Mn = Fn mod 2m for given pair of n and m. 0 n 2147483647 and 0 m< 20. Note that a mod b gives the remainder when a is divided by b.

Input and Output

Input consists of several lines specifying a pair of n and m. Output should be corresponding Mn, one per line.

Sample Input

11 7

11 6

Sample Output

89

25

时间: 2016-04-20

10299 Problem A: Modular Fibonacci(斐波那契的矩阵快速幂)的相关文章

C语言求Fibonacci斐波那契数列通项问题的解法总结_C 语言

一:递归实现  使用公式f[n]=f[n-1]+f[n-2],依次递归计算,递归结束条件是f[1]=1,f[2]=1. 二:数组实现  空间复杂度和时间复杂度都是0(n),效率一般,比递归来得快. 三:vector<int>实现  时间复杂度是0(n),时间复杂度是0(1),就是不知道vector的效率高不高,当然vector有自己的属性会占用资源. 四:queue<int>实现  当然队列比数组更适合实现斐波那契数列,时间复杂度和空间复杂度和vector<int>一样

斐波那契数列 矩阵求法 优化

在做编程题目的时候经常会遇到"斐波那契数列"相关的题目,尤其在做OJ中.下面说一些方法: (一)递归 递归是最慢的会发生重复计算,时间复杂度成指数级. long long fac(int n) { if(n==1) return 1; else if(n==2) return 2; else return fac(n-1)+fac(n-2); } (二)循环 利用临时变量来保存中间的计算过程,加快运算. long long fac(int n) { long long a=1,b=2,

HDU 3936 斐波那契性质矩阵连乘

题意:p[i]=fib[4*i-1] 给出L,R,求出中间的p[i]的和. 利用性质:p[1]+p[2]+...+p[n]=f[1]^2+f[2]^2+...+f[2*n-1]^2+f[2*n]^2=f[2*n]*f[2*n+1] fibonacci数列的性质: 1.gcd(fib(n),fib(m))=fib(gcd(n,m)) 证明:可以通过反证法先证fibonacci数列的任意相邻两项一定互素,然后可证n>m时gcd(fib(n),fib(m))=gcd(fib(n-m),fib(m)),

求解斐波那契数列 python 的两个方法比较

Fibonacci斐波那契数列,很简单,就是一个递归嘛,学任何编程语言可能都会做一下这个. 这次在,python中也不例外,最基本的那种递归(如下fib1)效率太低了,只要n数字大了运算时间就会很长:而通过将计算的指保存到一个dict中,后面计算时直接拿来使用,这种方式成为备忘(memo),如下面的fib2函数所示,则会发现效率大大提高. 在n=10以内时,fib1和fab2运行时间都很短看不出差异,但当n=40时,就太明显了,fib1运行花了35秒,fab2运行只花费了0.00001秒. n=

UVa 10229 Modular Fibonacci:矩阵快速幂求斐波那契

10229 - Modular Fibonacci Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=1170 The Fibonacci numbers (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...) are defin

UVa 10236 The Fibonacci Primes:斐波那契素数

10236 - The Fibonacci Primes Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1177 注意此题的描述和维基百科上Fibonacci Prime的描述不同. 上面加着重符的文字说明:可以用类似素数筛的方式筛出Fibonacci Pr

斐波那契数列-Fibonacci数列 的疑问(一增一减的迭代法)

问题描述 Fibonacci数列 的疑问(一增一减的迭代法) 程序如下: int f = 0; int g = 1; for (int i = 0; i <= 15; i++) { println(f); f = f + g; g = f - g; } 输出:0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 问题1:为什么是用一增一减实现的? 问题2:还有关初值f和g是怎么设定的? 谢谢! 解决方案 public int fibonacci(int n){

求斐波那契(Fibonacci)数列通项的七种实现方法_C 语言

一:递归实现使用公式f[n]=f[n-1]+f[n-2],依次递归计算,递归结束条件是f[1]=1,f[2]=1.二:数组实现空间复杂度和时间复杂度都是0(n),效率一般,比递归来得快.三:vector<int>实现时间复杂度是0(n),时间复杂度是0(1),就是不知道vector的效率高不高,当然vector有自己的属性会占用资源.四:queue<int>实现当然队列比数组更适合实现斐波那契数列,时间复杂度和空间复杂度和vector<int>一样,但队列太适合这里了,

HDOJ/HDU 5686 Problem B(斐波拉契+大数~)

Problem Description 度熊面前有一个全是由1构成的字符串,被称为全1序列.你可以合并任意相邻的两个1,从而形成一个新的序列.对于给定的一个全1序列,请计算根据以上方法,可以构成多少种不同的序列. Input 这里包括多组测试数据,每组测试数据包含一个正整数N,代表全1序列的长度. 1≤N≤200 Output 对于每组测试数据,输出一个整数,代表由题目中所给定的全1序列所能形成的新序列的数量. Sample Input 1 3 5 Sample Output 1 3 8 Hin