SPOJ.com - Problem FRS2

FRS2 - Fibonaccibonacci (easy)

no tags

Leo would like to play with some really big numbers, OK...

Let FIB the Fibonacci function :
FIB(0)=0 ; FIB(1)=1
and
for N>=2 FIB(N) = FIB(N-1) + FIB(N-2)

Example : we have FIB(6)=8, and FIB(8)=21, so FIB(FIB(6))=21

Input

The input begins with the number T of test cases in a single line.
In each of the next T lines there are an integer N.

Output

For each test case, print FIB(FIB(N)) ,
as the answer could not fit in a 64bit container,
give your answer modulo 1000000007.

Example

Input:
3
0
5
6

Output:
0
5
21

Constraints

1 <= T <= 10^4
0 <= N <= 10^100

Time limit is set to allow (sub-optimal) 500B of python3 code to get AC.
A near optimal solution is within 0.02 and 0.04s with a fast language, and around 1s in Python2 without psyco.

Edit(20/I/2015) With Cube cluster, it is not hard to get 0.0s with fast languages, and my old code ended in 0.08s using PY3.4.

Edit(11-2-2017) With compiler update, new TL. My old Python code ends in 0.04s, and it's easy to get 0.00s using a fast language.

Submit solution!

hide comments

< Previous 1 2 Next >

	Shashank Srivastava: 2015-12-13 09:18:28 Great problem, but very strict time limit. Had to optimize a lot. @Francky can you give some hints for further optimization? =(Francky)=> You have to find them for other problems, good luck. Last edit: 2015-12-14 21:02:00
	abdou_93: 2015-01-20 06:25:35 @Francky. why WA ! can you help me? ID(13472432 last submission) --Francky--> You should check again C2 and C3. abdou-> thanks . nice problem Last edit: 2015-01-20 16:31:04
	mjh: 2014-12-24 07:44:55 how to handle 10^100 for input --ans(Francky)--> You can store it in a string, or process it on the fly, char by char. But there's no numeric standard container for those numbers ; you have to handle that. edit : I saw you used Python ; in that case you need a much better method. thanks for reply. i first used python, but get tle. so i want to use c++, however i don't know how to handle the big input --(Francky)--> In that case, the first answer suit. Last edit: 2014-12-25 21:13:30
	tyson: 2014-07-01 21:36:38 can someone help me on the time i got AC in 2.9s and have no idea to improve it
	Francis: 2014-04-28 09:03:09 nice prob! actually it costs me a lot of time to get "key" and helps me review some basic knowledge of C~finally get 0.49s in C with fast I/O, and I have no idea how to improve my code, any suggestions? --ans(Francky)--> another key is to do smart precomputation. Please do not spoil on some part of the answer. @Francky, hi Franky. Thx for your advice, you mean the scan part or ??? I know I need to improve my alg rather than using that part. I tried to use precomputation and I chose to precomputate Fib(n) with the big part of n in 0~MOD-1. However it seems that my precomputation only adds time rather than reduces time. I want to know how to deicde the range of n(the bigger n the better??? the larger n the better???) to be precomputated to reduce time efficiently, does that has something to do with the test cases??? I need your hints, Waiting for your reply! :) --ans(Francky)--> precompute all take too much time, you have to do a smart precomputation method. I can't tell you more without spoiling. Good luck. Another tip : matrices are very slow, work only on some coeff, you will avoid redundant computations. Last edit: 2014-04-28 14:11:48
	pankaj bhardwaj: 2013-07-04 11:33:59 Is chinese not enough
	[Lakshman]: 2013-05-12 06:33:59 Don't know how to handle 10^100... --ans--> It's part of the problem. Finally done!!! Awesome problem !!!!!!!!! Last edit: 2013-06-04 16:22:37
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-01-22 05:28:46 After solve FIB64, FRSKT, and PISANO, this problem seems much easier... finally #1st place ;-) --ans--> Good job and congratulations, there's still some small opti to be found ;-) a good ×2 is possible. Last edit: 2013-01-22 07:13:20
	Atul Vaibhav: 2012-10-25 14:28:51 Getting WA! what is the ans for 10^100 ?? --ans--> solve the problem and you'll know. -- Hint : try to manage a brute force with python (for example) in order to debug. Good luck. Last edit: 2012-10-25 20:56:45
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2012-10-05 21:05:48 finally AC after silly mistake.. Why 0k mem usage?? --ans--> Some trouble on spoj servers, should be fixed in few times. (Warning, it slows submissions) RE: I did my best (for now), I don't know other trick to speed up my code, maybe next time :-) Google +1 for this awesome problem.. Last edit: 2012-08-26 15:59:56

Submit solution!

Added by:	Francky
Date:	2012-08-19
Time limit:	0.300s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	Own problem