hidehic0's library

僕が競プロで使っているライブラリです
主にpythonのライブラリです、c++のもあるけど、いかにも普通です
ファイルは、分割したのは、libsに、全文はcodeに、置いてあります

主要な機能

数学系

機能	アルゴリズム	計算量	備考
素数判定	ミラーラビン素数判定法	$O(\log N)$	$N <= 2^{64}$の場合のみ、動作します
素数列挙	エラトステネスの篩	$O(N \log \log N)$
素因数分解	√N以下の数で試し割り	$O(\sqrt N)$
複数の数を素因数分解	$\sqrt N$以下の素数で試し割り	$O(len(a) \times (\sqrt max(a) \log \log \sqrt max(a)))$
約数列挙	√N以下の数で試し割り	$O(\sqrt N)$
1からNまでの総和	和の公式	$O(1)$	いつも忘れてしまうので関数化した

数列作成

二次元配列、三次元配列を作成できます
ただのスニペットです

二分探索

二分探索を関数化しただけ

ModInt

ModIntのクラス
加算、減算、乗算は、$O(1)$
除算は、$O(\log MOD)$
べき乗は、$O(\log b)$

標準入力

普通です

YesNo関数

特色は、YesまたはNoを出力して、exitする関数ぐらいです

グリッド関数

• 座標がグリッドの中にあるか判定する関数
• 次に行ける場所を列挙する関数

DP

• 部分和dp
• ナップサックdp
• 個数制限ナップサックの品物を分解する関数

グラフのオブジェクト

スペルミスに気づいた
標準入力で、辺を追加する関数がある

UnionFind

いつ使うかも、分からないrollback機能がある

trie木

いつか使う時が来ると、信じたい

BIT

binary indexed tree
累積和よりよさそう

座標圧縮

座標圧縮
一次元のしか揃えてない