7K12 blog

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

2020-05-11から1日間の記事一覧

EDPC R - Walk

https://atcoder.jp/contests/dp/submissions/13115881 行列の掛け算は計算量 繰り返し二乗法を使うと行列累乗(K乗)がになる 隣接行列のK乗⇔有向グラフ距離Kの経路組み合わせ数と暗記する 以上、解説終わり(ぇ 正直、行列累乗を理解したとしても凡人に応用…

ABC132 E - Hopscotch Addict

https://atcoder.jp/contests/abc132/submissions/11351529 modグラフとでも暗記すると良いかもしれない。 グラフの頂点数を3倍に増やす⇔結果を格納する配列の次元を増やすことで実現 上記に合わせてqueueもpair<ll, ll>にすると実装が楽 結果を格納する配列の初期値</ll,>…