Educational DP Contest / DP まとめコンテスト R - Walk
解法
与えられた入力をの行列とみなし、これを
乗すれば、その行列の値の総和が、長さ
のパスの総数になります。
あとは、バイナリ法なるものを利用して高速に計算することができれば、答えとなります。
感想
この計算をする問題はたまに見ますが、いつもささっと実装ができなくてどこかでバグらせます。
思考の流れですが、この手の問題は反射的にこれだ、となってしまうのであんまり過程がありません…個人的には知識として位置付けてもいいのかなと思っています(DPといえばDPなのですが、あんまりDPっぽくない気がしています)。
