NPLFSEQ - Editorial

general
, ,
1

PROBLEM LINK:

Practice

Contest

Author: vinod10

Editorialist: vinod10

DIFFICULTY:

Medium

PREREQUISITES:

Matrix Exponentiation , Modular multiplicative inverse

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® = { 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® = A * f(r-1) + B * f(r-2).

Summing these all will give:

S(l,r) = A * ( S(l,r) - f® + f(l-1) ) + B * ( S(l,r) - f® - 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.

2

@vinod10, Can you tell me where am I wrong with this solution :

Thanks!