Library

このライブラリは競技プログラミングで使用することを目的として作成されています。

g++/c++20 で動作することが確認されています。

バグや誤り、改善案がある場合は issue にお願いします。

Library Files

Dice

• Dice (Dice/Dice.hpp)

algorithm

• Convex Hull Trick (algorithm/convex_hull_trick.hpp)
• Enumerate Monge d-edge shortest path (algorithm/enumerate_monge_d_edge_shortest_path.hpp)
• Golden section search (algorithm/golden_section_search.hpp)
• algorithm/mo_algorithm.hpp
• Monge d-edge shortest path (algorithm/monge_d_edge_shortest_path.hpp)
• Monge shortest path (algorithm/monge_shortest_path.hpp)
• Monotone Minima (algorithm/monotone_minima.hpp)
• algorithm/submodular.hpp
• algorithm/two_sat.hpp

convolution

• Bitwise AND Convolution (convolution/and_convolution.hpp)
• Arbitrary Convolution (convolution/arbitrary_ntt.hpp)
• Convolution $\pmod{2^{64}}$ (convolution/convolution_mod_2_64.hpp)
• Dirichlet Convolution (convolution/dirichlet_convolution.hpp)
• GCD Convolution (convolution/gcd_convolution.hpp)
• LCM Convolution (convolution/lcm_convolution.hpp)
• Min Plus Convolution (convolution/min_plus_convolution.hpp)
• NTT Convolution (convolution/ntt.hpp)
• Online Convolution (convolution/online_convolution.hpp)
• Bitwise OR Convolution (convolution/or_convolution.hpp)
• Subset Convolution (convolution/subset_convolution.hpp)
• Bitwise XOR Convolution (convolution/xor_convolution.hpp)

data_structure

• data_structure/DynamicSegmentTree.hpp
• data_structure/ImplicitTreap.hpp
• data_structure/PersistentSegmentTree.hpp
• data_structure/SegmentTreeBeats.hpp
• data_structure/Stream.hpp
• data_structure/Suspension.hpp
• Wavelet Matrix (data_structure/WaveletMatrix.hpp)
• data_structure/bankers_queue.hpp
• data_structure/binary_trie.hpp
• data_structure/bitVector.hpp
• Compress (data_structure/compress.hpp)
• Sliding Window Aggregation (Deque) (data_structure/deque_aggregation.hpp)
• Double-Ended Priority Queue (data_structure/double_ended_priority_queue.hpp)
• dual segtree (data_structure/dual_segtree.hpp)
• dual segtree (commutative) (data_structure/dual_segtree_commutative.hpp)
• dynamic dual segtree (data_structure/dynamic_dual_segtree.hpp)
• fenwick tree (data_structure/fenwick_tree.hpp)
• fibonacci heap (data_structure/fibonacci_heap.hpp)
• data_structure/kd_tree.hpp
• lazy segtree (data_structure/lazy_segtree.hpp)
• Li Chao Tree (data_structure/li_chao_tree.hpp)
• data_structure/link_cut_tree.hpp
• offline 2D dual segtree (data_structure/offline_dual_segtree_2d.hpp)
• Offline Dynamic Connectivity (data_structure/offline_dynamic_connectivity.hpp)
• offline 2D segtree (data_structure/offline_segtree_2d.hpp)
• online mex (data_structure/online_mex.hpp)
• partially persistent unionfind (data_structure/partially_persistent_unionfind.hpp)
• data_structure/persistent_array.hpp
• data_structure/persistent_unionfind.hpp
• data_structure/predecessor_set.hpp
• Sliding Window Aggregation (Queue) (data_structure/queue_aggregation.hpp)
• data_structure/range_query_binary_trie.hpp
• data_structure/range_tree.hpp
• Removable Priority Queue (data_structure/removable_priority_queue.hpp)
• section set (data_structure/section_set.hpp)
• segtree (data_structure/segtree.hpp)
• 2D segtree (data_structure/segtree_2d.hpp)
• Simple CSR (data_structure/simple_csr.hpp)
• data_structure/skew_heap.hpp
• Slope Trick (data_structure/slope_trick.hpp)
• Sparse Table (data_structure/sparse_table.hpp)
• 2D sparse table (data_structure/sparse_table_2d.hpp)
• data_structure/splay_tree.hpp
• Static Rectangle Sum (data_structure/static_rectangle_sum.hpp)
• Undo UnionFind (data_structure/undo_unionfind.hpp)
• UnionFind (data_structure/unionfind.hpp)
• UnionFind with potential (data_structure/unionfind_with_potential.hpp)

