AtCoder Libraryの内容をまとめました。詳細はリンクのドキュメントを読んで下さい。

#include<atcoder/all>
using namespace atcoder;

上の宣言が必要。以降llはlong longを指す。

あと、基本ライブラリは0-indexedです。特にBITとか注意。

数学

modint

型としてmodint998244353, modint1000000007が用意されている。大抵の問題ではこれで十分。

利便性のために使う。powやinvはメソッドにある。

using mint = modint1000000007;
mint i = 10;
i.val(); // 10
i += mint::raw(20); // +=20だが、20がmod以下なのでmodを取らない。定数倍高速用。 

using mint2 = static_modint<100001>; // staticなmod(問題文で与えられる時)

using mint3 = dynamic_modint<0>;// 複数modを動的に取りたい時, 他の型を取りたい時は1, 2, ...とすればいい
mint3::set_mod(101);
mint3 j = 102;

pow_mod

$x^n mod m$ を求める。O(log n)。繰り返し二乗法を用いている。

ll pow_mod(ll x, ll n, int m)

inv_mod

mod上の逆元を求める。O(log m)。

mod上の逆元は $ax \equiv 1 (mod m)$ となるaのこと。これはmが素数でxがmの倍数で無い時一意に存在。素数じゃないとき存在したりしなかったりする。

ll inv_mod(ll x, ll m)

crt

中国剰余定理。連立合同式を解く。O(n log lcm(m[i]))

ex. $x \equiv 2 (mod 3), x \equiv 3 (mod 5)$ は $x \equiv 8 (mod 15)$

仕組みはけんちょんさんのブログを参考にしてください。要点はユークリッドの互除法をうまく使うこと。3変数以上の時も可能(2つずつマージしていく感じ)

pair<ll, ll> crt(vector<ll> r, vector<ll> m)

mはmod、rは余り。結果は $x \equiv y mod z$ で(y, z)が答え。解なし(0, 0)、n=0の時(0, 1)

floor_sum

$\sum_{i = 0}^{n - 1} \mathrm{floor}(\frac{a \times i + b}{m})$ を求める。O(log (n+m+a+b)). kyopro_friendsさんのツイートが参考になるかも。思い付けねぇ...(周期性に着目して実装してみたけど実装重すぎて諦めた)

高難易度問題で最終的にここに帰着される事とかあるのかな？応用のされかたが予想できない。

ll floor_sum(ll n, ll m, ll a, ll b)

convolution

畳み込み．恐らく NTT．m は NTT-like な static な素数である必要がある．

vector<T> convolution<int m = 998244353>(vector<T> a, vector<T> b)
vector<static_modint<m>> convolution<int m>(vector<static_modint<m>> a, vector<static_modint<m>> b)

convolution_ll

畳み込み．恐らく FFT．long long に収まることが前提．

vector<ll> convolution_ll(vector<ll> a, vector<ll> b)

データ構造

Fenwick Tree(BIT)

要素の1点更新、区間の総和を求める事が可能。Segment Treeの方が高度な事が出来るが、こちらのほうが定数倍が軽い。intやll, modintなどが使える。

メソッド	説明	オーダー
fenwick_tree<T>(int n)	コンストラクタ, 長さn, 初期値0の配列を作る	O(n)
void add(int p, T x)	場所pの値にxを加算、pは $0 \leq p \leq n-1$	O(log n)
T sum(int l, int r)	[l, r)のsum	O(log n)

SegmentTree

セグメントツリー。1点更新、範囲取得。モノイドが載る。eは関数である事に注意。

メソッド	説明	オーダー
segtree<S, op, e>(int n)	コンストラクタ, 型S二項演算op単位元を返す関数e, 要素数n	O(n)
segtree<S, op, e>(vector<S> v)	コンストラクタ, 型S二項演算op単位元を返す関数e, 要素v	O(n)
void set(int p, S x)	場所pの値にxを代入、pは $0 \leq p \leq n-1$	O(log n)
S get(int p)	場所pの値を返す、pは $0 \leq p \leq n-1$	O(log n)
S prod(int l, int r)	[l, r)の範囲クエリ	O(log n)
S all_prod()	[0, n)の範囲クエリ	O(1)
int max_right<f>(int l)	[l, i)のtrueとなる最大のiを返す, min_leftも同じ	O(log n)
int max_right<F>(int l, F f)	[l, i)のtrueとなる最大のiを返す, min_leftも同じ	O(log n)

Lazy SegmentTree

遅延セグ木。色々な操作をO(log n)でできる。作用素モノイドが載る。beetさんの記事を参考に。(beetさんの記事の関数の引数とは逆なので注意！)難しいです。

普通のセグ木は要素の集合(型)Sと写像opと単位元eが必要だが、それに加えて遅延セグ木は、作用素の集合F、要素に作用素を作用させる関数mapping、作用素同士をマージする関数composition、Fの恒等写像idが必要。

mappingは(F, S) → S (作用素が第一引数)

