Matrix Expo

a(0) = -1
a(1) = 1
a(n) = 2a(n-1) + 3a(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 .:smiley:

1 Like

Hello

I read this one too CodeChef: Practical coding for everyone

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

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

this will surely help you guys :smiley:

read this problem based on the same concept

thanks for the help…