×

# NPLFSEQ - Editorial

Author: vinod10
Editorialist: vinod10

Medium

# PROBLEM:

Given a sequence f(n) = A * f(n-1) + B * f(n-2), ( with base case f(1)=f(2)=1 ), find sum of f(n) where l<=n<=r. Find this sum for Q queries.

# QUICK EXPLANATION:

S(l,r) = f(l) + f(l+1) + ..... +f(r) = { f(r+2) - f(l+1) + (A-1) * ( f(l) - f(r+1) ) } / {A+B-1}. Now using matrix exponentiation, f(X) can be found in logX time. Hence each query can be solved in LogN time.

# EXPLANATION:

Given,

f(l) = A * f(l-1) + B * f(l-2).

f(l+1) = A * f(l) + B * f(l-1).
.
.
.

f(r-1) = A * f(r-2) + B * f(l-3).

f(r) = A * f(r-1) + B * f(r-2).

Summing these all will give:

S(l,r) = A * ( S(l,r) - f(r) + f(l-1) ) + B * ( S(l,r) - f(r) - f(r-1) + f(l-1) + f(l-2) ).

Simplifying it gives: S(l,r) = { f(r+2) - f(l+1) + (A-1) * ( f(l) - f(r+1) ) } / {A+B-1}

Now calculation of f(n) requires knowledge of matrix exponentiation, and if you are not familiar with it, you can follow this blog.

We know :

$$\left(\begin{array}{cc} f(n) & f(n-1)\\ f(n-1) & f(n-2) \end{array}\right) \left(\begin{array}{cc} A & 1\\ B & 0 \end{array}\right) = \left(\begin{array}{cc} f(n+1) & f(n)\\ f(n) & f(n-1) \end{array}\right)$$

therefore,

$$\left(\begin{array}{cc} A+B & 1\\ 1 & 1 \end{array}\right) \left(\begin{array}{cc} A & 1\\ B & 0 \end{array}\right)^{n-3} = \left(\begin{array}{cc} f(n) & f(n-1)\\ f(n-1) & f(n-2) \end{array}\right)$$

Using matrix multiplication M^{N-3} can be calculated in logN time. Hence we calculate each term in the answer and to divide the final answer by {A+B-1}, we use modular multiplicative inverse. Notice 109+7 is a prime, hence Fermat's little theorem can be used to get modular multiplicative inverse of {A+B-1}, which is {(A+B-1)MOD-2} % MOD, where MOD = 109+7.

# AUTHOR'S SOLUTIONS:

Author's solution can be found here.

6★vinod10
513
accept rate: 0%

 0 @vinod10, Can you tell me where am I wrong with this solution : Thanks! answered 08 Nov '17, 13:55 96●6 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×285
×8
×1

question asked: 01 Nov '17, 13:33

question was seen: 350 times

last updated: 08 Nov '17, 13:55