compositionは(F, F) → F (元々第二引数があって第一引数を加える感じ)

遅延セグ木が使える条件は以下の3つ

a, bをマージしてからcを作用させるのと、aにcを作用させたものとbにcを作用させたものは等しい $mapping(c, op(a, b)) = op(mapping(c, a), mapping(c, b)) (a, b\in S, c\in F)$
aにbを作用させてcを作用させるのと、aにbとcをマージしたものを作用させたものは等しい $mapping(c, mapping(b, a)) = mapping(composition(c, b), a) (a \in S, b, c \in F)$
作用素には単位元idがある
- $mapping(id, a) = a (a \in F)$

これで何故O(log n)になるのかというと、作用を遅延させて、欲しい時に作用(その後、子ノードも再帰的に作用させたいが...辞退して遅延)

例えば、区間更新、区間加算取得の遅延セグ木は

普通の区間加算モノイド(int, +, 0)
Fはint
mapping(a, b) = a // 元々bのものを
composition(a, b) = a // bを代入してaを代入なので
id = INF(あり得ない値, 引数がidの時のためにcompositonとmappingを修正)

で作れる。

区間加算は $mapping(c, op(a, b)) = op(mapping(c, a), mapping(c, b)) (a, b\in S, c\in F)$ の条件を満たすために、Sの方に長さの情報を加えるか、beetさんのライブラリのように長さを引数に入れる関数を作ればいいと思います。AtCoder Libraryでは後者の関数が使え無さそうなので前者でやるしか無いっぽい

メソッド	説明	オーダー
lazy_segtree<S, op, e, F, mapping, composition, id>(int n)	コンストラクタ, 型S二項演算op単位元を返す関数e, 作用させる関数mapping, 作用素の合成composition作用素の単位元を返す関数id, 要素数n	O(n)
lazy_segtree<S, op, e, F, mapping, composition, id>(vector<S> v)	コンストラクタ, 型S二項演算op単位元を返す関数e, 作用させる関数mapping, 作用素の合成composition作用素の単位元を返す関数id, 要素v	O(n)
void set(int p, S x)	場所pの値にxを代入、pは $0 \leq p \leq n-1$	O(log n)
S get(int p)	場所pの値を返す、pは $0 \leq p \leq n-1$	O(log n)
S prod(int l, int r)	[l, r)の範囲クエリ	O(log n)
S all_prod()	[0, n)の範囲クエリ	O(1)
void apply(int p, F f)	場所pに作用素fを作用させる	O(log n)
void apply(int l, int r, F f)	[l, r)に作用素fを作用させる	O(log n)
int max_right<g>(int l)	[l, i)のtrueとなる最大のiを返す, min_leftも同じ	O(log n)
int max_right<G>(int l, G g)	[l, i)のtrueとなる最大のiを返す, min_leftも同じ	O(log n)

DSU(Union Find)

disjoint set union. 辺の追加、2頂点が連結かの判定を高速に求める事ができる。

メソッド	説明	オーダー
dsu(int n)	コンストラクタ, n頂点の無向グラフを作る	O(n)
int merge(int a, int b)	頂点a, bを結ぶ, $0 \leq a, b \leq n$	ならしO(α(n))
bool same(int a, int b)	頂点a, bが連結かを調べる	ならしO(α(n))
int size(int a)	頂点の連結成分のサイズ	ならしO(α(n))
vector<vector<int>> groups()	連結成分のリストのグループを返す	O(n)
int leader(int a)	頂点aの代表元	ならしO(α(n))

フロー

MaxFlow

最大流を求めます。多分Dinicが使われているのかな。オーダーよりも高速に動く。応用のされ方は非常に広いのでアリ本を読んだほうが良さそう。

メソッド	説明	オーダー
mf_graph<Cap>(int n)	コンストラクタ, 容量Cap, n頂点のグラフを作る	O(n)
int add_edge(int from, int to, Cap cap)	頂点fromからtoへ最大容量capの辺を張る。何番目に張られた辺かを返す。	ならしO(1)
Cap flow(int s, int t)	頂点sからtへの最大流を返す	辺の容量が全て1の時O( $\min(n^{\frac{2}{3}}m, m^{\frac{3}{2}})$ ), それ以外O( $n^2m$ )
Cap flow(int s, int t, Cap flow_limit)	最大流量がlimit	辺の容量が全て1の時O( $\min(n^{\frac{2}{3}}m, m^{\frac{3}{2}})$ ), それ以外O( $n^2m$ )
vector<bool> min_cut(int s)	i番目の要素は頂点sからiへの残余グラフで到達可能か	O(n + m)
mf_graph<Cap>::edge get_edge(int i)	i番目の辺の内部状態を返す。	O(1)
vector<mf_graph<Cap>::edge> edges()	全ての辺の内部状態を返す。	O(m)
void change_edge(int i, Cap new_cap, Cap new_flow)	i番目の辺の容量、流量をnew_cap, new_flowに変更	O(1)