fps

• $f(g(x))$ (fps/composition_of_fps.hpp)
• $f(x)$ の逆関数 (fps/compositional_inverse_of_fps.hpp)
• Formal Power Series (fps/fps.hpp)
• Formal Power Series (Sparse) (fps/fps_sparse.hpp)
• $\sqrt{f}$ (fps/fps_sqrt.hpp)
• $[x^i]c = \sum_{j} [x^{i+j}]a [x^j]b$ (fps/middle_product.hpp)
• Multipoint Evaluation (fps/multipoint_evaluation.hpp)
• Polynomial Interpolation (fps/polynomial_interpolation.hpp)
• $\prod_{i=0}^n f_i$ (fps/product_of_fps.hpp)
• $\prod (1 - x^{a_i}) \mod x^d$ (fps/product_of_one_minus_xn.hpp)
• $\prod (1 + x^{a_i}) \mod x^d$ (fps/product_of_one_plus_xn.hpp)
• $\sum_i (\sum_n A_n^i) x^i$ (fps/sums_of_powers.hpp)
• $f(x + c)$ (fps/taylor_shift.hpp)

geometry

• geometry/circle.hpp
• geometry/convex_hull.hpp
• geometry/line.hpp
• geometry/line_segment.hpp
• point (geometry/point.hpp)
• geometry/polygon.hpp

graph

• Graph (CSR format) (graph/base.hpp)
• Bellman-Ford (graph/bellman_ford.hpp)
• graph/biconnected_components.hpp
• Chromatic Number (彩色数) (graph/chromatic_number.hpp)
• Complement Graph BFS (graph/complement_graph_bfs.hpp)
• Cycle Detection (graph/cycle_detection.hpp)
• dijkstra (graph/dijkstra.hpp)
• graph/dijkstra_fibheap.hpp
• Directed MST (graph/directed_mst.hpp)
• Euler Trail (graph/euler_trail.hpp)
• Low Link (graph/low_link.hpp)
• Manhattan MST (graph/manhattan_mst.hpp)
• Maximum Independent Set (graph/maximum_independent_set.hpp)
• Minimum Spanning Tree (graph/mst.hpp)
• graph/scc_graph.hpp
• Two Edge Connected Components (graph/two_edge_connected_components.hpp)

math

• Dirichlet Series (math/DirichletSeries.hpp)
• Bernoulli Number (math/bernoulli_number.hpp)
• Binomial Coefficient (math/binomial.hpp)
• Bostan-Mori Algorithm (math/bostan_mori_algorithm.hpp)
• Catalan's Convolution Formula (math/catalan_convolution.hpp)
• Catalan Number (math/catalan_number.hpp)
• Divisor Transform (Zeta / Möbius) (math/divisor_transform.hpp)
• Eratosthenes Sieve (math/eratosthenes_sieve.hpp)
• math/factorial_mod_998.hpp
• math/internal_math.hpp
• Inversion Number (math/inversion_number.hpp)
• Lagrange Interpolation (math/lagrange_interpolation.hpp)
• Linear Sieve (math/linear_sieve.hpp)
• LIS (math/longest_increasing_subsequence.hpp)
• Mod Inv (math/mod_inv.hpp)
• Mod Sqrt (math/mod_sqrt.hpp)
• Multiple Transform (Zeta / Möbius) (math/multiple_transform.hpp)
• Partition Function (math/partition_function.hpp)
• Stern-Brocot Tree (math/stern_brocot_tree.hpp)
• Stirling Numbers of the First Kind (math/stirling_number_1st.hpp)
• Stirling Numbers of the Second Kind (math/stirling_number_2nd.hpp)

matrix

• matrix/base.hpp
• matrix/det_arbitrary_mod.hpp
• matrix/gauss_jordan.hpp
• matrix/square_matrix.hpp

modint

• modint/base.hpp
• modint/dynamic_modint.hpp
• modint/modint.hpp
• modint/modint61.hpp
• modint/montgomery_modint.hpp

set_function

