4

What is the most efficient way to find the modulus of sum of sequence of fibinacci numbers. For example (F(N) + F(N + 1) + ... + F(M)) mod 1000000007.

user3714385
  • 43

2 Answers2

2

Let $S(n)$ be the sum of first $n$ fibonacci modulo MOD( in you case MOD=1000000007). What you want to find is $answer=(S(M)-S(N-1)) \% { MOD}$. If $awswer$ if negative, then $answer=answer+MOD$. So we have to basically find $S(n)$ for any $n$ efficiently. This can be done in $O(logn)$ by matrix exponentiation. First built the recurrence in matrix form and then calculate the power of a matrix modulo MOD efficiently using matrix exponentiation.( here $F(n)$ denotes $n$th fibonacci number, you will have to take care of base cases, I have assumed 1 base index numbering ). $$ \left( \begin{array}{cc} F(n) \\ F(n-1)\\ S(n) \end{array} \right) % = \left( \begin{array}{cc} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{array} \right) % \left( \begin{array}{cc} F(n-1) \\ F(n-2)\\ S(n-1) \end{array} \right) $$ Thus by repeatedly applying this relation we get for $n>=3$ $$ \left( \begin{array}{cc} F(n) \\ F(n-1)\\ S(n) \end{array} \right) % = {\left( \begin{array}{cc} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{array} \right)}^{n-2} % \left( \begin{array}{cc} 1 \\ 1 \\ 2 \end{array} \right) $$ So you just have to calculate the power of this first matrix on RHS of equation. This can be done $O(logn)$ by matrix representation. You can read about it more here it is easy to understand, http://community.topcoder.com/tc?module=Static&d1=features&d2=0104. Just remember what ever multiplication , addition you are doing while matrix exponentiation do it modulo MOD.

advocateofnone
  • 2,059
1

First, note that $$\sum_{i=1}^nF_i = F_{n+2}-1$$ so your sequence reduces as follows: $$\sum_N^MF_i = \sum_1^MF_i - \sum_1^{N-1}F_i = F_{M+2}-F_{N+1}$$

Then those two Fibonacci numbers can be generated without going through the entire sequence using

$$ \begin{align} F_{2n-1} &= F_n^2 + F_{n-1}^2\\ F_{2n} &= (2F_{n-1}+F_n)F_n \end{align}$$

All of which can be done modulo some chosen base.

Joffan
  • 39,627