snippet

競プロの

01knapsack.py

分枝限定法

avl_tree.py

AVL 木（非推奨、square_skip_list.py を使うべき）

binary_indexed_tree.py

Binary Indexed Tree

fast_primality_test.py

高速素数判定

geometry.py

点と直線の距離
2 線分の交差判定
Monotone Chain (凸包)
最小包含円
円と多角形の共通部分の面積

numba_library.py

Numba コンパイルのテンプレート
Numba で高速化したライブラリ

segtree.py

Segment Tree いろいろ

snippet.py

拡張ユークリッド互除法
中国剰余定理
mod 逆元
組み合わせ計算
- C (組み合わせ)
- P (順列)
- H (重複組み合わせ)
- 上昇階乗冪
- 第 1 種スターリング数
- 第 2 種スターリング数
- Balls and Boxes 3 (第2種スターリング数 * k!)
- ベルヌーイ数
- ファウルハーバーの公式
- Lah number
- ベル数
素数リスト作成
素因数分解 (愚直)
素因数分解 (ロー法)
ミラーラビン素数判定法
BIT (Binary Indexed Tree)
- BIT でのいもす法
- 区間加算
ダイクストラ法
SPFA (Shortest Path Faster Algorithm)
Union Find 木
高速ゼータ変換
(倍数集合の高速ゼータ変換)
Segment Tree
Manacher (最長回文)
Z-algorithm
Dinic 法 (最大流問題)
LIS (最長増加部分列)
LCA (ダブリング)
ニュートン補間
X = [0, 1, 2, ... , n] のラグランジュ補間
ファウルハーバーの公式
ローリングハッシュ
畳み込み (NumPy)
Garner のアルゴリズム (NumPy)
任意 mod 畳み込み (Numpy)
n 個を k 人に均等/貪欲に分けるだけ
xorshift (乱数生成)
(重み付き Union Find)
(Trie)
(全方位木 DP)

snippet2.py

分割数
原始ピタゴラス数の列挙
オイラーの Φ 関数
sqrt(n) の連分数展開
ペル方程式 x*x - n*y*y = 1 の最小整数解
ペル方程式の拡張 x*x - n*y*y = -1 の最小整数解
カレンダー
- ツェラーの公式
階乗進数
- 順列の辞書順 i 番目
ラグランジュ補間
多倍長整数を使った Karatsuba 法
F2 上の Gauss Jordan の掃き出し法
LCA (HL分解)
ドント方式
割り算の結果によって処理を変えることで場合分けが O(sqrt(N)) 通りで済む問題の補助
osa_k 法
奇置換・偶置換の判定
二項間漸化式 a_n = x * a_{n-1} + y
二項間漸化式 a_n = r * a_{n-1} + b * n + c
多項式
きたまさ法
最大クリーク (Bron–Kerbosch algorithm + ヒューリスティック枝刈り)
全方位木 DP
スライド最小値
ダブリング
Berlekamp--Massey
Karatsuba 法
リスト埋め込み用エンコーダ・デコーダ

square_skip_list.py

C++ の multiset に相当するデータ構造

wrap_cpp_multiset.py

C++ の multiset のラッパー