I cannot understand how to solve this problem using matrix exponentiation and also how should i calculate the transition matrix.
And more specifically this paragraph in editorial :
“The key step to solve the problem now is to notice that each transition from the solution for the first k crimes to the solution for the first (k + 1) crimes can be seen as multiplying the vector of the current state by the transition matrix. Once all possible transitions are converted to the matrix form, the problem can be solved by raising the matrix into n-th power. Raising the matrix into large power can be done efficiently using matrix exponentiation: on some steps instead of computing Ai + 1 = Ai· A0 one can compute A2i = Ai· Ai.”
I mean what transition matrix to multiply.
Question Link: http://codeforces.com/problemset/problem/107/D
Editorial Link: http://codeforces.com/blog/entry/2514
Thanks in Advance!!