C++ library

Library Files

algebraic-structure

• algebraic-structure/group.hpp
• algebraic-structure/magma.hpp
• algebraic-structure/monoid-action.hpp
• algebraic-structure/monoid.hpp
• algebraic-structure/util.hpp

algorithm

• algorithm/cartesian-tree.hpp
• algorithm/mo.hpp
• monotone minima (algorithm/monotone-minima.hpp)
• algorithm/smawk.hpp
• algorithm/ternary-search.hpp

automaton

• 決定性有限オートマトン(DFA)(small) (automaton/dfa-small.hpp)
• 決定性有限オートマトン(DFA) (automaton/dfa.hpp)
• 非決定性有限オートマトン(NFA)(small) (automaton/nfa-small.hpp)
• 非決定性有限オートマトン(NFA) (automaton/nfa.hpp)

binary-search-tree

• 挿入/削除の可能な配列 (乱択二分探索木) (binary-search-tree/rbst-array.hpp)
• Randomized Binary Search Tree (基底クラス) (binary-search-tree/rbst-base.hpp)

convolution

• gcd 畳み込み (convolution/gcd.hpp)
• 任意 mod 畳み込み (convolution/intmod.hpp)
• lcm 畳み込み (convolution/lcm.hpp)
• min-plus 畳み込み (convex) (convolution/min-plus-convex.hpp)
• 畳み込み mod 2^64 (convolution/mod2_64.hpp)

data-structure

• Binary Indexed Tree (data-structure/binary-indexed-tree.hpp)
• Binary Trie (data-structure/binary-trie.hpp)
• data-structure/bit-vector.hpp
• 座標圧縮 (data-structure/compress.hpp)
• Double Ended Priority Queue (data-structure/double-ended-priority-queue.hpp)
• Dynamic Bitset (data-structure/dynamic-bitset.hpp)
• Dynamic Li Chao Tree (data-structure/dynamic-li-chao-tree.hpp)
• Foldable Deque (data-structure/foldable-deque.hpp)
• Foldable Queue (data-structure/foldable-queue.hpp)
• 整数の集合(64分木) (data-structure/integer-set.hpp)
• 区間集合 (data-structure/interval-set.hpp)
• Li Chao Tree (data-structure/li-chao-tree.hpp)
• Persistent Array (data-structure/persistent-array.hpp)
• Range Add Range Min (data-structure/range-add-range-min.hpp)
• Range Add Range Positive Sum (data-structure/range-add-range-positive-sum.hpp)
• data-structure/range-array.hpp
• data-structure/simple-queue.hpp
• Slope Trick (data-structure/slope-trick.hpp)
• data-structure/sparse-table.hpp
• data-structure/wavelet-matrix-with-segment-tree.hpp
• data-structure/wavelet-matrix-with-weight.hpp
• Wavelet Matrix (data-structure/wavelet-matrix.hpp)

fft

• NTT (数論変換) (fft/ntt.hpp)

flow

• Max Flow (flow/max-flow.hpp)
• Project Selection Problem (flow/project-selection-problem.hpp)

fps

• Berlekamp-Massey (fps/berlekamp-massey.hpp)
• Bostan-Mori (fps/bostan-mori.hpp)
• FPS 合成 (fps/composition.hpp)
• 逆関数 (fps/compositional-inv.hpp)
• Count Subset Sum (fps/count-subset-sum.hpp)
• 有名数列 (fps/famous-sequences.hpp)
• fps/formal-power-series.hpp
• fps/fps-2d-arbitrary.hpp
• fps/fps-2d-ntt-friendly.hpp
• 二変数形式的冪級数 (fps/fps-2d.hpp)
• fps/fps-arbitrary.hpp
• fps/fps-ntt-friendly.hpp
• fps/fps-rational.hpp
• fps/fps-sqrt.hpp
• Interpolate (fps/interpolate.hpp)
• Inverse の次数シフト (fps/inverse-shift.hpp)
• 線形漸化式用 (fps/linearly-recurrent-sequence.hpp)
• 単項式基底から Newton 基底への変換 (fps/monomial-basis-to-newton-basis.hpp)
• 多点評価 (fps/multipoint-evaluation.hpp)
• Newton 基底から単項式基底への変換 (fps/newton-basis-to-monomial-basis.hpp)
• P-recursive (fps/p-recursive.hpp)
• Polynomial Gcd (fps/polynomial-gcd.hpp)
• 多項式補間 (fps/polynomial-interpolation.hpp)
• Power Projection (fps/power-projection.hpp)
• 多項式の Prefix Sum (fps/prefix-sum-of-polynomial.hpp)
• 多項式の積 (fps/product-of-polynomials.hpp)
• Relaxed (fps/relaxed.hpp)
• 評価点シフト (fps/sampling-points-shift.hpp)
• Sparse な FPS 演算 (fps/sparse.hpp)
• $\sum_{i}r^i poly(i)$ (fps/sum-of-exp-poly.hpp)
• 有理式の和 (fps/sum-of-rationals.hpp)
• Taylor Shift (fps/taylor-shift.hpp)

