tkmst201's Library

競技プログラミングで用いるデータ構造やアルゴリズムが置いてあります。バグ報告や意見、要望があれば issue か Twitter に連絡して下さい。

Twitter: @mtk_cp21
AtCoder: tkmst201

マークがあるものは verify または自動テストが行われていないことを表しています。

Library Files

Algorithm

• https://tkmst201.github.io/Library/Algorithm/frequency_table_of_tree_distance.hpp (Algorithm/frequency_table_of_tree_distance.hpp)

Convolution

• 高速フーリエ変換 (FFT) (Convolution/FastFourierTransform.hpp)
• 数論変換 (NTT) (Convolution/NumberTheoreticTransform.hpp)
• 任意 mod 数論変換 (任意 mod NTT) (Convolution/NumberTheoreticTransform_AnyMod.hpp)

DataStructure

• AVL 木 (平衡二分探索木) (DataStructure/AVL_Tree.hpp)
• Binary Indexed Tree (DataStructure/BinaryIndexedTree.hpp)
• 二次元 Binary Indexed Tree (DataStructure/BinaryIndexedTree2D.hpp)
• 区間加算 Binary Indexed Tree (DataStructure/BinaryIndexedTree_RangeAdd.hpp)
• Disjoint Sparse Table (DataStructure/DisjointSparseTable.hpp)
• 動的セグメント木 (DataStructure/DynamicSegmentTree.hpp)
• 遅延伝搬セグメント木 (DataStructure/LazySegmentTree.hpp)
• 完全永続配列 (DataStructure/PersistentArray.hpp)
• 完全永続赤黒木 (平衡二分木) (DataStructure/PersistentRedBlackTree.hpp)
• 完全永続 Stack (DataStructure/PersistentStack.hpp)
• 完全永続 Union Find (DataStructure/PersistentUnionFind.hpp)
• ポテンシャル付き Union Find (DataStructure/PotentializedUnionFind.hpp)
• 赤黒木 (平衡二分探索木) (DataStructure/RedBlackTree.hpp)
• セグメント木 (DataStructure/SegmentTree.hpp)
• Sliding Window Aggregation (SWAG) (DataStructure/SlidingWindowAggregation.hpp)
• Sparse Table (DataStructure/SparseTable.hpp)
• 簡潔ビットベクトル (DataStructure/SuccintBitVector.hpp)
• 素集合データ構造 (Union-Find) (DataStructure/UnionFind.hpp)
• Wavelet Matrix (DataStructure/WaveletMatrix.hpp)

GraphTheory

• 二部マッチング (GraphTheory/BipartiteMatching.hpp)
• 重心分解 (GraphTheory/CentroidDecomposition.hpp)
• 最大流 (Dinic) (GraphTheory/Dinic.hpp)
• 最大流 (Edmonds-Karp) (GraphTheory/EdmondsKarp.hpp)
• オイラーツアー (GraphTheory/EulerTour.hpp)
• 重軽分解 ( HL 分解) (GraphTheory/HeavyLightDecomposition.hpp)
• 重軽分解 ( HL 分解) クエリ (GraphTheory/HeavyLightDecomposition_Query.hpp)
• Level Ancestor Problem (GraphTheory/LevelAncestor.hpp)
• 最近共通祖先 (LCA) (GraphTheory/LowestCommonAncestor.hpp)
• 強連結成分分解 (SCC) (GraphTheory/StronglyConnectedComponents.hpp)
• 1 点更新 パス Fold (GraphTheory/VertexUpdatePathFold.hpp)

Mathematics

• 組み合わせ $_nC_r$ (Mathematics/Combination.hpp)
• 行列 (Mathematics/Matrix.hpp)
• ModInt 構造体 (Mathematics/ModInt.hpp)
• ModInt 構造体 (実行時 mod 指定) (Mathematics/RuntimeModInt.hpp)
• 2-SAT (Mathematics/TwoSat.hpp)
• bit 操作 (Mathematics/bit_operation.hpp)
• 中国剰余定理 (Mathematics/chinese_remainder.hpp)
• ユークリッドの互除法 (Mathematics/euclid.hpp)
• Garner (連立一次合同式 mod M) (Mathematics/garner.hpp)
• $\mod{m}$ での冪と逆元 (Mathematics/mod_pow_inv.hpp)
• Sum of Floor of Linear (Mathematics/sum_of_floor_of_linear.hpp)
• Mathematics/zeta_moebius_transform.hpp

Mathematics/PrimeNumber

• Mathematics/PrimeNumber/counting_primes.hpp
• Mathematics/PrimeNumber/enumerate_primes.hpp
• Mathematics/PrimeNumber/prime_sum.hpp

String

• String/KMP.hpp
• String/RollingHash.hpp
• String/SuffixArray.hpp

Verification Files

Test

• Test/AVL_Tree.2.test.cpp
• Test/AVL_Tree.test.cpp
• Test/BinaryIndexedTree.test.cpp
• Test/BinaryIndexedTree2D.test.cpp
• Test/BinaryIndexedTree_RangeAdd.test.cpp
• Test/BipartiteMatching.test.cpp
• Test/CentroidDecomposition.test.cpp
• Test/Combination.test.cpp
• Test/Dinic.test.cpp
• Test/DisjointSparseTable.test.cpp
• Test/DynamicSegmentTree.swap.test.cpp
• Test/DynamicSegmentTree.test.cpp
• Test/EdmondsKarp.test.cpp
• Test/EulerTour.path.test.cpp
• Test/EulerTour.subtree.test.cpp
• Test/FastFourierTransform.test.cpp
• Test/HeavyLightDecomposition.test.cpp
• Test/HeavyLightDecomposition_Query.PathQuery.test.cpp
• Test/HeavyLightDecomposition_Query.SubtreeQuery.test.cpp
• Test/LazySegmentTree.test.cpp
• Test/LevelAncestor.test.cpp
• Test/LowestCommonAncestor.test.cpp
• Test/NumberTheoreticTransform.test.cpp
• Test/NumberTheoreticTransform_AnyMod.test.cpp
• Test/PersistentRedBlackTree.test.cpp
• Test/PersistentUnionFind.test.cpp
• Test/PotentializedUnionFind.test.cpp
• Test/PrimeNumber.counting_primes.test.cpp
• Test/PrimeNumber.enumerate_primes.test.cpp
• Test/RedBlackTree.lower.upper.test.cpp
• Test/RedBlackTree.test.cpp
• Test/RollingHash.test.cpp
• Test/SegmentTree.fold.test.cpp
• Test/SlidingWindowAggregation.test.cpp
• Test/SparseTable.test.cpp
• Test/StronglyConnectedComponents.test.cpp
• Test/SuffixArray.lcp.test.cpp
• Test/SuffixArray.sa_is.test.cpp
• Test/SuffixArray.search.test.cpp
• Test/TwoSat.test.cpp
• Test/UnionFind.test.cpp
• Test/VertexUpdatePathFold.vertex.test.cpp
• Test/WaveletMatrix.next_prev_value.test.cpp
• Test/WaveletMatrix.quantile.test.cpp
• Test/WaveletMatrix.range_frequency.test.cpp
• Test/WaveletMatrix.select.range_k.test.cpp
• Test/chinese_remainder.test.cpp
• Test/euclid.gcd.lcm.test.cpp
• Test/garner.test.cpp
• Test/matrix.det.test.cpp
• Test/matrix.pow.test.cpp
• Test/sum_of_floor_of_linear.test.cpp
• Test/zeta_moebius_transform.set.1.test.cpp