いけるかな？ (AOJ 2107)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2107

問題

略

解法

辺の数が50と少ないので、最後に使った辺+どちらの頂点に行ったかで状態を保存し、その遷移行列を作る。この行列をz乗すればちょうどz歩でn-1の頂点に辿りつけるかどうか分かる。普通に行列の乗算をするとたぶんオーバーフローするので行列は0か1で保存すること。