You are not logged in. Please login at www.codechef.com to post your questions!

×

NPLFSEQ - Editorial

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(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.

asked 01 Nov '17, 13:33

vinod10's gravatar image

6★vinod10
513
accept rate: 0%


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

Thanks!

link

answered 08 Nov '17, 13:55

vivek_shah98's gravatar image

5★vivek_shah98
966
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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