SPOJ.com - Problem FLIB

FLIB - Flibonakki

no tags

G(n) is defined as

G(n) = G(n-1) + f(4n-1) , for n > 0

and G(0) = 0

f(i) is ith Fibonacci number. Given n you need to evaluate G(n) modulo 1000000007.

First line contains number of test cases t (t < 40000). Each of the next t lines contain an integer n (0 <= n < 2^51).

For each test case print G(n) modulo 1000000007.

Input:
2
2
4

Output:
15
714

< Previous 1 2 3 4 Next >

	ivar.raknahs: 2015-03-03 16:00:16 reduce as much mod operation as you can. long long is good but too much mod operation can TLE. AC . Last edit: 2015-03-03 16:00:39
	Abhishek: 2014-12-26 17:55:45 Remember , The Fib(n) can also be calculated in O(logn) , if you read CLRS in a proper manner , you can never miss this!
	Kriti Joshi: 2014-12-10 08:31:26 After repeated TLEs , WAs and silly mistakes finally accepted :) Enjoyed solving it.
	Rohan Jain: 2014-12-03 09:18:36 just managed to get AC (2.95sec :p) after removing few mods could be easily done using 2x2 matix
	Aditya Paliwal: 2014-10-26 13:17:26 I got 1.7 secs! Could someone kindly reveal the optimizations for less than 0.1 second? thanks!
	Venkatesh Ganesan: 2013-11-08 17:02:23 dirty optimizations needed for 3x3 matrix.
	Federico LebrÃ³n: 2013-06-03 06:03:11 Wow, this is a lot of fun! Thank you! I've no idea how Tjandra, Francky and Misha are doing it. There must still be secrets I haven't unlocked :) EDIT: Haskell exponentiation works just fine, mine ACs in 1.58s. Last edit: 2013-06-07 07:00:58
	Aradhya: 2013-05-16 06:45:27 how they have done this in 0.03 o.O ... --ans(francky)--> It's very hard. There's many secrets in fib sequence. Last edit: 2013-05-16 16:01:06
	Aradhya: 2013-05-15 15:02:23 learned sth new from this question :) :)

Added by:	Prof_Utonium_ಉಮೆಶ್
Date:	2010-10-05
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64 JS-RHINO OBJC SQLITE
Resource:	MNNIT IOPC 2010