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 のラッパー