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



Problem Link :


Author: Amrutansu Garanaik , Abhishek Patnaik
Tester: Keshow Sablaka, Amit Das
Editorialist: Amrutansu Garanaik , Amit Kumar Sahu

Difficulty :



Matrix multiplication, Modular matrix exponentiation

Problem :

Given a recurrence relation of the form
             T(n) = a*T(n-1) + b*T(n-2) + c*T(n-3) +d;
Find the nth term.


The solution has many approaches but given the high constraints, most trivial ones will fail. Still, lets take a look at them.

approach 1

Simple recursion - Here, simply use recursion to find the value of previous terms. int result=0; //let t1, t2 and t3 are first three terms of recurrence int T(n) { if(n==1) return t1; if(n==2) return t2; if(n==3) return t3; result + = (a*T(n-1))%MOD; result%=MOD; result + = (b*T(n-2))%MOD; result%=MOD; result + = (c*T(n-3))%MOD; result%=MOD; result + = d; result%=MOD; return result; } This solution will fail as it has too many overlapping sub problems and calling them will take too much stack memory causing memory overflow.

approach 2

We can simply create an array to store the result of successive terms and use them to derive the next ones. This approach will take a fixed amount of memory (i.e. the given array size). int arr[1000000]={0}; arr[0]=0; arr[1]=t1; arr[2]=t2; arr[3]=t3; for(i=4;i<1000000;i++) { int result=0; result + = (a*arr[i-3])%MOD; result%=MOD; result + = (b*arr[i-2])%MOD; result%=MOD; result + = (c*arr[i-1])%MOD; result%=MOD; result + = d; result%=MOD; return result; } This approach will fail as the value of n is upto 10^9 and this will cause memory overflow. But this approach will give answer for more terms then the recursion approach. N.B. This approach can be modified a little bit so that there is no requirement of an array. This will give the required result in linear time (for all values of n) but will fail to pass within time limits. Check this solution for more details.(This approach will take a lot of time (about a minute for our test case) and will fail)

Approach 3 : Matrix exponentiation :

The given recurrence relation is
      T(n) = a*T(n-1) + b*T(n-2) + c*T(n-3) +d;
What if we write it as

M is a matrix derived later

So now we can solve the problem by finding M^(n-3) and multiplying it with the initial given terms. The first row of the multiplication result matrix is our answer.
Now the problen reduces to finding the value of the matrix M. Since we are finding M^(n-3), it means the matrix must be square, otherwise the multiplication of n matrices will not be possible.

Also, we are multiplying the matrix with the initial condition matrix of size 4 X 1. This multiplication is possible if the matrix M^(n-3) has 4 columns (Matrix multiplication property). So M is a 4 X 4 matrix.

Multiplying the matrices, we get
a1 * T(n) + a2 * (T(n-1) + a3 * (T(n-2)) +a4 * d = T(n+1)
b1 * T(n) + b2 * (T(n-1) + b3 * (T(n-2)) +b4 * d = T(n)
c1 * T(n) + c2 * (T(n-1) + c3 * (T(n-2)) +c4 * d = T(n-1)
d1 * T(n) + d2 * (T(n-1) + d3 * (T(n-2)) +d4 * d = d

Equating the terms, we get, a1=a b1=1 a2=b b2=0 a3=c b3=0 a4=1 b4=0 c1=0 c2=1 c3=0 c4=0 d1=0 d2=0 d3=0 d4=1 So the required transformation matrix is :
| a b c 1 |
| 1 0 0 0 |
| 0 1 0 0 |
| 0 0 0 1 |

The matrix multiplication has complexity O(K^3) and we can find the power of the matrix in O(logn) using modular exponentiation. So, overall complexity of the algorithm is O(K^3 log n) where K is the size (number of rows or columns) in the transformation matrix and n is the nth term. For our program, k=4. So overall complexity is O(64*logn).
Check setter solution for implementations.
N.B. If any other method is there for the problem, please share in the comments.
This question is marked "community wiki".

asked 03 Apr '15, 19:30

dragonemperor's gravatar image

accept rate: 10%

toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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:


question asked: 03 Apr '15, 19:30

question was seen: 1,997 times

last updated: 03 Apr '15, 19:30