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/

# | User | Rating |
---|---|---|

1 | tourist | 3870 |

2 | Benq | 3618 |

3 | Miracle03 | 3453 |

4 | peehs_moorhsum | 3430 |

5 | Radewoosh | 3418 |

6 | Petr | 3408 |

7 | maroonrk | 3387 |

8 | sunset | 3338 |

9 | ko_osaga | 3334 |

9 | jiangly | 3334 |

# | User | Contrib. |
---|---|---|

1 | YouKn0wWho | 214 |

2 | 1-gon | 203 |

3 | Um_nik | 195 |

4 | Errichto | 181 |

5 | awoo | 180 |

6 | sus | 176 |

6 | tourist | 176 |

8 | antontrygubO_o | 173 |

9 | maroonrk | 170 |

10 | -is-this-fft- | 169 |

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/

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/06/2021 15:51:39 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.

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))

If you lazy: http://www.wolframalpha.com/input/?i=Sum+Fib%28n%29

i think u should calculate fibonacci numbers using matrix exponentiation and then use prefix sums.

It's clear that we only need the sum of the first

nFibonacci numbers. As we know thatwith $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-Ecan be replaced by multiplication by the inverse of that (non-singular) matrix, which isso 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.

Thanks a lot , that is something new I have learnt :)

@Xellos

Shouldnt the matrix T be T00=0, T10=1?

There's a nice identity that you can prove by induction or by telescoping sums:

F_{0}+F_{1}+ ... +F_{n}=F_{n + 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.Thanks a lot you guys!!!!