• $f(a)$ (Set Power Series, f is EGF) (set_function/egf_composite_sps.hpp)
• $\exp {a}$ (Set Power Series) (set_function/exp_of_sps.hpp)
• Hadamard Transform (set_function/hadamard_transform.hpp)
• $f(a)$ (Set Power Series, f is FPS) (set_function/poly_composite_sps.hpp)
• Ranked Subset Transform (Zeta / Mobius) (set_function/ranked_subset_transform.hpp)
• Subset Transform (Zeta / Möbius) (set_function/subset_transform.hpp)
• Superset Transform (Zeta / Möbius) (set_function/superset_transform.hpp)

string

• string/Z_Algorithm.hpp
• string/aho_corasick.hpp
• string/palindromic_tree.hpp
• string/parsing.hpp
• Rolling Hash (string/rolling_hash.hpp)
• string/trie.hpp

template

• template/debug_template.hpp
• template/int_alias.hpp
• template/io.hpp
• template/template.hpp
• template/utility.hpp

tree

• Block Cut Tree (tree/block_cut_tree.hpp)
• Cartesian Tree (tree/cartesian_tree.hpp)
• Centroid Decomposition (tree/centroid_decomposition.hpp)
• Contour Query on Tree (tree/contour_query_on_tree.hpp)
• Contour Query on Tree (Weighted) (tree/contour_query_on_weighted_tree.hpp)
• Heavy Light Decomposition (tree/heavy_light_decomposition.hpp)
• LCA based Auxiliary Tree (tree/lca_based_auxiliary_tree.hpp)
• Level Ancestor (tree/level_ancestor.hpp)
• Lowest Common Ancestor (tree/lowest_common_ancestor.hpp)
• Rerooting DP (tree/rerooting.hpp)
• Rooted Tree Hash (tree/rooted_tree_hash.hpp)
• Tree Diameter (tree/tree_diameter.hpp)

utility

• Hash structure (utility/hash.hpp)
• Random Number Generator (utility/random_number_generator.hpp)

Verification Files

test/Dice

• test/Dice/dice1.test.cpp
• test/Dice/dice2.test.cpp
• test/Dice/dice3.test.cpp
• test/Dice/dice4.test.cpp

test/algorithm

• test/algorithm/Two_Sat.test.cpp

test/aoj

• test/aoj/aoj_1068_1.test.cpp
• test/aoj/aoj_1068_2.test.cpp
• test/aoj/aoj_1645.test.cpp
• test/aoj/aoj_2152.test.cpp
• test/aoj/aoj_2235.test.cpp
• test/aoj/aoj_2444.test.cpp
• test/aoj/aoj_2450.test.cpp
• test/aoj/aoj_2863.test.cpp
• test/aoj/aoj_2873.test.cpp
• test/aoj/aoj_3086.test.cpp
• test/aoj/aoj_3361.test.cpp
• test/aoj/aoj_grl_1_a.test.cpp
• test/aoj/aoj_grl_1_b.test.cpp

test/convolution

• test/convolution/Bitwise_And_Convolution.test.cpp
• test/convolution/Bitwise_OR_Convolution.test.cpp
• test/convolution/Bitwise_Xor_Convolution.test.cpp
• test/convolution/Convolution.test.cpp
• test/convolution/Convolution_Mod_1000000007.test.cpp
• test/convolution/Convolution_Mod_2_64.test.cpp
• test/convolution/Gcd_Convolution.test.cpp
• test/convolution/Lcm_Convolution.test.cpp
• test/convolution/Min_Plus_Convolution_Convex_and_Arbitary.test.cpp
• test/convolution/Subset_Convolution.test.cpp

test/data_structure

