library

Library Files

Algorithm

• Cartesian Tree (Algorithm/cartesian.hpp)
• K-Project Selection (Algorithm/kprojectselection.hpp)
• Matroid (Algorithm/matroid.hpp)
• Maximal Rectangles (Algorithm/maximalrect.hpp)
• Mo's Algorithm (Algorithm/mo.hpp)
• Monotone Minima (Algorithm/monotoneminima.hpp)
• Project Selection (Algorithm/projectselection.hpp)
• Rollback Mo (Algorithm/rollbackmo.hpp)

Convolution

• Arbitrary Mod Convolution (Convolution/arbitrary.hpp)
• Bitwise Convolution (Convolution/bitwise.hpp)
• Convex Min Plus Convolution (Convolution/convexminplus.hpp)
• Divisor Multiple Transform (Convolution/divisor.hpp)
• Fast Fourier Transform (Convolution/fft.hpp)
• Multivariate Convolution (Convolution/multivariate.hpp)
• Multivarate Convolution Cyclic (Convolution/multivariatecyclic.hpp)
• Number Theoretic Transform (Convolution/ntt.hpp)
• Relaxed Convolution (Convolution/relax.hpp)
• Subset Convolution (Convolution/subset.hpp)

DataStructure

• 2D Binary Indexed Tree (DataStructure/2dbit.hpp)
• 2D Segment Tree (DataStructure/2dsegtree.hpp)
• Binary Indexed Tree (DataStructure/bit.hpp)
• Sliding Window Aggregation for deque (DataStructure/dequeswag.hpp)
• Disjoint Sparse Table (DataStructure/disjointsparsetable.hpp)
• Dual Segment Tree (DataStructure/dualsegtree.hpp)
• Fast Set (DataStructure/fastset.hpp)
• Hash Map (DataStructure/hashmap.hpp)
• Lazy Segment Tree (DataStructure/lazysegtree.hpp)
• Convex Hull Trick (Li Chao Tree) (DataStructure/lichaotree.hpp)
• Manhattan MST (DataStructure/manhattanmst.hpp)
• Persistent Array (DataStructure/persistentarray.hpp)
• Persistent Randomized Binary Search Tree (set) (DataStructure/persistentrbstset.hpp)
• Persistent Union Find (DataStructure/persistentunionfind.hpp)
• Range Linear Add Range Min (DataStructure/rangelinearaddrangemin.hpp)
• Range LIS Query (DataStructure/rangelis.hpp)
• Range Union Set (DataStructure/rangeunionset.hpp)
• Randomized Binary Search Tree (set) (DataStructure/rbstset.hpp)
• Rollback Union Find (DataStructure/rollbackunionfind.hpp)
• Segment Tree (DataStructure/segtree.hpp)
• Segment Tree Beats (DataStructure/segtreebeats.hpp)
• Slope Trick (DataStructure/slopetrick.hpp)
• Sortable Segment Tree (DataStructure/sortablesegtree.hpp)
• Static Rectangle Add Rectangle Sum (DataStructure/staticrectaddrectsum.hpp)
• Static Rectangle Sum (DataStructure/staticrectsum.hpp)
• Sliding Window Aggregation (DataStructure/swag.hpp)
• Union Find (DataStructure/unionfind.hpp)
• Area of Union of Rectangles (DataStructure/unionrect.hpp)
• Wavelet Matrix (DataStructure/wavelet.hpp)
• Weighted Union Find (DataStructure/weightedunionfind.hpp)

FPS

