Hey!
I was asked this question in my C-Programming assignment in college. I tried submitting a solution but got TLE. Could anybody please tell me how I could optimize it? Just give me a hint or what I have to use. I want to do it on my own.
Thanks!
Here goes the question :
We all know what Fibonacci numbers are (The sequence of numbers such that every number
in the sequence is the sum of the previous two numbers in the sequence, with the first two
numbers 0 and 1)
f(n) = f(n − 1) + f(n − 2)
f(1) = 0 f(2) = 1
Now lets define a new kind of Fibonacci numbers, the iFibo Numbers.
The iFibo numbers are defined as the sequence of numbers, such that every number in the
sequence is the sum of A times the previous number, B times the number before the previous
number, and C times the number before the number before the previous number in the
sequence, with the first two iFibo numbers equal to D, E and F.
f(n) = A * f(n − 1) + B * f(n − 2) + C * f(n − 3)
f(1) = D f(2) = E f(3) = F
Now, your task is simple. Given N, A, B, C, D, E, F you need to tell the Nth iFibo number (mod
10000007).
Input
The first line contains T. Next T lines contain 7 space separated integers N A B C D E F.
Output
For each testcase, output in a single line, the Nth iFibo number, mod 10000007.
Constraints
0 <= A, B, C, D, E, F < 10000007
For 80% score
0 <= T <= 50
1 <= N <= 100000
For 100% score
0 <=T <= 100000
1 <= N <= 10^12
SampleInput
3
5 1 1 0 1 1 2
4 1 1 1 1 1 1
10 2 0 2 1 2 3
Sample output
5
3
1424