https://kanpurin.hatenablog.com/entry/2021/01/16/180926

問題概要
思考の流れ
提出プログラム
感想

問題概要

${N}$ 頂点 ${M}$ 辺の有向グラフの頂点 ${0}$ からちょうど ${T}$ 本の辺を辿って行くことのできる頂点の個数を求めよ.

${1\leq N\leq 10^2\\ 0\leq M\leq 10^4\\ 0\leq T\leq 10^{18}}$

思考の流れ

yukicoder No.1112 冥界の音楽の解法で書いたように隣接行列を ${T}$ 乗した行列の ${(i,j)}$ 成分は「頂点 ${i}$ から頂点 ${j}$ まで ${T}$ 本の辺を辿っていく経路(ウォーク)の数」となる. よって, 隣接行列を ${T}$ 乗した行列の ${1}$ 行目の ${1}$ 以上の成分の数が答えとなるが単に ${T}$ 乗するとオーバーフローするが ${1}$ 以上であるものは ${1}$ として計算しても今回の答えは変わらない.

提出プログラム

https://yukicoder.me/submissions/606002

感想

No.1339の方がキツかった.