FLIB - Flibonakki
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.
Input
First line contains number of test cases t (t < 40000). Each of the next t lines contain an integer n (0 <= n < 2^51).
Output
For each test case print G(n) modulo 1000000007.
Example
Input: 2 2 4 Output: 15 714
hide comments
|
[Lakshman]:
2013-05-09 16:41:05
Too hard to get AC in JAVA....some how manage to get AC in C++. |
|
Francky:
2012-12-31 01:27:53
I was waiting for that moment since almost a year !!! It's feasible in Python !!! My code has 888 Bytes, do a small precomp part, then for each n compute flib(n) with only 6 mul(32+32=64bits) and 4 mod operations (and few other small ops). My IO are not magic, so it can be much faster. |
|
(Tjandra Satria Gunawan)(曾毅昆):
2012-12-30 15:59:08
-My first submission 8 months ago is using 5x5 matrix and got AC in 0.84s
|
|
StupidGuy:
2012-09-13 20:23:05
What is ans for 2^51-1 ?
|
|
god_father:
2012-08-10 20:31:32
do not use unnecessary modulo it cost me 2 times TLE... |
|
Prakhar Jain:
2011-12-23 18:01:55
what's the problem here....even 2*2 matrix with log(n) solution is exceeding time limit........:( Last edit: 2011-12-23 19:34:38 |
|
manu:
2011-12-04 13:16:20
Ahh... Done finally!! :) |
|
Gurpreet Singh:
2011-10-01 19:16:24
'0' is not in the input file. My code which stops working if input = 0 , got AC. |
|
bashrc is back:
2011-09-27 16:33:50
2*2 without any optimization....(even with redundancy) gave me AC
|
|
darryl:
2011-07-12 10:05:11
fun problem. enjoyed solving it |
| 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 |
RSS