• Formal Power Series (Arbitrary mod) (FPS/arbitraryfps.hpp)
• Berlekamp Massey Algorithm (FPS/berlekampmassey.hpp)
• $f(\exp(x))$ (FPS/compexp.hpp)
• Compositional Inverse (FPS/compinv.hpp)
• Composition of Formal Power Series (FPS/composition.hpp)
• Factorial (Large) (FPS/factlarge.hpp)
• Factorize Polynomial (FPS/factorize.hpp)
• Famous Sequence (FPS/famous.hpp)
• Find roots (FPS/findroots.hpp)
• Formal Power Series (NTT-friendly mod) (FPS/fps.hpp)
• Half GCD (FPS/halfgcd.hpp)
• interpolate (one point) (FPS/interpolate.hpp)
• Mobius Transform (FPS/mobius.hpp)
• Multipoint Evaluation (FPS/multieval.hpp)
• Multipoint Evaluation on Geometric Sequence (FPS/multievalgeom.hpp)
• Bostan-Mori Algorithm (FPS/nthterm.hpp)
• P-recursive (FPS/p-recursive.hpp)
• Pow Enumerate (FPS/powenum.hpp)
• Prefix Sum of Polynomial (FPS/prefixsumofpoly.hpp)
• Enumerate $\sum_{k=0}^{N-1} k^i$ (FPS/prefixsumofpowers.hpp)
• $\Pi_{k=0}^{m-1} f(r^kx)$ (FPS/prodoffrkx.hpp)
• Product of Polynomials (FPS/prodofpolys.hpp)
• Shift of Sampling Points of Polynomial (FPS/samplepointshift.hpp)
• Sum of Rationals (FPS/sumofRationals.hpp)
• $\sum_{k} r^k\cdot poly(k)$ (FPS/sumofpolyexp.hpp)
• Enumerate $\sum_k a_k^i$ (FPS/sumofpowers.hpp)

Geometry

• Enclosing Circle (Geometry/Enclosing.hpp)
• Geometry(Fraction Coordinates) (Geometry/FracCoord.hpp)
• Geometry (Geometry/geometry.hpp)
• Geometry(integer Coordinates) (Geometry/intCoord.hpp)

Graph

• Auxiliary Tree(Virtual Tree) (Graph/auxiliarytree.hpp)
• Bipartite Matching (Graph/bimatching.hpp)
• Block Cut Tree (Graph/blockcut.hpp)
• Centroid Decomposition (Graph/centroid.hpp)
• Chromatic Number (Graph/chromatic.hpp)
• Contour Sum Query (Graph/contour.hpp)
• Cycle Detection (Graph/cycledetect.hpp)
• DM decomposition (Graph/dmdecomp.hpp)
• Enumerate Cliques (Graph/enumcliques.hpp)
• Eulerian Trail (Graph/euler.hpp)
• General Weighted Matching (Graph/generalweightedmatching.hpp)
• Heavy Light Decomposition (Graph/hld.hpp)
• Lowest Common Ancestor (Graph/lca.hpp)
• Link-Cut Tree (Graph/linkcut.hpp)
• Lowlink (Graph/lowlink.hpp)
• Maximum Flow (Graph/maxflow.hpp)
• Maximum Independent Set (Graph/maxindependentset.hpp)
• Minimum Cost b-flow (Graph/mincostflow.hpp)
• Rerooting (Graph/rerooting.hpp)
• Strongly Connected Components (Graph/scc.hpp)
• Steiner Tree (Graph/steiner.hpp)

Math

• Algebra Structure (Math/algebra.hpp)
• Black Box Linear Algebra (Math/bbla.hpp)
• Big Integer(Float) (Math/bigint.hpp)
• Binomial Coefficient for query (Math/binomquery.hpp)
• Characteristic Polynomial (Math/charpoly.hpp)
• Count Square-free integers (Math/countsquarefree.hpp)
• $\det(A+Bx)$ (Math/detaplusbx.hpp)
• Dirichlet series (Math/dirichlet.hpp)
• Dynamic Modint (Math/dynamic.hpp)
• Fast Division (Math/fastdiv.hpp)
• Floor Sum (Math/floorsum.hpp)
• Fraction (Math/fraction.hpp)
• Gaussian Integer (Math/gaussian.hpp)
• Hafnian of matrix (Math/hafnian.hpp)
• Kth Root(Integer) (Math/kthroot.hpp)
• Linear Equation (Math/linearequation.hpp)
• Matrix (Math/matrix.hpp)
• Miller-Rabin (Math/miller.hpp)
• Modint (Math/modint.hpp)
• Multiplicative Sum (Math/multiplicative.hpp)
• Nimber (Math/nimber.hpp)
• Pollard-Rho (Math/pollard.hpp)
• Enumrate $n^k$ (Math/powertable.hpp)
• Prime Sum (Math/primesum.hpp)
• Primitive Function (Math/primitive.hpp)
• Prime Sieve (Math/sieve.hpp)
• Stern-Brocot Tree (Math/sternbrocot.hpp)
• Stirling Number for query (Math/stirlingquery.hpp)
• 2-SAT (Math/twosat.hpp)