geometry

• 円 (geometry/circle.hpp)
• 二次元幾何の基本要素 (geometry/geometry-base.hpp)
• 半平面交差 (geometry/halfplane-intersection.hpp)
• 直線 (geometry/line.hpp)
• 多角形 (geometry/polygon.hpp)
• 線分 (geometry/segment.hpp)

geometry-3d

• 三次元幾何の基本要素 (geometry-3d/geometry-base.hpp)
• 三次元空間上の直線 (geometry-3d/line.hpp)
• 三次元空間上の平面 (geometry-3d/plane.hpp)
• 三次元空間上の線分 (geometry-3d/segment.hpp)
• 三次元空間上の円と球 (geometry-3d/sphere.hpp)
• 三次元空間上の三角形 (geometry-3d/triangle.hpp)

graph

• Compressed Sparse Row (graph/csr.hpp)
• Graph (graph/graph.hpp)
• Shortest Path (graph/shortest-path.hpp)

heuristic

• Beam Search (heuristic/beam-search.hpp)
• heuristic/time-keeper.hpp

math

• math/barrett.hpp
• モノイド版 Floor Sum (math/floor-monoid-product.hpp)
• Floor Sum (math/floor-sum.hpp)
• 有理数 (math/fraction.hpp)
• Garner のアルゴリズム (オンライン) (math/garner-online.hpp)
• Garner のアルゴリズム (math/garner.hpp)
• Min of Mod of Linear (math/min-of-mod-of-linear.hpp)
• 多項式版 floor sum (math/polynomial-floor-sum.hpp)
• math/root-extension.hpp
• 有理数 (約分なし) (math/simple-fraction.hpp)
• Stern-Brocot Tree (math/stern-brocot-tree.hpp)
• math/util.hpp

matrix

• Matrix Mod 2 (matrix/matrix-mod2.hpp)
• matrix/matrix.hpp
• 多項式行列の prefix product (matrix/polynomial-matrix-prefix-product.hpp)

modint

• 一般 mod での二項係数 (modint/binomial-general-mod.hpp)
• modint/dynamic-modint.hpp
• 階乗, 二項係数 (modint/factorial.hpp)
• modint/mod-sqrt.hpp
• modint/modint-m127.hpp
• modint/modint-m61.hpp
• modint/modint.hpp
• modint/modint64.hpp
• 複数の要素の逆元を一括で計算 (modint/multi-inverse.hpp)
• Power Table (modint/power-table.hpp)
• Power Tower Modint (modint/power-tower-modint.hpp)

number-theory

• Count Square Free (number-theory/count-square-free.hpp)
• Dirichlet 積の prefix sum (number-theory/dirichlet-series-prefix-sum.hpp)
• 約数・倍数変換 (number-theory/divisor-multiple-transform.hpp)
• 商の列挙 (number-theory/enumerate-quotients.hpp)
• 形式的 Dirichlet 級数 (number-theory/formal-dirichlet-series.hpp)
• Lucy DP (number-theory/lucy-dp.hpp)
• Miller-Rabin 素数判定 (number-theory/miller-rabin.hpp)
• Mobius Function (number-theory/mobius-function.hpp)
• Pollard's rho algorithm (number-theory/pollard-rho.hpp)
• 素数カウント (number-theory/prime-count.hpp)
• 素数の剰余類別集計 (number-theory/prime-residue.hpp)
• 素数篩 (number-theory/prime-sieve.hpp)
• 原始根 (number-theory/primitive-root.hpp)
• 区間篩 (number-theory/range-sieve.hpp)
• number-theory/sum-of-multiplicative-function.hpp
• Totient Function (number-theory/totient-function.hpp)

