MtSaka's Library

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

Library Files

dp/

• Alien DP (dp/alien-dp.hpp)
• Simple LARSCH (dp/larsch.hpp)
• Monge DP (dp/monge.hpp)
• Smawk's Algorithm (dp/smawk.hpp)

ds/cht/

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

ds/heap/

• Double-Ended Priority Queue (ds/heap/double-ended-priority-queue.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)
• Sliding Window Aggregation(SWAG) (ds/others/sliding-window-aggregation.hpp)
• Slope Trick (ds/others/slope-trick.hpp)

ds/segment/

• ds/segment/binary-indexed-tree-01.hpp
• 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)
• Range Assign Segmnet Tree (ds/segment/range-assign-segmnet-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)
• Static Range Count Distinct (ds/segment/static-range-count-distinct.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/

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

graph/flow/

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

graph/mst/

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

graph/others/

• Cycle Detection(閉路検出) (graph/others/detect-cycle.hpp)
• Enumerate Cliques (graph/others/enumerate-cliques.hpp)
• Enumerate Triangles (graph/others/enumerate-triangles.hpp)
• Maximum Independent Set (graph/others/maximum-independet-set.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)
• Lowest Common Ancestor(最小共通祖先) (graph/tree/fast-lowest-common-ancestor.hpp)
• Heavy-Light Decomposition(HL分解) (graph/tree/heavy-light-decomposition.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)
• Large Convolution (math/convolution/large-convolution.hpp)
• LCM Convolution (math/convolution/lcm-convolution.hpp)
• Min-Plus Convolution (Convex and Convex) (math/convolution/min-plus-convolution-convex.hpp)
• Min-Plus Convolution (Convex and Arbitrary) (math/convolution/min-plus-convolution.hpp)
• Convolution on the Multiplicative Monoid of Z/pZ (math/convolution/mul-convolution-mod-p.hpp)

math/fps/

• Formal Power Series(形式的冪級数) (math/fps/fps.hpp)
• Middle Product (math/fps/middle-product.hpp)
• Multipoint Evaluation (Geometric Sequence) (math/fps/multipoint-evaluation-geometric.hpp)
• Multipoint Evaluation(多点評価) (math/fps/multipoint-evaluation.hpp)
• Polynomial Interpolation (Geometric Sequence) (math/fps/polynomial-interpolation-gemoetric.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 Enumeration(約数列挙) (math/number/divisor.hpp)
• Factor Count(約数個数) (math/number/factor-cnt.hpp)
• math/number/floor-sum.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 Count (math/number/prime-count.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/number/sum-of-multiplicative-function.hpp

math/others/

• Combinatorics(組み合わせ) (math/others/combinatorics.hpp)
• Lagrange Interpolation(ラグランジュ補間) (math/others/lagrange-interpolation.hpp)
• Matrix(行列) (math/others/matrix.hpp)
• Fraction(有理数型) (math/others/rational.hpp)

others/

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

scrap/

• scrap/static-top-tree.hpp
• scrap/trie.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/func.hpp
• template/in.hpp
• template/macro.hpp
• template/out.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/yosupo/convolution/

• test/yosupo/convolution/convolution_mod.test.cpp
• test/yosupo/convolution/convolution_mod_1000000007.test.cpp
• test/yosupo/convolution/convolution_mod_large.test.cpp
• test/yosupo/convolution/gcd_convolution.test.cpp
• test/yosupo/convolution/lcm_convolution.test.cpp
• test/yosupo/convolution/min_plus_convolution_convex_arbitrary.test.cpp
• test/yosupo/convolution/min_plus_convolution_convex_convex.test.cpp
• test/yosupo/convolution/mul_modp_convolution.test.cpp

test/yosupo/data_strucuture/

• test/yosupo/data_strucuture/associative_array.test.cpp
• test/yosupo/data_strucuture/double_ended_priority_queue.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/point_set_range_composite_large_array.test.cpp
• test/yosupo/data_strucuture/point_set_range_frequency.test.cpp
• test/yosupo/data_strucuture/predecessor_problem.test.cpp
• test/yosupo/data_strucuture/queue_operate_all_composite.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/range_set_range_composite.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_count_distinct.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/data_strucuture/unionfind_with_potential.test.cpp
• test/yosupo/data_strucuture/unionfind_with_potential_non_commutative_group.test.cpp
• test/yosupo/data_strucuture/vertex_add_subtree_sum.test.cpp

test/yosupo/enumerative_combinatorics/

• test/yosupo/enumerative_combinatorics/binominal_coefficient_prime_mod.test.cpp
• test/yosupo/enumerative_combinatorics/sharp_p_subset_sum.test.cpp

test/yosupo/graph/

• test/yosupo/graph/counting_spanning_tree_directed.test.cpp
• test/yosupo/graph/counting_spanning_tree_undirected.test.cpp
• test/yosupo/graph/enumerate_cliques.test.cpp
• test/yosupo/graph/enumerate_triangles.test.cpp
• test/yosupo/graph/maximum_independent_set.test.cpp
• test/yosupo/graph/minimum_spanning_tree.test.cpp
• test/yosupo/graph/scc.test.cpp
• test/yosupo/graph/shortest_path.test.cpp

test/yosupo/linear_algebra/

• test/yosupo/linear_algebra/matrix_det.test.cpp
• test/yosupo/linear_algebra/matrix_product.test.cpp
• test/yosupo/linear_algebra/pow_of_matrix.test.cpp

test/yosupo/number_theory/

• test/yosupo/number_theory/counting_primes.test.cpp
• test/yosupo/number_theory/discrete_logarithm_mod.test.cpp
• test/yosupo/number_theory/enumerate_primes.test.cpp
• test/yosupo/number_theory/enumerate_quotients.test.cpp
• test/yosupo/number_theory/factorize.test.cpp
• test/yosupo/number_theory/kth_root_integer.test.cpp
• test/yosupo/number_theory/sqrt_mod.test.cpp
• test/yosupo/number_theory/sum_of_floor_of_linear.test.cpp

test/yosupo/other/

• test/yosupo/other/two_sat.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/multipoint_evaluation_on_geometric_sequence.test.cpp
• test/yosupo/polynomial/polynomial_interpolation.test.cpp
• test/yosupo/polynomial/polynomial_interpolation_on_geometric_sequence.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/jump_on_tree.test.cpp
• test/yosupo/tree/lca1.test.cpp
• test/yosupo/tree/lca2.test.cpp
• test/yosupo/tree/lca3.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