C++ library

Library Files

algorithm

• monotone minima (algorithm/monotone-minima.hpp)
• algorithm/smawk.hpp

automaton

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

convolution

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

data-structure

• Binary Indexed Tree (data-structure/binary-indexed-tree.hpp)
• 座標圧縮 (data-structure/compress.hpp)
• 整数の集合(64分木) (data-structure/integer-set.hpp)
• data-structure/range-array.hpp
• data-structure/simple-queue.hpp
• data-structure/sparse-table.hpp

fft

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

flow

• Max Flow (flow/max-flow.hpp)

fps

• Berlekamp-Massey (fps/berlekamp-massey.hpp)
• Bostan-Mori (fps/bostan-mori.hpp)
• FPS 合成 (fps/composition.hpp)
• 逆関数 (fps/compositional-inv.hpp)
• fps/formal-power-series.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)
• Multipoint Evaluation (fps/multipoint-evaluation.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)

heuristic

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

math

• モノイド版 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)
• LPF Table (math/lpf-table.hpp)
• 多項式版 floor sum (math/polynomial-floor-sum.hpp)
• 素数篩 (math/prime-sieve.hpp)
• 有理数 (約分なし) (math/simple-fraction.hpp)
• Stern-Brocot Tree (math/stern-brocot-tree.hpp)
• math/util.hpp

modint

• 階乗, 二項係数 (modint/factorial.hpp)
• modint/mod-pow.hpp
• modint/mod-sqrt.hpp
• modint/modint.hpp
• modint/modint261.hpp
• Power Table (modint/power-table.hpp)

number-theory

• Dirichlet 積の prefix sum (number-theory/dirichlet-series-prefix-sum.hpp)
• 約数・倍数変換 (number-theory/divisor-multiple-transform.hpp)
• 商の列挙 (number-theory/enumerate-quotients.hpp)
• 素数カウント (number-theory/prime-count.hpp)

segment-tree

• Dual Segment Tree (segment-tree/dual-segment-tree.hpp)
• Lazy Segment Tree (segment-tree/lazy-segment-tree.hpp)
• Segment Tree (長さを2冪にする) (segment-tree/segment-tree-pow2.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
• Subset Convolution (set/subset-convolution.hpp)
• set/xor-convolution.hpp
• set/zeta-mobius-transform.hpp

template

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

union-find

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

util

• Random (util/random.hpp)

Verification Files

verify/convolution

• verify/convolution/LC_convolution_mod.test.cpp
• verify/convolution/LC_convolution_mod_1000000007.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_point_add_range_sum.test.cpp
• verify/data-structure/LC_predecessor_problem.test.cpp
• verify/data-structure/LC_staticrmq.test.cpp

verify/flow

• verify/flow/AOJ_GRL_6_A.test.cpp

verify/fps

• 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_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_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_sparse.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_multipoint_evaluation.test.cpp
• verify/fps/LC_multipoint_evaluation_on_geometric_sequence.test.cpp
• verify/fps/LC_polynomial_interpolation.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_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_sum_of_exponential_times_polynomial.test.cpp
• verify/fps/LC_sum_of_exponential_times_polynomial_limit.test.cpp
• verify/fps/UNIT_prefix_sum_of_polynomial.test.cpp

verify/math

• 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/number-theory

• verify/number-theory/LC_counting_primes.test.cpp
• verify/number-theory/LC_enumerate_quotients.test.cpp

verify/segment-tree

• verify/segment-tree/LC_point_add_range_sum.pow2.test.cpp
• verify/segment-tree/LC_point_add_range_sum.test.cpp
• verify/segment-tree/LC_point_set_range_composite.test.cpp
• verify/segment-tree/LC_range_affine_point_get.test.cpp
• verify/segment-tree/LC_range_affine_range_sum.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_subset_convolution.test.cpp
• verify/set/UNIT_composite_set_power_series.test.cpp

verify/union-find

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