• test/data_structure/Deque_Operate_All_Composite.test.cpp
• test/data_structure/Double-Ended_Priority_Queue.test.cpp
• test/data_structure/Dynamic_Sequence_Range_Affine_Range_Sum.test.cpp
• test/data_structure/Dynamic_Tree_Vertex_Add_Path_Sum.test.cpp
• test/data_structure/Line_Add_Get_Min.test.cpp
• test/data_structure/Persistent_Queue.test.cpp
• test/data_structure/Persistent_Unionfind.test.cpp
• test/data_structure/Point_Add_Range_Sum_BIT.test.cpp
• test/data_structure/Point_Add_Range_Sum_Persistent_Segtree.test.cpp
• test/data_structure/Point_Add_Range_Sum_Segtree.test.cpp
• test/data_structure/Point_Add_Rectangle_Sum.test.cpp
• test/data_structure/Point_Set_Range_Composite.test.cpp
• test/data_structure/Predecessor_Problem.test.cpp
• test/data_structure/Queue_Operate_All_Composite.test.cpp
• test/data_structure/Range_Add_Query.test.cpp
• test/data_structure/Range_Affine_Point_Get.test.cpp
• test/data_structure/Range_Affine_Point_Get_Dynamic_Segtree.test.cpp
• test/data_structure/Range_Affine_Range_Sum.test.cpp
• test/data_structure/Range_Chmin_Chmax_Add_Range_Sum.test.cpp
• test/data_structure/Range_Kth_Smallest.test.cpp
• test/data_structure/Rectangle_Add_Point_Get.test.cpp
• test/data_structure/Rectangle_Sum_Range_Tree.test.cpp
• test/data_structure/Rectangle_Sum_Segtree.test.cpp
• test/data_structure/Segment_Add_Get_Min.test.cpp
• test/data_structure/Set_Xor_Min.test.cpp
• test/data_structure/Static_Range_Frequency.test.cpp
• test/data_structure/Static_Range_Inversion_Query.test.cpp
• test/data_structure/Static_Rectangle_Sum.test.cpp
• test/data_structure/Static_Rmq.test.cpp
• test/data_structure/Union_Find.test.cpp
• test/data_structure/Vertex_Add_Path_Sum.test.cpp
• test/data_structure/Vertex_Add_Subtree_Sum.test.cpp
• test/data_structure/Vertex_Set_Path_Compositie.test.cpp

test/geometry

• test/geometry/area.test.cpp
• test/geometry/circumscribed_circle_of_triangle.test.cpp
• test/geometry/closest_pair.test.cpp
• test/geometry/common_area.test.cpp
• test/geometry/common_area_circles.test.cpp
• test/geometry/common_tangent.test.cpp
• test/geometry/contains.test.cpp
• test/geometry/convex_diameter.test.cpp
• test/geometry/convex_hull.test.cpp
• test/geometry/convex_polygon_cut.test.cpp
• test/geometry/cross_point.test.cpp
• test/geometry/cross_points_of_circle_and_line.test.cpp
• test/geometry/cross_points_of_circles.test.cpp
• test/geometry/distance.test.cpp
• test/geometry/incircle_of_triangle.test.cpp
• test/geometry/intersection.test.cpp
• test/geometry/intersection_circle.test.cpp
• test/geometry/intersection_line_segment.test.cpp
• test/geometry/is_convex.test.cpp
• test/geometry/isp.test.cpp
• test/geometry/reflection.test.cpp
• test/geometry/segment_intersection.test.cpp
• test/geometry/tangent_to_circle.test.cpp

test/graph

• test/graph/Articulation_Points.test.cpp
• test/graph/Biconnected_Components.test.cpp
• test/graph/Chromatic_Number.test.cpp
• test/graph/Cycle_Detection_Directed.test.cpp
• test/graph/Cycle_Detection_Undirected.test.cpp
• test/graph/Directed_MST.test.cpp
• test/graph/Eulerian_Trail_Directed.test.cpp
• test/graph/Eulerian_Trail_Undirected.test.cpp
• test/graph/Manhattan_MST.test.cpp
• test/graph/Maximum_Independent_Set.test.cpp
• test/graph/Minimum_Spanning_Tree.test.cpp
• test/graph/Shortest_Path.test.cpp
• test/graph/Two_Edge_Connected_Components.test.cpp
• test/graph/dijkstra.test.cpp
• test/graph/fibonacci_heap.test.cpp
• test/graph/scc_graph.test.cpp

test/math