segment-tree

• 2D Dual Segment Tree (segment-tree/dual-segment-tree-2d.hpp)
• Dual Segment Tree (segment-tree/dual-segment-tree.hpp)
• Dynamic 2D Dual Segment Tree (segment-tree/dynamic-dual-segment-tree-2d.hpp)
• Dynamic Dual Segment Tree (segment-tree/dynamic-dual-segment-tree.hpp)
• Dynamic 2D Segment Tree (segment-tree/dynamic-segment-tree-2d.hpp)
• Dynamic Segment Tree (segment-tree/dynamic-segment-tree.hpp)
• よく使う Lazy Segment Tree (segment-tree/lazy-segment-tree-util.hpp)
• Lazy Segment Tree (segment-tree/lazy-segment-tree.hpp)
• Persistent Segment Tree (segment-tree/persistent-segment-tree.hpp)
• Range Set Range Prod (segment-tree/range-set-range-prod.hpp)
• 2D Segment Tree (segment-tree/segment-tree-2d.hpp)
• よく使う Segment Tree (segment-tree/segment-tree-util.hpp)
• Segment Tree (segment-tree/segment-tree.hpp)

set

• set/and-convolution.hpp
• Polynomial Composite Set Power Series (set/composite-set-power-series.hpp)
• Exp Of Set Power Series (set/exp-of-set-power-series.hpp)
• set/hadamard-transform.hpp
• set/or-convolution.hpp
• Power Projection Of Set Power Series (set/power-projection-of-set-power-series.hpp)
• Subset Convolution (set/subset-convolution.hpp)
• set/xor-convolution.hpp
• set/zeta-mobius-transform.hpp

string

• string/rolling-hash-base.hpp
• string/rolling-hash-monoid.hpp
• string/rolling-hash-segment-tree.hpp
• string/rolling-hash-value.hpp
• string/rolling-hash.hpp
• Trie (string/trie.hpp)
• string/util.hpp
• Z-algorithm (string/z-algorithm.hpp)

template

• template/debug.hpp
• template/inout.hpp
• template/macro.hpp
• template/template.hpp
• template/util.hpp

tools

• tools/library_checker_coverage.py
• tools/sanitizer-default-options.cpp

tree

• 木上の距離 (tree/distance.hpp)
• Heavy Light Decomposition (tree/heavy-light-decomposition.hpp)
• LCA ベースの Auxiliary Tree (tree/lca-auxiliary-tree.hpp)
• Lowest Common Ancestor (tree/lowest-common-ancestor.hpp)
• 全方位木 DP (tree/rerooting-dp.hpp)
• 木の直径 (tree/tree-diameter.hpp)
• Tree Jump (tree/tree-jump.hpp)

union-find

• Persistent Potentialized Union Find (union-find/persistent-potentialized-union-find.hpp)
• Persistent Union Find (union-find/persistent-union-find.hpp)
• ポテンシャル付き Union Find (union-find/potentialized-union-find.hpp)
• Union Find (union-find/union-find.hpp)

util

• Random (util/random.hpp)
• XOR shift (util/xorshift.hpp)

Verification Files

verify/algorithm

• verify/algorithm/LC_cartesian_tree.test.cpp
• verify/algorithm/LC_static_range_count_distinct.test.cpp

verify/binary-search-tree

• verify/binary-search-tree/UNIT_rbst_array.test.cpp

verify/convolution

• verify/convolution/LC_convolution_mod.test.cpp
• verify/convolution/LC_convolution_mod_1000000007.test.cpp
• verify/convolution/LC_convolution_mod_2_64.test.cpp
• verify/convolution/LC_gcd_convolution.test.cpp
• verify/convolution/LC_lcm_convolution.test.cpp
• verify/convolution/LC_min_plus_convolution_convex_arbitrary.test.cpp
• verify/convolution/LC_min_plus_convolution_convex_convex.test.cpp

