SPOJ PROBLEM 8001. FIBONACCI SUM

Problem Link: http://www.spoj.com/SPOJ/problems/FIBOSUM/

SUMMARY:

The fibonacci sequence is defined by the following relation:

F(0) = 0

F(1) = 1

F(N) = F(N - 1) + F(N - 2), N >= 2

Your task is very simple. Given two non-negative integers N and M, you have to calculate the sum (F(N) + F(N + 1) + ... + F(M)) mod 1000000007.

Logic:

What I have done is that I used matrix powers a nice way to find F[n] (nth term of Fibonacci Series) 

you can calculate this using fast matrix exponentiation i.e nth power of the matrix above at L.H.S gives you the value of (n+1)th Fibonacci number as the element at row and column (1,1) in the resultant matrix. 

at first try to write the first few Fibonacci numbers:
0  1  1  2  3  5  8  13  21  34  55

now write the sum of Fibonacci numbers from 0 to i:
0  1  2  4  7  12  20  33  54

looking the pattern given above we found that

Sum(N) = F(N+2) ---------> (1)

where sum(N) is sum up to Nth term of Fibonacci series

and the simple way to calculate the sum of all the numbers b/w "N" and "M" is: sum(M)-sum(N-1)

so (F(N) + F(N + 1) + ... + F(M)) mod 1000000007 = (sum(M)-sum(N-1)) mod 1000000007

from (1)

sum(M) = F(M+2) and

sum(N-1) = F(N+1)

now the final results become:

(F(N) + F(N + 1) + ... + F(M)) mod 1000000007 = (F(M+2)-F(N+1))mod 1000000007

To View My Solution:

https://github.com/shivam04/spoj/blob/master/FIBOSUM