I would like to know to simplify the summation given in the problem SANBAN
ie) Σi*fibonacci(i)
LINK : Banta needs help
I would like to know to simplify the summation given in the problem SANBAN
ie) Σi*fibonacci(i)
LINK : Banta needs help
In this question, if you observe and calculate initial terms , you can get a simple formulae to
solve your problem.
The formulae for the problem is (n-1)*fib(n+2)-fib(n+1)+2.
and you can calculate nth fibonacci number using matrix exponentiation in O(logN) time which will pass both the subtasks,here’s the link
Matrix exponentiation | HackerEarth. It is a great blog for understanding matrix exponentiation.
I hope this clears your problem!
First let us find out the sum of the first n Fibonacci numbers.
Now we are ready to solve the given problem.
That is the final form which can be used to solve the problem. Here is my code for reference, using matrix exponentiation for calculation of the Fibonacci numbers : link.
Cheers!
@meooow , can you help me here - Can anyone explain the problem Geometric Trick ? - general - CodeChef Discuss