verify/data-structure

• verify/data-structure/LC_deque_operate_all_composite.test.cpp
• verify/data-structure/LC_double_ended_priority_queue.test.cpp
• verify/data-structure/LC_line_add_get_min.dynamic_li_chao_tree.test.cpp
• verify/data-structure/LC_line_add_get_min.test.cpp
• verify/data-structure/LC_point_add_range_sum.test.cpp
• verify/data-structure/LC_point_add_rectangle_sum.wavelet_matrix.test.cpp
• verify/data-structure/LC_predecessor_problem.test.cpp
• verify/data-structure/LC_queue_operate_all_composite.test.cpp
• verify/data-structure/LC_range_add_range_min.test.cpp
• verify/data-structure/LC_range_kth_smallest.test.cpp
• verify/data-structure/LC_rectangle_sum.wavelet_matrix.test.cpp
• verify/data-structure/LC_segment_add_get_min.dynamic_li_chao_tree.test.cpp
• verify/data-structure/LC_segment_add_get_min.test.cpp
• verify/data-structure/LC_set_xor_min.test.cpp
• verify/data-structure/LC_static_range_frequency.test.cpp
• verify/data-structure/LC_static_range_sum.test.cpp
• verify/data-structure/LC_static_range_sum_with_upper_bound.test.cpp
• verify/data-structure/LC_staticrmq.test.cpp
• verify/data-structure/UNIT_dynamic_bitset.test.cpp
• verify/data-structure/UNIT_interval_set.test.cpp
• verify/data-structure/UNIT_range_add_range_positive_sum.test.cpp
• verify/data-structure/UNIT_simple_queue.test.cpp

verify/flow

• verify/flow/AOJ_GRL_6_A.test.cpp

verify/fps

• verify/fps/LC_bell_number.test.cpp
• verify/fps/LC_composition_of_formal_power_series.test.cpp
• verify/fps/LC_composition_of_formal_power_series_large.test.cpp
• verify/fps/LC_compositional_inverse_of_formal_power_series.test.cpp
• verify/fps/LC_compositional_inverse_of_formal_power_series_large.test.cpp
• verify/fps/LC_consecutive_terms_of_linear_recurrent_sequence.test.cpp
• verify/fps/LC_conversion_from_monomial_basis_to_newton_basis.test.cpp
• verify/fps/LC_convolution_mod.relaxed.test.cpp
• verify/fps/LC_convolution_mod.semirelaxed.test.cpp
• verify/fps/LC_division_of_polynomials.test.cpp
• verify/fps/LC_exp_of_formal_power_series.relaxed.test.cpp
• verify/fps/LC_exp_of_formal_power_series.test.cpp
• verify/fps/LC_exp_of_formal_power_series_sparse.test.cpp
• verify/fps/LC_factorial.p_recursive.test.cpp
• verify/fps/LC_find_linear_recurrence.test.cpp
• verify/fps/LC_inv_of_formal_power_series.relaxed.test.cpp
• verify/fps/LC_inv_of_formal_power_series.test.cpp
• verify/fps/LC_inv_of_formal_power_series_2d.test.cpp
• verify/fps/LC_inv_of_formal_power_series_sparse.test.cpp
• verify/fps/LC_inv_of_polynomials.test.cpp
• verify/fps/LC_kth_term_of_linearly_recurrent_sequence.test.cpp
• verify/fps/LC_log_of_formal_power_series.relaxed.test.cpp
• verify/fps/LC_log_of_formal_power_series.test.cpp
• verify/fps/LC_log_of_formal_power_series_sparse.test.cpp
• verify/fps/LC_montmort_number_mod.test.cpp
• verify/fps/LC_multipoint_evaluation.test.cpp
• verify/fps/LC_multipoint_evaluation_on_geometric_sequence.test.cpp
• verify/fps/LC_partition_function.test.cpp
• verify/fps/LC_polynomial_interpolation.test.cpp
• verify/fps/LC_polynomial_interpolation_on_geometric_sequence.test.cpp
• verify/fps/LC_polynomial_taylor_shift.test.cpp
• verify/fps/LC_pow_of_formal_power_series.test.cpp
• verify/fps/LC_pow_of_formal_power_series_sparse.test.cpp
• verify/fps/LC_product_of_polynomial_sequence.test.cpp
• verify/fps/LC_sharp_p_subset_sum.test.cpp
• verify/fps/LC_shift_of_sampling_points_of_polynomial.test.cpp
• verify/fps/LC_sqrt_of_formal_power_series.relaxed.test.cpp
• verify/fps/LC_sqrt_of_formal_power_series.test.cpp
• verify/fps/LC_sqrt_of_formal_power_series_sparse.test.cpp
• verify/fps/LC_stirling_number_of_the_first_kind.test.cpp
• verify/fps/LC_stirling_number_of_the_first_kind_fixed_k.test.cpp
• verify/fps/LC_stirling_number_of_the_second_kind.test.cpp
• verify/fps/LC_stirling_number_of_the_second_kind_fixed_k.test.cpp
• verify/fps/LC_sum_of_exponential_times_polynomial.test.cpp
• verify/fps/LC_sum_of_exponential_times_polynomial_limit.test.cpp
• verify/fps/UNIT_fps_2d.test.cpp
• verify/fps/UNIT_newton_basis_to_monomial_basis.test.cpp
• verify/fps/UNIT_prefix_sum_of_polynomial.test.cpp

