7K12 blog

猫でも分かるアルゴリズム解説

EDPC R - Walk

f:id:tkr987:20200511201143p:plain

https://atcoder.jp/contests/dp/submissions/13115881

  • 行列の掛け算は計算量 O(N^3)
  • 繰り返し二乗法を使うと行列累乗(K乗)が O(N^3 \log K)になる
  • 隣接行列のK乗⇔有向グラフ距離Kの経路組み合わせ数と暗記する

f:id:tkr987:20200511201528p:plain

 

以上、解説終わり(ぇ

 

正直、行列累乗を理解したとしても凡人に応用できるとは思えないので虚無な知識になりそうという気持ちになる。理解するのが難しいので「掛け算の答えがfrom→Y→toの出力になっている」とだけ暗記すれば良いかと思った(適当)