問題はこちら
問題概要
頂点
辺の有向グラフの頂点
からちょうど
本の辺を辿って行くことのできる頂点の個数を求めよ.
思考の流れ
yukicoder No.1112 冥界の音楽の解法で書いたように隣接行列を
乗した行列の
成分は「頂点
から頂点
まで
本の辺を辿っていく経路(ウォーク)の数」となる. よって, 隣接行列を
乗した行列の
行目の
以上の成分の数が答えとなるが単に
乗するとオーバーフローするが
以上であるものは
として計算しても今回の答えは変わらない.
提出プログラム
https://yukicoder.me/submissions/606002感想
No.1339の方がキツかった.
