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.
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.
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.