### byte_gambler's blog

By byte_gambler, 8 years ago,

Can anyone help with this fibosum problem in SPOJ. I tried it with normal method by storing the fibonacci numbers in array and finding the sum. http://www.spoj.com/problems/FIBOSUM/

• 0

 » 8 years ago, # |   0 Well, your method isn't normal because the constrains are too big.I think this problem can be solved using binary exponentiation of a matrix.
 » 8 years ago, # | ← Rev. 2 →   +3 At first, sorry for my english.Let 's call S(n) = FIB(1) + FIB(2) + ... + FIB(n)It is easy to calculate S(n), DIY (Hint: try calculate S(1), S(2), S(3), S(4) by hand (or computer, whatever), you should find a very simple formula)The rest is easy. O(lg (max(m, n))
•  » » 8 years ago, # ^ |   +11
 » 8 years ago, # |   0 i think u should calculate fibonacci numbers using matrix exponentiation and then use prefix sums.
 » 8 years ago, # | ← Rev. 2 →   0 It's clear that we only need the sum of the first n Fibonacci numbers. As we know that with $F_0=F_1=1$, the sum of all Fibonacci numbers from 0-th to n-th will be just a geometric series: where $E$ is the 2x2 unit matrix and division by matrix A - E can be replaced by multiplication by the inverse of that (non-singular) matrix, which is so in this particular case (Fibonacci numbers), and using modular exponentiation of matrices, the result can be computed in $O(\log{N})$ time.Alternatively, you could use a modular inverse matrix: , it requires less knowledge about matrices.
•  » » 8 years ago, # ^ | ← Rev. 3 →   0 Thanks a lot , that is something new I have learnt :)
•  » » 6 years ago, # ^ | ← Rev. 2 →   -6 @XellosShouldnt the matrix T be T00=0, T10=1?
 » 8 years ago, # |   0 There's a nice identity that you can prove by induction or by telescoping sums: F0 + F1 + ... + Fn = Fn + 2 - 1. This way, you only have to calculate two fibonacci numbers per query and this can be done with matrix exponentiation as everyone else said.
 » 8 years ago, # |   0 Thanks a lot you guys!!!!