How to know this problem uses Matrix Exponentiation?

https://atcoder.jp/contests/dp/tasks/dp_r

After searching on the internet, i found out that this is a very common application of Matrix Exponentiation . But how to do this intuitively and please provide some easy problems similar to this problem.

Exponentiation need not be related to matrices. If you can find f(a+b) using f(a) and f(b) you can use logarithmic exponentiation. It just so happens that the logarithmic exponentiation used here is the same as matrix exponentiation. I’ve already explained it here.

1 Like

I understand your concept but still i am confused. Is it right to say that the given adjacency matrix is for 0 step , so raising it to the power of k will give the result for k steps.

It is correct, but there are intricacies that allow that to happen.

1 Like