AC(AtCoder) Library Document

インストール方法

zipファイルを解凍すると、ac-libraryフォルダ, そしてその中にatcoderフォルダが入っているはずです。
g++を使っている場合, atcoderフォルダをmain.cppと同じ場所に置いて、g++ main.cpp -std=c++14 -I .でコンパイルできます。
- -std=c++14か-std=c++17をつけてコンパイルする必要があります。
詳しくは Appendix を参照してください。

制約外の入力を入れたときの挙動はすべて未定義です。
このドキュメントでは長い型を便宜上短く書きます
- unsigned int → uint
- long long → ll
- unsigned long long → ull
$0^0$ は $1$ です
明記されていない場合、多重辺や自己ループも入力可能です。

ACLには収録されていないが、使用頻度が高そうなライブラリを追加しました。

ソート済みのset, table(map)(C++のset, mapと同機能) import atcoder/extra/structure/set_map
Skew Heap
dual fenwick tree
Splay Tree
Universal SegTree
Wavelet Matrix
weighted Union Find
Sliding Window Aggregation
Radix Heap
二分木関係
- Link Cut Tree
- Randomized Binary Search Tree
Sparse Table
永続関係
- 永続配列 import atcoder/extra/structure/persistent_array
- 永続DSU import atcoder/extra/structure/persistent_dsu
- Partially Persistent DSU

約数系
- 約数列挙 import atcoder/extra/math/divisor
- エラトステネス import atcoder/extra/math/eratosthenes
- 素因数分解(pollard-rho法)import atcoder/extra/math/factorization
畳み込み関係
- 任意modの畳み込み
- 高速フーリエ変換
- NTT
- bitwise畳み込み
形式的べき級数関係
- 形式的べき級数
- 形式的べき級数(sparse)
行列
順列・組み合わせ関係
- コンビネーション(階乗・逆元)import atcode/extra/math/combination
- コンビネーションテーブル
進数変換
大きな数の階乗
modint関係
- モンゴメリ演算によるmodint
- modintによる平方根
- modintの分数推測

import atcoder/extra/graph/graph_template
最短経路問題
- dijkstra法: import atcoder/extra/graph/dijkstra
- bellman-ford法: import atcoder/extra/graph/bellman_ford
- warshall-floyd法: import atcoder/extra/graph/warshall_floyd
最小木問題
- prim法
- kruskal法
- volvka法
有向グラフの最小木問題
- Chu-Liu-Edmonds
二部グラフの最大マッチング(最小頂点被覆)
- hopcroft-karp法
一般グラフのマッチング
- gabow-edmonds法
割当問題　- ハンガリアン法
橋と結節点
- lowlink
最大独立集合
サイクルの検出
オイラー周回
彩色数
トポロジカルソート
強連結の向き付け: import atcoder/extra/graph/strong_orientation

ヘッダファイル群(同梱の atcoder フォルダ以下)はCC0ライセンスで公開しています。詳しくはatcoder/LICENSEを参照してください。