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 >

	Kunal: 2011-07-07 22:32:37 Can some one provide some big test cases with correct answers . Thanks in advance.
	restricteur: 2011-07-05 08:29:30 I've got an NZEC even if I put an infinite loop at the beginning of the main method. Normally I should see a TLE ??!! EDIT: accepted after porting from JAVA to C++ This is not fair :( Last edit: 2011-07-05 09:21:42
	mukesh tiwari: 2011-06-24 13:09:53 2x2 matrix exponentiation in Haskell is TLE.
	Santiago Zubieta: 2011-05-02 16:49:07 I'm getting TLE, I guess my solution is sort of archaic I read a, I call gib(a) where gib(a) is a recursive function on itself and fib(a) (which is another recursion) :( hahaha
	prp: 2011-02-02 13:40:57 its showing wrong answer but its running perfectly on my machine
	sandeep pandey: 2010-12-24 16:36:11 phew!AC:-)) Last edit: 2011-03-06 11:54:40
	David Gómez: 2010-12-19 23:31:33 block is right. But, with some optimizations you can get AC using 33 matrix exponentiation. Last edit: 2010-12-20 00:04:16*
	Anoop Chaurasiya: 2010-11-07 19:29:04 time limit is too strict,merely using 33 matrix exponentiation instead of 22 gave me TLE Last edit: 2010-11-07 19:29:53

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