MtSaka's Library

MtSakaのライブラリです。
バグってたらごめんなさい。その場合には気軽に私のTwitterのDMに連絡するか、GitHubのRepositoryにてIssueを立ててくれるとありがたいです。

Library Files

ds/cht

• Convex Hull Trick (ds/cht/convex-hull-trick.hpp)
• Li Chao Tree (ds/cht/li-chao-tree.hpp)

ds/others

• Binary Trie (ds/others/binary-trie.hpp)
• Fast Set (ds/others/fast-set.hpp)
• HashMap(ハッシュマップ) (ds/others/hash-map.hpp)
• HashSet(ハッシュセット) (ds/others/hash-set.hpp)
• 永続配列(Persistent Array) (ds/others/persistent-array.hpp)
• Slope Trick (ds/others/slope-trick.hpp)

ds/segment

• Binary Indexed Tree(Fenwick Tree, BIT) (ds/segment/binary-indexed-tree.hpp)
• ds/segment/disjoint-sparse-table.hpp
• Dual Segment Tree(双対セグメント木) (ds/segment/dual-segment-tree.hpp)
• Dynamic Segment Tree(動的セグ木) (ds/segment/dynamic-segment-tree.hpp)
• Lazy Segment Tree(遅延セグメント木) (ds/segment/lazy-segment-tree.hpp)
• Segment Tree Beats!(Rnage Chmin Chmax Add Update Range Sum Min Max) (ds/segment/segment-tree-beats.hpp)
• Segment Tree(セグメント木) (ds/segment/segment-tree.hpp)
• Sparse Table (ds/segment/sparse-table.hpp)

ds/union-find

• Persistent Disjoint Set Union(永続Union-Find) (ds/union-find/persistent-union-find.hpp)
• Rollback Disjoint Set Union(Union Find) (ds/union-find/rollback-union-find.hpp)
• Union Find(Disjoint Set Union) (ds/union-find/union-find.hpp)
• Weighted Disjoint Set Union(重み付きUnion Find) (ds/union-find/weighted-union-find.hpp)

ds/wavelet

• Bit Vector (ds/wavelet/bit-vector.hpp)
• Wavelet Matrix (ds/wavelet/wavelet-matrix.hpp)

geometry

• geometry/geometry.hpp

graph/flow

• Dinic(最大流) (graph/flow/dinic.hpp)
• Ford Fulkerson(最大流) (graph/flow/ford-fulkerson.hpp)

graph

• Graph Template(グラフテンプレート) (graph/graph-template.hpp)

graph/mst

• Kruskal(最小全域木) (graph/mst/kruskal.hpp)
• Prim(最小全域木) (graph/mst/prim.hpp)

graph/others

• Cycle Detection(閉路検出) (graph/others/detect-cycle.hpp)
• Strongly Connected Components(強連結成分分解) (graph/others/scc.hpp)
• Topological Sort(トポロジカルソート) (graph/others/topological-sort.hpp)
• Tow Satisfiability(2-SAT) (graph/others/two-sat.hpp)

graph/shortest-path

• Bellman-Ford(単一始点最短路) (graph/shortest-path/bellman-ford.hpp)
• Dijkstra With Path(経路付き単一始点最短路) (graph/shortest-path/dijkstra-path.hpp)
• Dijkstra(単一始点最短路) (graph/shortest-path/dijkstra.hpp)
• Warshall Floyd(全点対間最短路) (graph/shortest-path/warshall-floyd.hpp)

graph/tree

• RMQ Lowest Common Ancestor(最小共通祖先) (graph/tree/RMQ_lowest_common_ancestor.hpp)
• graph/tree/catersian-tree.hpp
• Centroid(木の重心) (graph/tree/centroid.hpp)
• Doubling Lowest Common Ancestor(最小共通祖先) (graph/tree/doubling-lowest-common-ancestor.hpp)
• ReRooting(全方位木DP) (graph/tree/rerooting.hpp)
• Tree Diameter(木の直径) (graph/tree/tree-diameter.hpp)

math/convolution

• Convolution(畳み込み) (math/convolution/convolution.hpp)
• Fast Fourier Transform(高速フーリエ変換) (math/convolution/fft.hpp)
• GCD Convolution (math/convolution/gcd-convolution.hpp)
• LCM Convolution (math/convolution/lcm-convolution.hpp)

math/fps

• Formal Power Series(形式的冪級数) (math/fps/fps.hpp)
• Multipoint Evaluation(多点評価) (math/fps/multipoint-evaluation.hpp)
• Polynomial Interpolation(多項式補間) (math/fps/polynomial-interpolation.hpp)
• Count Subset Sum (math/fps/subset-sum.hpp)
• Taylor Shift(多項式の平行移動) (math/fps/taylor-shift.hpp)

