penguin8331's Library

penguin8331のライブラリです
これから随時追加していきます
なにか不備があったら私のtwitterのDMで教えていただけるとありがたいです

ライブラリ作成で参考にさせていただいたサイト
drken1215/algorithm
Luzhiled’s Library
アルゴリズムロジック

Library Files

data-structure

• BIT-2D (領域加算, 領域和取得に両対応) (data-structure/binary-indexed-tree-2d-raq.hpp)
• BIT-2D (data-structure/binary-indexed-tree-2d.hpp)
• BIT (区間加算, 区間和取得に両対応) (data-structure/binary-indexed-tree-raq.hpp)
• BIT (data-structure/binary-indexed-tree.hpp)
• data-structure/binary-trie.hpp
• boost/multiprecision (data-structure/boost-multiprecision.hpp)
• Disjoint Sparse Table (data-structure/disjoint-sparse-table.hpp)
• Dynamic-ModInt (data-structure/dynamic_modular-arithmetic.hpp)
• ext/pb_ds (data-structure/ext-pb_ds.hpp)
• ext/rope (data-structure/ext-rope.hpp)
• ImplicitTreap (data-structure/implicit-treap.hpp)
• 等差数列を作用させる Lazy Segment Tree (data-structure/lazy-segment-tree-arthmetic-raq.hpp)
• 等差数列を作用させる Lazy Segment Tree (data-structure/lazy-segment-tree-arthmetic-ruq.hpp)
• Lazy Segment Tree (data-structure/lazy-segment-tree.hpp)
• PairQuery (by Implicit Treap) (data-structure/pair-query-by-implicit-treap.hpp)
• PrioritySum (by Implicit Treap) (data-structure/priority-sum-by-implicit-treap.hpp)
• data-structure/randomized-binary-search-tree.hpp
• Segment Tree (data-structure/segment-tree.hpp)
• Sparse Table 2D (data-structure/sparse-table-2d.hpp)
• data-structure/sparse-table.hpp
• Static-ModInt (data-structure/static-modular-arithmetic.hpp)
• UnionFind (data-structure/union-find.hpp)
• WeightedUnionFind (data-structure/weighted-union-find.hpp)
• With-Input (data-structure/with_input.hpp)

dump

• dump/dump.hpp

dynamic-programming

• LCS (復元あり) (dynamic-programming/longest-common-subsequence-restoration.hpp)
• LCS (dynamic-programming/longest-common-subsequence.hpp)
• LIS (復元あり) (dynamic-programming/longest-increasing-subsequence-restoration.hpp)
• LIS (dynamic-programming/longest-increasing-subsequence.hpp)
• 累積和 (dynamic-programming/section-sum.hpp)
• 二次元累積和 (dynamic-programming/section-sum2d.hpp)
• 巡回セールスマン問題 (by bitDP) (dynamic-programming/traveling-salesman-problem.hpp)

geomeny

• 多角形の面積 (geomeny/area-polygon.hpp)
• 点と線分の位置関係 (geomeny/ccw.hpp)
• 凸多角形の切断 (geomeny/convex-cut.hpp)
• 凸包 (geomeny/convex-hull.hpp)
• 交点 (geomeny/crosspoint.hpp)
• 距離 (geomeny/distance.hpp)
• 幾何テンプレート (geomeny/geomeny-template.hpp)
• 点と多角形の包含関係 (geomeny/is-contain-in-the-polygon.hpp)
• 凸性判定 (geomeny/is-convex.hpp)
• 交差判定 (geomeny/is-inter.hpp)
• 射影 (geomeny/projection.hpp)

graph

• Bellman–Ford (graph/bellman-ford.hpp)
• BFS (graph/bfs.hpp)
• BFS-2D (graph/bfs2d.hpp)
• graph/cycle-detection-undirected.hpp
• Dijkstra (経路復元あり) (graph/dijkstra-route.hpp)
• Dijkstra (graph/dijkstra.hpp)
• Dijkstra-2D (graph/dijkstra2d.hpp)
• 二部グラフ判定 (graph/is_biparite.hpp)
• Kruskal (最小全域木) $O(E log V)$ (graph/kruskal.hpp)
• Low-Link (橋, 関節点列挙) (graph/low-link.hpp)
• Prim (最小全域木) $O(V log E)$ (graph/prim.hpp)
• Strongly Connected Component (graph/scc.hpp)
• トポロジカルソート (graph/topological-sort.hpp)
• graph/two-sat.hpp
• Warshall Floyd (graph/warshall-floyd.hpp)

graph/flow

• Ford Fullkerson (最大流) (graph/flow/ford-fullkerson.hpp)
• graph/flow/primal-dual.hpp

graph/tree

• Auxiliary Tree (graph/tree/auxiliary-tree.hpp)
• 木の直径 (graph/tree/diameter-weighted.hpp)
• graph/tree/euler-tour-on-edges.hpp
• graph/tree/euler-tour-on-nodes.hpp
• Lowest Common Ancestor (graph/tree/lca.hpp)

math/algebra

• Matrix (行列) (math/algebra/matrix.hpp)

math/combinatorics

• 二項係数テーブル (math/combinatorics/binomial-coefficient.hpp)
• 転倒数 (math/combinatorics/inversion-number.hpp)
• modpow (math/combinatorics/modpow.hpp)
• next_combination (math/combinatorics/next-combination.hpp)