verify/geometry

• verify/geometry/AOJ_CGL_1_A.test.cpp
• verify/geometry/AOJ_CGL_1_B.test.cpp
• verify/geometry/AOJ_CGL_1_C.test.cpp
• verify/geometry/AOJ_CGL_2_A.test.cpp
• verify/geometry/AOJ_CGL_2_B.test.cpp
• verify/geometry/AOJ_CGL_2_C.test.cpp
• verify/geometry/AOJ_CGL_2_D.test.cpp
• verify/geometry/AOJ_CGL_3_A.test.cpp
• verify/geometry/AOJ_CGL_3_B.test.cpp
• verify/geometry/AOJ_CGL_3_C.test.cpp
• verify/geometry/AOJ_CGL_4_A.test.cpp
• verify/geometry/AOJ_CGL_4_B.test.cpp
• verify/geometry/AOJ_CGL_4_C.test.cpp
• verify/geometry/AOJ_CGL_7_A.test.cpp
• verify/geometry/AOJ_CGL_7_D.test.cpp
• verify/geometry/AOJ_CGL_7_E.test.cpp
• verify/geometry/AOJ_CGL_7_F.test.cpp
• verify/geometry/AOJ_CGL_7_G.test.cpp
• verify/geometry/AOJ_CGL_7_I.test.cpp
• verify/geometry/UNIT_halfplane_intersection.test.cpp
• verify/geometry/UNIT_polygon.test.cpp

verify/geometry-3d

• verify/geometry-3d/UNIT_geometry_3d.test.cpp

verify/graph

• verify/graph/LC_shortest_path.test.cpp
• verify/graph/UNIT_graph.test.cpp
• verify/graph/UNIT_shortest_path.test.cpp

verify/math

• verify/math/LC_kth_root_integer.test.cpp
• verify/math/LC_min_of_mod_of_linear.test.cpp
• verify/math/LC_rational_approximation.test.cpp
• verify/math/LC_stern_brocot_tree.test.cpp
• verify/math/LC_sum_of_floor_of_linear.monoid.test.cpp
• verify/math/LC_sum_of_floor_of_linear.test.cpp
• verify/math/UNIT_barrett.test.cpp
• verify/math/UNIT_fraction.test.cpp
• verify/math/UNIT_util.test.cpp

verify/matrix

• verify/matrix/LC_inverse_matrix.test.cpp
• verify/matrix/LC_inverse_matrix_mod_2.test.cpp
• verify/matrix/LC_matrix_det.test.cpp
• verify/matrix/LC_matrix_det_mod_2.test.cpp
• verify/matrix/LC_matrix_product.test.cpp
• verify/matrix/LC_matrix_product_mod_2.test.cpp
• verify/matrix/LC_matrix_rank_mod_2.test.cpp
• verify/matrix/LC_pow_of_matrix.test.cpp

verify/modint

