Luzhiled's memo

Luzhiled’s memo 簡潔に計算量の話がまとまってて便利なのでよく参照する

グラフ

• [オイラー路]
• [グリッド上の幅優先探索]
• [ハンガリアン法]
• [二部グラフの最大マッチング]
  • 二部グラフの最大マッチング(Hopcroft-Karp)
• [二重辺連結成分分解]
• [二重頂点連結成分分解]
• [全点対間最短路]
• [単一始点最短路]
  • 単一始点最短路(Dijkstra)
  • 単一始点最短路(SPFA)
• [強連結成分分解]
• [彩色数]
• [最大クリーク]
• [最大流]
  • 最大流(Ford-Fulkerson)
  • 最大流(Push-Relabel)
• [最大独立集合]
• [最小全域有向木]
• [最小全域木]
  • 最小全域木(Kruskal)
  • 最小全域木(Prim)
• 最小流量制限付き最大流
• [最小費用流]
• 関節点]

データ構造

• [BIT]
• Binary-Trie
• Convex-Hull-Trick-Add-Monotone
• Li-Chao-Tree
• [Link-Cut木 部分木クエリ]
• [Link-Cut木]
• [ウェーブレット行列]
• [スパーステーブル]
• [スライド区間の昇順k個の和]
• [セグメント木]
• [トライ木]
• [マージ可能ヒープ]
• [列の平方分割]
• [平衡二分探索木]
  • 平衡二分探索木(Red-Black-Tree)
• [永続配列]
• [素集合データ構造]

文字列

• [ローリングハッシュ]
• [接尾辞配列]
• [最長共通接頭辞]
• [最長回文] 回文
• [複数文字列検索]

木

• [HL分解]
• [全方位木DP]
• [最小共通祖先]
• [木の直径]
• [木の重心分解]
• [根付き木に変換]

数学

• Mod-Int
• べき乗(Mod-Pow)
• [オイラーのφ関数]
• [オイラーのφ関数テーブル]
• [ベル数]
• [ラグランジュ補間]
• [二項係数]
• [二項係数テーブル]
• [任意mod畳み込み]
• [分割数]
• [分割数テーブル]
• [商列挙]
• [形式的冪級数] 形式的べき級数
• [拡張ユークリッドの互除法] 拡張ユークリッド互除法
• [第2種スターリング数]
• [約数列挙]
• [素因数分解]
• [素数テーブル]
• [素数判定]
• [組合せ]
• [行列演算]
• [進数変換]
• [階乗]
• [離散対数問題]
• [高速フーリエ変換]

動的計画法

• Divide-And-Conquer-Optimization
• Monotone-Minima
• [スライド最小値]
• [一次元累積和]
• [二次元累積和]
• [個数制限付きナップサック]
• [最大長方形]
• [最適二分探索木]
• [最長増加部分列]

メモ

• ダブリング
• 包除原理
• 燃やす埋める問題 燃やす埋める
• 牛ゲー

その他

• Mo’s Algorithm
• Offline-Dynamic-Connectivity

  • 辺の追加削除クエリがオフラインで与えられる場合は、Undo可能Union-Findを用いることで効率的に処理できる。

• [座標圧縮]

アルゴリズム