a(0) = -1

a(1) = 1

a(n) = 2*a(n-1) + 3*a(n-2) + pow (3, n)

Solving using matrix exponentiation

How to calculate the initial matrices

a(0) = -1

a(1) = 1

a(n) = 2*a(n-1) + 3*a(n-2) + pow (3, n)

Solving using matrix exponentiation

How to calculate the initial matrices

i think we can have a transformation matrix of 3 x 3 .

Transformation Matrix T[3][3] = {{0 , 1 , 0} , {3 , 2 , 3} , {0 , 0 , 3} }

F[3] = {a[0],a[1],3}

I think this will surely help you .

1 Like

can u please explain how to form transformation matrix for this types of questionsâ€¦can u generalizeâ€¦

How exactly you jumped to the conclusion

Elaborate

Hello

I read this one too http://www.codechef.com/ALMA2015/problems/ALMA04

This is very standard problem and can be solved using matrix exponentiation . Such Problem are easily solvable following dynammic programming approach but due to high constraints techniques used to solve such problem is called Solving Linear Recurrences .

Here is link for learning 1

Here is link for learning 1

Here is link for learning 3

This will surely help .

1 Like

this will surely help you guys

read this problem based on the same concept

thanks for the helpâ€¦