### PROBLEM LINK:

*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 :

therefore,

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 10^{9}+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 = 10^{9}+7.

### AUTHOR’S SOLUTIONS:

Author’s solution can be found here.