math/modular

• Mod Log(離散対数) (math/modular/mod-log.hpp)
• Mod Square Root(平方剰余) (math/modular/mod-sqrt.hpp)
• ModInt (math/modular/modint.hpp)
• MontgomeryModInt(モンゴメリ乗算) (math/modular/montgomery-modint.hpp)

math/number

• Factor Count(約数個数) (math/number/factor-cnt.hpp)
• Factor Enumeration(約数列挙) (math/number/factor.hpp)
• Kth Root Integer (math/number/kth-root-integer.hpp)
• Miller-Rabin Primality Test(ミラーラビン素数判定) (math/number/miller-rabin.hpp)
• Euler's Totient Function(オイラーのφ関数) (math/number/phi.hpp)
• Pollard's Rho Factorization(ポラード・ロー法) (math/number/pollard-rho.hpp)
• Prime Factorization(素因数分解) (math/number/prime-factor.hpp)
• Prime Sieve(エラトステネスの篩) (math/number/prime-sieve.hpp)
• Primitive Root(原始根) (math/number/primitive-root.hpp)
• Quotient Ranges(商列挙) (math/number/quotient-ranges.hpp)
• Range Prime Sieve(エラトステネスの区間篩) (math/number/range-prime-sieve.hpp)

math/others

• Combinatorics(組み合わせ) (math/others/combinatorics.hpp)
• Lagrange Polynomial(多項式補間) (math/others/lagrange.hpp)
• Matrix(行列) (math/others/matrix.hpp)
• Fraction(有理数型) (math/others/rational.hpp)

others

• Mo's Algorithm (others/mo.hpp)
• others/monoid.hpp
• others/monoid2.hpp
• Random(乱数) (others/random.hpp)
• Timer(タイマー) (others/timer.hpp)

string

• Manacher Algorithm(最長回文) (string/manacher.hpp)
• Rolling Hash(ローリングハッシュ) (string/rolling-hash.hpp)
• string/run-length.hpp
• Z Algorithm (string/z-algorithm.hpp)

template

• template/alias.hpp
• template/debug.hpp
• template/func.hpp
• template/macro.hpp
• template/template.hpp
• template/type-traits.hpp
• template/util.hpp

Verification Files

test/aoj/ALDS1

• test/aoj/ALDS1/ALDS1_14_B.test.cpp
• test/aoj/ALDS1/ALDS1_1_C_1.test.cpp
• test/aoj/ALDS1/ALDS1_1_C_2.test.cpp

test/aoj/CGL

• test/aoj/CGL/CGL_1_A.test.cpp
• test/aoj/CGL/CGL_1_B.test.cpp
• test/aoj/CGL/CGL_1_C.test.cpp
• test/aoj/CGL/CGL_2_A.test.cpp
• test/aoj/CGL/CGL_2_B.test.cpp
• test/aoj/CGL/CGL_2_C.test.cpp
• test/aoj/CGL/CGL_2_D.test.cpp
• test/aoj/CGL/CGL_3_A.test.cpp
• test/aoj/CGL/CGL_3_B.test.cpp
• test/aoj/CGL/CGL_3_C.test.cpp

test/aoj/DSL

• test/aoj/DSL/DSL_1_A.test.cpp
• test/aoj/DSL/DSL_1_B.test.cpp
• test/aoj/DSL/DSL_2_A.test.cpp
• test/aoj/DSL/DSL_2_B.test.cpp
• test/aoj/DSL/DSL_2_B2.test.cpp
• test/aoj/DSL/DSL_2_D.test.cpp
• test/aoj/DSL/DSL_2_E.test.cpp
• test/aoj/DSL/DSL_2_F.test.cpp
• test/aoj/DSL/DSL_2_G.test.cpp
• test/aoj/DSL/DSL_2_H.test.cpp
• test/aoj/DSL/DSL_2_I.test.cpp

test/aoj/GRL

• test/aoj/GRL/GRL_1_A.test.cpp
• test/aoj/GRL/GRL_1_B.test.cpp
• test/aoj/GRL/GRL_1_C.test.cpp
• test/aoj/GRL/GRL_2_A.test.cpp
• test/aoj/GRL/GRL_2_A_2.test.cpp
• test/aoj/GRL/GRL_3_C.test.cpp
• test/aoj/GRL/GRL_4_A.test.cpp
• test/aoj/GRL/GRL_4_B.test.cpp
• test/aoj/GRL/GRL_5_A.test.cpp
• test/aoj/GRL/GRL_5_B.test.cpp
• test/aoj/GRL/GRL_5_C_1.test.cpp
• test/aoj/GRL/GRL_5_C_2.test.cpp
• test/aoj/GRL/GRL_6_A.test.cpp
• test/aoj/GRL/GRL_6_A_2.test.cpp

