I did my first dynamic programming problem successfully today here The editorial says that it can be solved int (log n) time with binary exponentiation of a 2x2 matrix. Can someone tell me how to convert a dynamic programming problem into a binary exponentiation problem ?

I don't want code. I want to practice the coding and implementation part myself. I want to know how to get the matrix from the recursive equations.

Let f(X, n) represent the number of paths ending in D with n moves left if the ant is at vertex X.

Then, f(D, 0) = 1, f(A/B/C, 0) = 0

Also, f(D, n) = 3f(A/B/C, n-1) f(A/B/C, n) = f(D, n-1) + 2f(A/B/C, n — 1)

How can I convert these equations into a matrix which needs to be exponentiated ?