# 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 = {{0 , 1 , 0} , {3 , 2 , 3} , {0 , 0 , 3} }
F = {a,a,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…