test/aoj/ITP1

• test/aoj/ITP1/ITP1_3_D.test.cpp

test/aoj/NTL

• test/aoj/NTL/NTL_1_A.test.cpp
• test/aoj/NTL/NTL_1_B.test.cpp
• test/aoj/NTL/NTL_1_C.test.cpp
• test/aoj/NTL/NTL_1_D.test.cpp

test/atcoder

• test/atcoder/arc070-c.test.cpp

test/yosupo/convolution

• test/yosupo/convolution/convolution_mod.test.cpp
• test/yosupo/convolution/convolution_mod_1000000007.test.cpp
• test/yosupo/convolution/gcd_convolution.test.cpp
• test/yosupo/convolution/lcm_convolution.test.cpp

test/yosupo/data_strucuture

• test/yosupo/data_strucuture/associative_array.test.cpp
• test/yosupo/data_strucuture/line_add_get_min.test.cpp
• test/yosupo/data_strucuture/persistent_unionfind.test.cpp
• test/yosupo/data_strucuture/persistent_unionfind2.test.cpp
• test/yosupo/data_strucuture/point_add_range_sum1.test.cpp
• test/yosupo/data_strucuture/point_add_range_sum2.test.cpp
• test/yosupo/data_strucuture/point_add_range_sum3.test.cpp
• test/yosupo/data_strucuture/point_set_range_composite.test.cpp
• test/yosupo/data_strucuture/predecessor_problem.test.cpp
• test/yosupo/data_strucuture/range_affine_range_sum.test.cpp
• test/yosupo/data_strucuture/range_chmin_chmax_add_range_sum.test.cpp
• test/yosupo/data_strucuture/range_kth_smallest.test.cpp
• test/yosupo/data_strucuture/segment_add_get_min.test.cpp
• test/yosupo/data_strucuture/set_xor_min.test.cpp
• test/yosupo/data_strucuture/static_range_inversions_query.test.cpp
• test/yosupo/data_strucuture/static_range_sum.test.cpp
• test/yosupo/data_strucuture/staticrmq.test.cpp
• test/yosupo/data_strucuture/staticrmq2.test.cpp
• test/yosupo/data_strucuture/unionfind.test.cpp

test/yosupo/graph

• test/yosupo/graph/scc.test.cpp
• test/yosupo/graph/shortest_path.test.cpp

test/yosupo/math

• test/yosupo/math/discrete-logarithm-mod.test.cpp
• test/yosupo/math/factorize.test.cpp
• test/yosupo/math/kth_root_integer.test.cpp
• test/yosupo/math/sharp_p_subset_sum.test.cpp
• test/yosupo/math/sqrt_mod.test.cpp
• test/yosupo/math/two_sat.test.cpp

test/yosupo/matrix

• test/yosupo/matrix/matrix_det.test.cpp
• test/yosupo/matrix/matrix_product.test.cpp

test/yosupo/polynomial

• test/yosupo/polynomial/division_of_polynomials.test.cpp
• test/yosupo/polynomial/exp_of_formal_power_series.test.cpp
• test/yosupo/polynomial/inv_of_formal_power_series.test.cpp
• test/yosupo/polynomial/log_of_formal_power_series.test.cpp
• test/yosupo/polynomial/multipoint_evaluation.test.cpp
• test/yosupo/polynomial/polynomial_interpolation.test.cpp
• test/yosupo/polynomial/polynomial_taylor_shift.test.cpp
• test/yosupo/polynomial/pow_of_formal_power_series.test.cpp
• test/yosupo/polynomial/sqrt_of_formal_power_series.test.cpp

test/yosupo/string

• test/yosupo/string/enumerate_palindromes.test.cpp
• test/yosupo/string/zalgorithm.test.cpp

test/yosupo/tree

• test/yosupo/tree/catersian_tree.test.cpp
• test/yosupo/tree/lca1.test.cpp
• test/yosupo/tree/lca2.test.cpp
• test/yosupo/tree/tree_diameter.test.cpp

test/yukicoder

• test/yukicoder/1236.test.cpp
• test/yukicoder/1435.test.cpp
• test/yukicoder/1469.test.cpp
• test/yukicoder/3030.test.cpp