String

• Aho-Corasick (String/ahocorasick.hpp)
• Manacher Algorithm (String/manacher.hpp)
• Palindromic Tree (String/palindromictree.hpp)
• Prefix Substring LCS (String/prefixsubstrlcs.hpp)
• Rolling Hash (String/rollinghash.hpp)
• Suffix Array (String/suffixarray.hpp)
• Suffix Automaton (String/suffixautomaton.hpp)
• Trie (String/trie.hpp)
• Z-Algorithm (String/zalgo.hpp)

Template

• Template/template.hpp

Utility

• Fast IO (Utility/fastio.hpp)
• Random (Utility/random.hpp)

Verification Files

Verify

• Verify/AOJ_1595.test.cpp
• Verify/AOJ_DSL_1_B.test.cpp
• Verify/AOJ_DSL_2_D.test.cpp
• Verify/AOJ_GRL_6_A.test.cpp
• Verify/LC_area_of_union_of_rectangles.test.cpp
• Verify/LC_associative_array.test.cpp
• Verify/LC_bernoulli_number.test.cpp
• Verify/LC_biconnected_components.test.cpp
• Verify/LC_binomial_coefficient.test.cpp
• Verify/LC_bipartitematching.test.cpp
• Verify/LC_bitwise_and_convolution.test.cpp
• Verify/LC_bitwise_xor_convolution.test.cpp
• Verify/LC_cartesian_tree.test.cpp
• Verify/LC_chromatic_number.test.cpp
• Verify/LC_convolution_mod.test.cpp
• Verify/LC_convolution_mod_1000000007.test.cpp
• Verify/LC_convolution_mod_2.test.cpp
• Verify/LC_counting_primes.test.cpp
• Verify/LC_cycle_detection.test.cpp
• Verify/LC_cycle_detection_undirected.test.cpp
• Verify/LC_deque_operate_all_composite.test.cpp
• Verify/LC_discrete_logarithm_mod.test.cpp
• Verify/LC_dynamic_tree_vertex_add_path_sum.test.cpp
• Verify/LC_dynamic_tree_vertex_add_subtree_sum.test.cpp
• Verify/LC_dynamic_tree_vertex_set_path_composite.test.cpp
• Verify/LC_enumerate_cliques.test.cpp
• Verify/LC_enumerate_palindromes.test.cpp
• Verify/LC_enumerate_primes.test.cpp
• Verify/LC_exp_of_formal_power_series.test.cpp
• Verify/LC_factorize.test.cpp
• Verify/LC_find_linear_recurrence.test.cpp
• Verify/LC_frequency_table_of_tree_distance.test.cpp
• Verify/LC_gcd_convolution.test.cpp
• Verify/LC_general_weighted_matching.test.cpp
• Verify/LC_hafnian_of_matrix.test.cpp
• Verify/LC_inv_of_formal_power_series.test.cpp
• Verify/LC_kth_root_integer.test.cpp
• Verify/LC_kth_term_of_linearly_recurrent_sequence.test.cpp
• Verify/LC_lca.test.cpp
• Verify/LC_lca_2.test.cpp
• Verify/LC_lcm_convolution.test.cpp
• Verify/LC_line_add_get_min.test.cpp
• Verify/LC_log_of_formal_power_series.test.cpp
• Verify/LC_manhattanmst.test.cpp
• Verify/LC_many_aplusb.test.cpp
• Verify/LC_many_factorials.test.cpp
• Verify/LC_matrix_det.test.cpp
• Verify/LC_matrix_product.test.cpp
• Verify/LC_maximum_independent_set.test.cpp
• Verify/LC_min_cost_b_flow.test.cpp
• Verify/LC_multipoint_evaluation.test.cpp
• Verify/LC_multivariate_convolution.test.cpp
• Verify/LC_multivariate_convolution_cyclic.test.cpp
• Verify/LC_nim_product_64.test.cpp
• Verify/LC_number_of_substrings.test.cpp
• Verify/LC_partition_function.test.cpp
• Verify/LC_persistent_unionfind.test.cpp
• Verify/LC_point_add_range_sum.test.cpp
• Verify/LC_point_add_rectangle_sum.test.cpp
• Verify/LC_point_set_range_composite.test.cpp
• Verify/LC_point_set_range_sort_range_composite.test.cpp
• Verify/LC_polynomial_interpolation.test.cpp
• Verify/LC_polynomial_taylor_shift.test.cpp
• Verify/LC_pow_of_formal_power_series.test.cpp
• Verify/LC_predecessor_problem.test.cpp
• Verify/LC_prefix_substring_lcs.test.cpp
• Verify/LC_product_of_polynomial_sequence.test.cpp
• Verify/LC_queue_operate_all_composite.test.cpp
• Verify/LC_range_affine_range_sum.test.cpp
• Verify/LC_range_chmin_chmax_add_range_sum.test.cpp
• Verify/LC_range_kth_smallest-2.test.cpp
• Verify/LC_range_kth_smallest.test.cpp
• Verify/LC_rectangle_sum.test.cpp
• Verify/LC_scc.test.cpp
• Verify/LC_segment_add_get_min.test.cpp
• Verify/LC_shift_of_sampling_points_of_polynomial.test.cpp
• Verify/LC_sparse_matrix_det.test.cpp
• Verify/LC_static_range_frequency.test.cpp
• Verify/LC_static_range_inversions_query.test.cpp
• Verify/LC_static_range_lis_query.test.cpp
• Verify/LC_static_range_sum.test.cpp
• Verify/LC_static_rectangle_add_rectangle_sum.test.cpp
• Verify/LC_staticrmq-2.test.cpp
• Verify/LC_staticrmq.test.cpp
• Verify/LC_stirling_number_of_the_first_kind.test.cpp
• Verify/LC_stirling_number_of_the_first_kind_small_p_large_n.test.cpp
• Verify/LC_stirling_number_of_the_second_kind.test.cpp
• Verify/LC_stirling_number_of_the_second_kind_small_p_large_n.test.cpp
• Verify/LC_subset_convolution.test.cpp
• Verify/LC_suffixarray.test.cpp
• Verify/LC_sum_of_exponential_times_polynomial.test.cpp
• Verify/LC_sum_of_exponential_times_polynomial_limit.test.cpp
• Verify/LC_sum_of_floor_of_linear.test.cpp
• Verify/LC_sum_of_totient_function.test.cpp
• Verify/LC_system_of_linear_equations.test.cpp
• Verify/LC_two_edge_connected_components.test.cpp
• Verify/LC_two_sat.test.cpp
• Verify/LC_unionfind.test.cpp
• Verify/LC_vertex_add_path_sum.test.cpp
• Verify/LC_vertex_add_range_contour_sum_on_tree.test.cpp
• Verify/LC_vertex_set_path_composite.test.cpp
• Verify/LC_zalgorithm.test.cpp
• Verify/YUKI_1080.test.cpp
• Verify/YUKI_1112.test.cpp
• Verify/YUKI_1781.test.cpp
• Verify/YUKI_2097.test.cpp
• Verify/YUKI_310.test.cpp
• Verify/YUKI_901.test.cpp