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_convolution.hpp)
• Convolution (convolution/convolution.hpp)
• Convolution 2D (convolution/convolution_2d.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/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)
• Area of Union of Rectangles (data_structure/area_of_union_of_rectangles.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)
• DSU (data_structure/dsu.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)
• Range Parallel DSU (data_structure/range_parallel_dsu.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 with potential (data_structure/unionfind_with_potential.hpp)

fps

• Formal Power Series (Arbitrary mod) (fps/arbitrary_mod_fps.hpp)
• Berlekamp Massey (fps/berlekamp_massey.hpp)
• $f(g(x))$ ( $O(N\log^2{N})$ ) (fps/composition_of_fps.hpp)
• $f(g(x))$ ( $O(N^2)$ ) (fps/composition_of_fps_old.hpp)
• $f(x)$ の逆関数 ( $O(N\log^2{N})$ ) (fps/compositional_inverse_of_fps.hpp)
• $f(x)$ の逆関数 ( $O(N^2)$ ) (fps/compositional_inverse_of_fps_old.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)
• $f^k \mod g$ (fps/middle_product_arbitrary.hpp)
• Multipoint Evaluation (fps/multipoint_evaluation.hpp)
• Formal Power Series (NTT Friendly) (fps/ntt_friendly_fps.hpp)
• fps/poly_mod_pow.hpp
• Polynomial Interpolation (fps/polynomial_interpolation.hpp)
• $\sum_{j}^{n-1} w_j [x^j] f(x)^i$ の $i = 0,1,\dots,M$ の列挙 (fps/power_projection_of_fps.hpp)
• $\prod 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)
• Shift of Sampling Points of Polynomial (fps/shift_of_sampling_points_of_poly.hpp)
• $\sum \frac{f_i}{g_i}$ (fps/sum_of_rational_fps.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)
• Count Directed Euler Trail (graph/count_directed_euler_trail.hpp)
• Count Spanning Tree (graph/count_spanning_tree.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)
• Maximum Matching Size (graph/maximum_matching_size.hpp)
• Minimum Steiner Tree (graph/minimum_steiner_tree.hpp)
• Minimum Spanning Tree (graph/mst.hpp)
• graph/scc_graph.hpp
• Two Edge Connected Components (graph/two_edge_connected_components.hpp)
• 便利関数 (graph/utility.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)
• 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)
• $\sum_{i = 0}^{n-1} a^i f(i)$ (math/sum_of_exp_times_poly.hpp)
• $\sum_{i = 0}^{n-1} i^k$ (math/sum_of_powers_iota.hpp)
• $\sum_n A_n^i$ の $i = 0, 1,\dots, k$ の列挙 (math/sums_of_powers.hpp)
• $\sum_{i = 0}^{n-1} i^k$ の $k$ に関する列挙 (math/sums_of_powers_iota.hpp)

matrix

• matrix/base.hpp
• Black Box Linear Algebra (matrix/black_box_linear_algebra.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
• Wildcard Pattern Matching (string/wildcard_pattern_matching.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)
• DP on Static Top Tree (tree/dp_on_static_top_tree.hpp)
• Dsu on Tree (tree/dsu_on_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)
• Static Top Tree (tree/static_top_tree.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_2995.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_2D.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/Online_Convolution.test.cpp
• test/convolution/Subset_Convolution.test.cpp

test/data_structure

• test/data_structure/Area_of_Union_of_Rectangles.test.cpp
• 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/Range_Parallel_DSU_Stress_test.test.cpp
• test/data_structure/Range_Parallel_Unionfind.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/Counting_Eulerian_Circuits.test.cpp
• test/graph/Counting_Spanning_Trees_Directed.test.cpp
• test/graph/Counting_Spanning_Trees_Undirected.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/Find_Linear_Recurrence.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/Negative_Binomial_Coefficient.test.cpp
• test/math/Partition_Function_FPS.test.cpp
• test/math/Partition_Function_Pentagonal.test.cpp
• test/math/Pow.test.cpp
• test/math/Sharp_P_Subset_Sum.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_Exponential_Times_Polynomial.test.cpp
• test/math/Sum_of_Exponential_Times_Polynomial_Limit.test.cpp
• test/math/Sum_of_Powers_Iota.test.cpp
• test/math/Sum_of_Totient_Function.test.cpp
• test/math/eratosthenes_sieve.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/Determinant_of_Sparse_Matrix.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/Composition_of_Formal_Power_Series_Large.test.cpp
• test/polynomial/Compositional_Inverse_of_Formal_Power_Series.test.cpp
• test/polynomial/Compositional_Inverse_of_Formal_Power_Series_Large.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/Shift_of_Sampling_Points_of_Polynomial.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/Wildcard_Pattern_Matching.test.cpp
• 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/Point_Set_Tree_Path_Composition_Sum_Fixed_Root.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_Add_Subtree_Sum_Dsu_on_Tree.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_1112.test.cpp
• test/yuki/yuki_1145.test.cpp
• test/yuki/yuki_1302.test.cpp
• test/yuki/yuki_1796.test.cpp
• test/yuki/yuki_1857.test.cpp
• test/yuki/yuki_2439.test.cpp
• test/yuki/yuki_2633.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