math/number

• 中国剰余定理 (math/number/chinese-remainder-theorem.hpp)
• 進数変換 (math/number/convert-base.hpp)
• 約数列挙 (math/number/divisors.hpp)
• エラトステネスの篩 (math/number/eratostenes.hpp)
• 拡張ユークリッドの互除法 (math/number/ext-gcd.hpp)
• 素数判定法 (math/number/isprime.hpp)
• 確率的素数判定 (Miller-Rabin 法) (math/number/miller-rabin.hpp)
• 確率的素因数分解 (Pollard のロー法) (math/number/pollard-rho.hpp)
• 累乗 (繰り返し二乗法) (math/number/pow.hpp)
• 素因数分解 (math/number/prime-factorization.hpp)

others

• 座標圧縮 (others/compress.hpp)
• 二次元座標圧縮 (others/compress2d.hpp)
• 日付,曜日 (others/date.hpp)
• ダブリング (others/doubling.hpp)
• 区間スケジューリング (others/interval_scheduling.hpp)
• Mo's algorithm (others/mo.hpp)
• 乱数生成 (others/rand-int.hpp)
• 区間をsetで管理するテク (others/range-set.hpp)
• others/timer.hpp

string

• 連長圧縮 (string/rle.hpp)
• ローリングハッシュ (string/rolling-hash.hpp)
• string/suffix-array.hpp
• string/trie.hpp

template

• template/alias.hpp
• template/debug.hpp
• template/func.hpp
• template/macro.hpp
• template/template.hpp
• template/util.hpp

Verification Files

test/AOJ

• test/AOJ/0233.test.cpp
• test/AOJ/0560.test.cpp
• test/AOJ/1160.test.cpp
• test/AOJ/2659.test.cpp
• test/AOJ/2667.test.cpp
• test/AOJ/2842.test.cpp
• test/AOJ/ALDS1_10_C.test.cpp
• test/AOJ/ALDS1_11_C.test.cpp
• test/AOJ/ALDS1_12_A.test.cpp
• test/AOJ/ALDS1_1_C-2.test.cpp
• test/AOJ/ALDS1_1_C.test.cpp
• test/AOJ/ALDS1_5_D.test.cpp
• test/AOJ/CGL_1_A.test.cpp
• test/AOJ/CGL_1_C.test.cpp
• test/AOJ/CGL_2_B.test.cpp
• test/AOJ/CGL_2_C.test.cpp
• test/AOJ/CGL_2_D.test.cpp
• test/AOJ/CGL_3_A.test.cpp
• test/AOJ/CGL_3_B.test.cpp
• test/AOJ/CGL_3_C.test.cpp
• test/AOJ/CGL_4_A.test.cpp
• test/AOJ/CGL_4_C.test.cpp
• test/AOJ/CGL_7_D.test.cpp
• test/AOJ/CGL_7_E.test.cpp
• test/AOJ/DPL_1_d.test.cpp
• test/AOJ/DPL_2_A.test.cpp
• test/AOJ/DSL_1_A.test.cpp
• test/AOJ/DSL_2_F.test.cpp
• test/AOJ/DSL_2_G.test.cpp
• test/AOJ/DSL_2_H.test.cpp
• test/AOJ/DSL_2_I.test.cpp
• test/AOJ/DSL_4_A.test.cpp
• test/AOJ/GRL_1_A.test.cpp
• test/AOJ/GRL_1_B.test.cpp
• test/AOJ/GRL_1_C.test.cpp
• test/AOJ/GRL_2_A.test.cpp
• test/AOJ/GRL_3_A.test.cpp
• test/AOJ/GRL_3_B.test.cpp
• test/AOJ/GRL_3_C.test.cpp
• test/AOJ/GRL_4_B.test.cpp
• test/AOJ/GRL_5_A.test.cpp
• test/AOJ/GRL_5_C.test.cpp
• test/AOJ/GRL_6_A.test.cpp
• test/AOJ/GRL_7_A.test.cpp
• test/AOJ/ITP1_3_D.test.cpp
• test/AOJ/NTL_1_A.test.cpp
• test/AOJ/NTL_1_B.test.cpp

test/atcoder

• test/atcoder/abc177_f.test.cpp
• test/atcoder/abc214_e.test.cpp
• test/atcoder/abc256_a.test.cpp
• test/atcoder/abc280_f.test.cpp
• test/atcoder/abc281_e.test.cpp

test/yosupo

• test/yosupo/binomial-cofficient-prime-mod.test.cpp
• test/yosupo/cycle-detection-undirected.test.cpp
• test/yosupo/matrix-det.test.cpp
• test/yosupo/scc.test.cpp
• test/yosupo/shortes-path.test.cpp
• test/yosupo/static-range-sum-2.test.cpp
• test/yosupo/static-range-sum.test.cpp
• test/yosupo/static-rmq-2.test.cpp
• test/yosupo/static-rmq-3.test.cpp
• test/yosupo/static-rmq-4.test.cpp
• test/yosupo/static-rmq.test.cpp
• test/yosupo/two-sat.test.cpp
• test/yosupo/zalgorithm.test.cpp

test/yukicoder

• test/yukicoder/1995.test.cpp
• test/yukicoder/649.test.cpp
• test/yukicoder/674.test.cpp