← All coding problems
N-th Fibonacci Number (Huge N)
mediumPlacement Coding+20 XPTime limit 2s
The Fibonacci numbers are F(0) = 0, F(1) = 1 and F(n) = F(n − 1) + F(n − 2). For each n, print F(n) modulo 1,000,000,007.
Input:
- line 1:
q - next
qlines: one integern
Output: q lines — F(n) mod 1000000007.
Constraints: 1 ≤ q ≤ 1000, 0 ≤ n ≤ 10¹⁸.
Think about it: a loop up to 10¹⁸ never finishes. Use fast doubling: F(2k) = F(k)·(2·F(k+1) − F(k)) and F(2k+1) = F(k)² + F(k+1)². This halves n at each step — about 60 steps. (Matrix exponentiation of [[1,1],[1,0]] also works.)
Sample input 1
4 0 1 10 50
Sample output 1
0 1 55 586268941
Sample input 2
1 100
Sample output 2
687995182
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).