• verify/modint/LC_binomial_coefficient.test.cpp
• verify/modint/LC_binomial_coefficient_prime_mod.test.cpp
• verify/modint/LC_sqrt_mod.test.cpp
• verify/modint/UNIT_dynamic_modint.test.cpp
• verify/modint/UNIT_mod_sqrt.test.cpp
• verify/modint/UNIT_modint.test.cpp
• verify/modint/UNIT_modint64.test.cpp
• verify/modint/UNIT_multi_inverse.test.cpp
• verify/modint/UNIT_power_tower_modint.test.cpp

verify/number-theory

• verify/number-theory/LC_counting_primes.test.cpp
• verify/number-theory/LC_counting_squarefrees.test.cpp
• verify/number-theory/LC_enumerate_primes.test.cpp
• verify/number-theory/LC_enumerate_quotients.test.cpp
• verify/number-theory/LC_factorize.test.cpp
• verify/number-theory/LC_primality_test.test.cpp
• verify/number-theory/LC_primitive_root.test.cpp
• verify/number-theory/LC_sum_of_multiplicative_function.test.cpp
• verify/number-theory/LC_sum_of_totient_function.test.cpp
• verify/number-theory/UNIT_enumerate_quotients.test.cpp
• verify/number-theory/UNIT_mobius_function.test.cpp
• verify/number-theory/UNIT_pollard_rho_divisors.test.cpp
• verify/number-theory/UNIT_prime_residue.test.cpp
• verify/number-theory/UNIT_prime_sieve.test.cpp
• verify/number-theory/UNIT_range_sieve_table.test.cpp

verify/segment-tree

• verify/segment-tree/AOJ_DSL_2_G.test.cpp
• verify/segment-tree/LC_point_add_range_sum.test.cpp
• verify/segment-tree/LC_point_add_rectangle_sum.dynamic_segment_tree_2d.test.cpp
• verify/segment-tree/LC_point_add_rectangle_sum.segment_tree_2d.test.cpp
• verify/segment-tree/LC_point_set_range_composite.test.cpp
• verify/segment-tree/LC_point_set_range_composite_large_array.dynamic_segment_tree.test.cpp
• verify/segment-tree/LC_range_affine_point_get.dynamic_dual_segment_tree.test.cpp
• verify/segment-tree/LC_range_affine_point_get.test.cpp
• verify/segment-tree/LC_range_affine_range_sum.test.cpp
• verify/segment-tree/LC_range_set_range_composite.test.cpp
• verify/segment-tree/LC_rectangle_add_point_get.dual_segment_tree_2d.test.cpp
• verify/segment-tree/LC_rectangle_add_point_get.dynamic_dual_segment_tree_2d.test.cpp

verify/set

• verify/set/LC_bitwise_and_convolution.or.test.cpp
• verify/set/LC_bitwise_and_convolution.test.cpp
• verify/set/LC_bitwise_xor_convolution.test.cpp
• verify/set/LC_exp_of_set_power_series.test.cpp
• verify/set/LC_polynomial_composite_set_power_series.test.cpp
• verify/set/LC_power_projection_of_set_power_series.test.cpp
• verify/set/LC_subset_convolution.test.cpp
• verify/set/UNIT_composite_set_power_series.test.cpp

verify/string

• verify/string/LC_zalgorithm.test.cpp
• verify/string/UNIT_rolling_hash.test.cpp
• verify/string/UNIT_trie.test.cpp

verify/template

• verify/template/UNIT_inout.test.cpp

verify/tree

• verify/tree/LC_jump_on_tree.test.cpp
• verify/tree/LC_lowest_common_ancestor.test.cpp
• verify/tree/LC_tree_diameter.test.cpp
• verify/tree/LC_tree_path_composite_sum.test.cpp
• verify/tree/LC_vertex_set_path_composite.test.cpp
• verify/tree/UNIT_distance.test.cpp
• verify/tree/UNIT_lca_auxiliary_tree.test.cpp

verify/union-find

• verify/union-find/LC_persistent_unionfind.test.cpp
• verify/union-find/LC_unionfind.test.cpp
• verify/union-find/LC_unionfind_with_potential.test.cpp
• verify/union-find/LC_unionfind_with_potential_non_commutative_group.test.cpp

reports

• Library Checker coverage (library-checker-coverage)