edgeはint from, toとCap cap, flowで構成された構造体。capが最大容量、flowが流量。

change_edgeで容量とかを変更して、何度もフローを流す時高速に求める事ができるようになる。

get_edgeでフローの際どの辺を使ったかを見る事がある。

MinCostFlow

最小費用流を求めます。これはフローに比べて遅い。

メソッド	説明	オーダー
mcf_graph<Cap, Cost>(int n)	コンストラクタ, 容量Cap, コストCost, n頂点のグラフを作る	O(n)
int add_edge(int from, int to, Cap cap, Cost cost)	頂点fromからtoへ最大容量capコストcostの辺を張る。何番目に張られた辺かを返す。	ならしO(1)
pair<Cap, Cost> flow(int s, int t)	頂点sからtへの最大流量流して最小コストを返す	O(F (n+m) log n) Fは流量
pair<Cap, Cost> flow(int s, int t, Cap flow_limit)	流量がlimit	O(F (n+m) log n) Fは流量
vector<pair<Cap, Cost>> slope(int s, int t)	流量とコストの関係の折れ線を返す	O(F (n+m) log n) Fは流量
vector<pair<Cap, Cost>> slope(int s, int t, Cap flow_limit)	流量がlimit	O(F (n+m) log n) Fは流量
mf_graph<Cap>::edge get_edge(int i)	i番目の辺の内部状態を返す。	O(1)
vector<mf_graph<Cap>::edge> edges()	全ての辺の内部状態を返す。	O(m)

slopeに関して、折れ線の頂点が列挙される。1つめは(0, 0)で折れ線は狭義単調増加。これは多分双対の話ですね。双対性の話は岩田さんのスライドが分かりやすいです。あるいはとこはるさんのpdfとかも良さそうです。が、多分サクッと読めるような話では無いですね。

グラフ

強連結成分分解

閉路を潰してDAGにします。色んな場所で使える。

メソッド	説明	オーダー
scc_graph(int n)	コンストラクタ, n頂点のグラフを作る	O(n)
void add_edge(int from, int to)	fromからtoへの有向辺を張る。	ならしO(1)
vector<vector<int>> scc()	強連結成分分解を行う。	O(n+m)

scc()で求めた2次元vectorですが、u→vに到達できる時、uの方が先に入っています。uとvが互いに到達可能、つまり閉路中に存在する時は同じ所に入っています。

例えば上のグラフがある時、一例として[[a, b, c], [d, e], [f], [g]]みたいになります。(実際にはaとかbとかじゃなくて頂点番号が入ります)

fとgの順番は逆転する可能性があります。

強連結成分分解してDAGにしてDPとか、応用範囲は広いです。

2-SAT

これはグラフアルゴリズムでは無いのですが、内部的に強連結成分分解が使われているので

以下のような論理式を解きます。

$(A \lor B) \land (C \lor D) \land ... $

記号に慣れない人はこう読み替えて下さい。

(A or B) and (C or D) and ...

メソッド	説明	オーダー
two_sat(int n)	コンストラクタ, n変数の2-SATを作成	O(n)
void add_clause(int i, bool f, int j, bool g)	$(x_i = f) \lor (x_j = g)$ を追加	ならしO(1)
bool satisfiable()	条件を満たす割り当てが存在するか	O(n+m)
vector<bool> answer()	satisfiableを呼んだ後に呼び出す。各変数の割り当て	O(n)

文字列

suffix_array

接尾辞配列。接尾辞の文字列の辞書順が小さい順に並べる。ダブリング解法でO(n log n)。かなり賢い。

下の2つは文字列以外に対応。基本Tは整数型のvector。

vector<int> suffix_array(string s) // O(n)
vector<int> suffix_array<T>(vector<T> s) // O(n log n)
vector<int> suffix_array(vector<int> s, int upper) // O(n + upper)

lcp_array

LCP Arrayを返す。接尾辞配列の前後で共通文字列の長さを求める。かなり賢い。O(n)。saは接尾辞配列。

vector<int> lcp_array(string s, vector<int> sa)
vector<int> lcp_array<T>(vector<T> s, vector<int> sa)

z_algorithm

z algorithm。名前がかっこいい。原理は理解できてない。snukeさんの記事を読めばいいと思う。

最終的にその文字列自身と接尾辞の文字列とのLCPをO(n)で求める事が出来るらしい。多分かなり賢い。

vector<int> z_algorithm(string s)
vector<int> z_algorithm<T>(vector<T> s)

文字列関連のアルゴリズムは頭が良いやつが多いです。

その他

AtCoderライブラリのヘッダ

g++ ~~~ -I/(ac-libraryのpath)

で標準ライブラリとして読み取ってくれます。あるいは.zshrc(bashなら.bashrc, Windowsとかは知らない)に

export CPLUS_INCLUDE_PATH="(ac-libraryのpath)"

と書けば良いです。

ライブラリを試したい時

AtCoder Library Practice Contestをしましょう。