# 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

## 求解斐波那契数列 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

## 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