KESHOW CHALLENGES AMIT - BIG(O)

general
1

Can any one help me with this problem ? I cannot understand the algorithm .

2 

this problem is directly solved using matrix exponentiation
first we need to write the recurrence in matrix form
|a b c 1| x |t(n-1)|
|1 0 0 0|   |t(n-2)|
|0 1 0 0|   |t(n-3)|
|0 0 0 1|   |d     |
then find pow(n-3) binary exponentiation
if u cant understand this see this link:http://zobayer.blogspot.in/2010/11/matrix-exponentiation.html
link to my solution:http://www.codechef.com/viewsolution/6610526
3

@shakil_ruet The editorial will be posted by tonight

4

@shakil_ruet the editorial has been posted

5

Thanks for the help :slight_smile: @dragonemperor and @pallesai