How to further optimise this… I am getting tle.
Problem link :- AVISKR02 Problem - CodeChef
my Solution :- xICiTo - Online C++0x Compiler & Debugging Tool - Ideone.com
Bro Try DP solution.
I couldn’t understnd your solution I m a pycoder so if u already tried it just skip my reply else try it.
Matrix exponentiation.
1 Like
Use matrix exponentiation.
Whenever there is a problem related to generating sequences, try to find out whether there is a pattern in the generated sequence. Most of the time there will be, and you can be sure by looking at the constraints provided in the problem.
And this site i.e. OEIS is great resource for checking the pattern.
Lets come to problem:
If you look at the recursive equation given to you i.e.
G(n) =
\begin{cases}
0 & \text{if $n = 0$} \\
G(n - 1) + f(4n - 1), & \text{if $n \gt 0$ where f(n) is }n^{th} \text{ Fibonacci number.}
\end{cases}
and generate sequence for different values of n, you will get the following sequence:
G(n) = 0, 2, 15, 104, 714, 4895, 33552, \cdots\cdots f(4n - 1).
and if you search for the sequence in OEIS site, you will find that, there is another formula for generating the above sequence i.e.
G(n) = Fibonacci(2n) \times Fibonacci(2n + 1),
that’s why you need to use matrix exponentiation to find these Fibonacci numbers because using the method of matrix exponentiation you can calculate the n^{th} Fibonacci number efficiently i.e. O(log_2n).
For Code Reference: Solution to the problem in C programming.
Thanks for reading.
Peace 
2 Likes
Try using the direct formula:
phi=(1+sqrt(5))/2
phi_0=(1-sqrt(5))/2
fib(n)=(1/sqrt(5))*(phi^n - phi_0^n)
Be careful of overflow so use long int types.
Won’t work.