How to further optimise this… I am getting tle.

Problem link :- https://www.codechef.com/problems/AVISKR02

my Solution :- https://ideone.com/xICiTo

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.

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.

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

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.