FIBOSUMT - Fibonacci extraction Sum
Some people may found FIBOSUM a too easy problem. We propose here a useful variation.
Fib is the Fibonacci sequence: For any positive integer i: if i<2 Fib(i) = i, else Fib(i) = Fib(i-1) + Fib(i-2)
The first line of input contains an integer T, the number of test cases. On each of the next T lines, your are given tree integers c, k, N.
Print Sum(Fib(ki+c) for i in [1..N]). As the answer could not fit in a 64-bit container, just output your answer modulo 1000000007.
Input: 1 3 5 2
Index-1 Fib sequence : 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... We want the 5*1+3 = 8th and 5*2+3 = 13th ones, thus the answer is 21 + 233 = 254.
0 < T <= 60606 0 <= c < k <= 2^15 0 < N <= 10^18
The numbers c,k,N are uniform randomly chosen in their range. For your information, constraints allow 1.3kB of Python3 code to get AC in 0.30s, it could be hard. A fast C-code can get AC around 0.01s. (Timing edited 2017-02-11, after compiler changes) Warning: Here is Cube cluster, you can try the classical edition (clone with Pyramid cluster). Have fun ;-)
could k*n+c >10^18?
@Francky any suggestion why I am getting WA. Thanks.
(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
Thank you for tutorial edition :)