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
|
nvdk:
2024-10-31 22:39:25
Operator overloading works as well, if you are getting TLE just make sure you have taken the input n as long long and not int. |
|
ankitjosh:
2023-03-07 11:50:57
After multiple optimisations, my 3*3 matrix passed. Don't overuse mod and don't use operator overloading or identity matrix creation in matrix exponentiation.
|
|
hackerbhaiya:
2020-08-31 20:31:01
I assumed 1st fibonacci number to be 1 not 0 !!! |
|
matcha1998:
2017-09-11 14:33:45
Application of Matrix Exponentiation!!
|
|
l0gic_b0mb:
2017-06-23 19:41:31
3x3 works if you reduce the MOD operations and don't overload the * operation to multiply matrices (or create a separate function to do the same). Dirty Optimisations. xP Last edit: 2017-06-23 19:43:52 |
|
candide:
2017-04-29 20:14:59
G(n) depends on two consecutive Fibonacci numbers, so you only need to fast-power a 2x2 integer matrix (fast-power = square-and-multiply algorithm). In C, this can get AC in 0.02s without any trick (2017/05). To do a better result, perform precomputation (little tricky). Same advice in order to get AC in Python. Congrat to Francky for his Python performance! |
|
galang:
2016-09-15 07:23:31
used 3x3 matrix with some precomputation, AC 0.10 s |
|
farhad chowdhury:
2016-04-12 19:09:43
can anyone plz share the idea how it can be solved with a 2*2 matrix.
|
|
Tahsin:
2015-07-24 11:21:46
3*3 matrix passed , but without overloading * operator :/ with overloading i got TLE :| time limit is so strict ! |
|
#include:
2015-03-04 13:41:34
2 WAs because of int in place of long long int |
| 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