• test/math/Berunoulli_Number.test.cpp
• test/math/Binomial_Coefficient_Prime_Mod.test.cpp
• test/math/Catalan_Convolution.test.cpp
• test/math/Enumerate_Primes.test.cpp
• test/math/Factorial.test.cpp
• test/math/Inversion_Number.test.cpp
• test/math/Kth_term_of_Linearly_Recurrent_Sequence.test.cpp
• test/math/Longest_Increasing_Subsequence.test.cpp
• test/math/Partition_Function_FPS.test.cpp
• test/math/Partition_Function_Pentagonal.test.cpp
• test/math/Pow.test.cpp
• test/math/Sqrt_Mod.test.cpp
• test/math/Stern-Brocot_Tree.test.cpp
• test/math/Stirling_Number_of_the_First_Kind.test.cpp
• test/math/Stirling_Number_of_the_Second_Kind.test.cpp
• test/math/Sum_of_Totient_Function.test.cpp
• test/math/eratosthenes_sieve.test.cpp
• test/math/sharp_p_subset_sum.test.cpp

test/matrix

• test/matrix/Determinant_of_Matrix.test.cpp
• test/matrix/Determinant_of_Matrix_2.test.cpp
• test/matrix/Determinant_of_Matrix_Arbitrary_Mod.test.cpp
• test/matrix/Inverse_Matrix.test.cpp
• test/matrix/Matrix_Product.test.cpp
• test/matrix/Pow_of_Matrix.test.cpp
• test/matrix/Rank_of_Matrix.test.cpp
• test/matrix/System_of_Linear_Equations.test.cpp

test/polynomial

• test/polynomial/Composition_of_Formal_Power_Series.test.cpp
• test/polynomial/Compositional_Inverse_of_Formal_Power_Series.test.cpp
• test/polynomial/Division_of_Polynomials.test.cpp
• test/polynomial/Exp_of_Formal_Power_Series.test.cpp
• test/polynomial/Exp_of_Formal_Power_Series_Sparse.test.cpp
• test/polynomial/Inv_of_Formal_Power_Series.test.cpp
• test/polynomial/Inv_of_Formal_Power_Series_Sparse.test.cpp
• test/polynomial/Log_of_Formal_Power_Series.test.cpp
• test/polynomial/Log_of_Formal_Power_Series_Sparse.test.cpp
• test/polynomial/Multipoint_Evaluation.test.cpp
• test/polynomial/Polynomial_Interpolation.test.cpp
• test/polynomial/Polynomial_Taylor_Shift.test.cpp
• test/polynomial/Pow_of_Formal_Power_Series.test.cpp
• test/polynomial/Pow_of_Formal_Power_Series_Sparse.test.cpp
• test/polynomial/Product_of_Polynomial_Sequence.test.cpp
• test/polynomial/Sqrt_of_Formal_Power_Series.test.cpp
• test/polynomial/Sqrt_of_Formal_Power_Series_Sparse.test.cpp

test/set_function

• test/set_function/Exp_of_Set_Power_Series.test.cpp
• test/set_function/Polynomial_Composite_Set_Power_Series.test.cpp

test/string

• test/string/Z_Algorithm.test.cpp

test/tree

• test/tree/Cartesian_Tree.test.cpp
• test/tree/Frequency_Table_of_Tree_Distance_MODE_0.test.cpp
• test/tree/Frequency_Table_of_Tree_Distance_MODE_1.test.cpp
• test/tree/Frequency_Table_of_Tree_Distance_MODE_2.test.cpp
• test/tree/Jump_on_Tree.test.cpp
• test/tree/Jump_on_Tree_HLD.test.cpp
• test/tree/Rooted_Tree_Isomorphism_Classification.test.cpp
• test/tree/Tree_Diameter.test.cpp
• test/tree/Tree_Path_Composite_Sum.test.cpp
• test/tree/Vertex_Add_Range_Contour_Sum_on_Tree.test.cpp
• test/tree/Vertex_Add_Range_Contour_Sum_on_Tree_2.test.cpp
• test/tree/Vertex_Get_Range_Contour_Add_on_Tree.test.cpp
• test/tree/level_ancestor_lca.test.cpp
• test/tree/lowest_common_ancestor.test.cpp

test/yuki

• test/yuki/yuki_1038.test.cpp
• test/yuki/yuki_1077.test.cpp
• test/yuki/yuki_1145.test.cpp
• test/yuki/yuki_1302.test.cpp
• test/yuki/yuki_1796.test.cpp
• test/yuki/yuki_2439.test.cpp
• test/yuki/yuki_2747.test.cpp
• test/yuki/yuki_409.test.cpp
• test/yuki/yuki_901.test.cpp
• test/yuki/yuki_901_2.test.cpp
• test/yuki/yuki_952.test.cpp