kyopro_library

競技プログラミング用のライブラリです。

明らかに整備されていないものはバグっている可能性が高いです。

各アルゴリズムの概要はメモも兼ねています。

Library Files

lib/convolution

• Bitwise AND Convolution (lib/convolution/bitwise_and_convolution.hpp)
• Bitwise OR Convolution (lib/convolution/bitwise_or_convolution.hpp)
• Bitwise XOR Convolution (lib/convolution/bitwise_xor_convolution.hpp)
• Divisor Zeta/Mobius Transform (lib/convolution/divisor_zeta_mobius_transform.hpp)
• Fast Walsh-Hadamard Transform (lib/convolution/fast_walsh_hadamard_transform.hpp)
• GCD Convolution (lib/convolution/gcd_convolution.hpp)
• Karatsuba Algorithm (lib/convolution/karatsuba_algorithm.hpp)
• LCM Convolution (lib/convolution/lcm_convolution.hpp)
• Number Theoretic Transform (lib/convolution/ntt.hpp)
• Set Zeta/Mobius Transform (lib/convolution/set_zeta_mobius_transform.hpp)
• lib/convolution/subset_convolution.hpp

lib/data_structure

• Binary Indexed Tree (lib/data_structure/binary_indexed_tree.hpp)
• Binary Indexed Tree 2D (lib/data_structure/binary_indexed_tree_2d.hpp)
• lib/data_structure/binary_trie.hpp
• Convex Hull Trick (lib/data_structure/convex_hull_trick.hpp)
• Cumulative Sum 2D (二次元累積和) (lib/data_structure/cumulative_sum_2d.hpp)
• DESWAG (lib/data_structure/deswag.hpp)
• Disjoint Sparse Table (lib/data_structure/disjoint_sparse_table.hpp)
• Double Ended Priority Queue (lib/data_structure/double_ended_priority_queue.hpp)
• lib/data_structure/dynamic_binary_indexed_tree.hpp
• lib/data_structure/dynamic_binary_indexed_tree_2d.hpp
• Dynamic Li Chao Tree (lib/data_structure/dynamic_li_chao_tree.hpp)
• Dynamic Segment Tree (lib/data_structure/dynamic_segment_tree.hpp)
• lib/data_structure/dynamic_union_find.hpp
• lib/data_structure/dynamic_weighted_union_find.hpp
• lib/data_structure/fast_deque.hpp
• Grid Union-Find (lib/data_structure/grid_unionfind.hpp)
• Imos Linear (静的な一次関数の加算) (lib/data_structure/imos_linear.hpp)
• k-d Tree (lib/data_structure/kd_tree.hpp)
• lib/data_structure/lazy_segment_tree.hpp
• lib/data_structure/mergeable_set.hpp
• lib/data_structure/mo.hpp
• Partly Persistent Union-Find (lib/data_structure/partly_persistent_union_find.hpp)
• Persistent Array (永続配列) (lib/data_structure/persistent_array.hpp)
• Persistent Queue (永続キュー) (lib/data_structure/persistent_queue.hpp)
• Persistent Stack (永続スタック) (lib/data_structure/persistent_stack.hpp)
• Persistent Union Find (永続 UnionFind) (lib/data_structure/persistent_union_find.hpp)
• Eraseable Priority Queue (削除可能優先度付きキュー) (lib/data_structure/priority_queue.hpp)
• Radix Heap (lib/data_structure/radix_heap.hpp)
• Range Parallel Union-Find (lib/data_structure/range_parallel_union_find.hpp)
• lib/data_structure/range_tree.hpp
• Segment Tree (lib/data_structure/segment_tree.hpp)
• lib/data_structure/segment_tree_beats.hpp
• lib/data_structure/segment_tree_func.hpp
• lib/data_structure/segment_tree_indexed.hpp
• lib/data_structure/slope_trick.hpp
• Sparse Table (lib/data_structure/sparse_table.hpp)
• lib/data_structure/square_division.hpp
• Static Ordered Set (lib/data_structure/static_ordered_set.hpp)
• SWAG (lib/data_structure/swag.hpp)
• Union-Find (lib/data_structure/union_find.hpp)
• Weighted Union-Find (lib/data_structure/weighted_union_find.hpp)

lib/dp

• Longest Common Subsequence (lib/dp/LCS.hpp)
• Longest Increasing Subsequence (lib/dp/LIS.hpp)
• Count Substrings (lib/dp/substring.hpp)

lib/enumerative_combinatorics

• Combination (二項係数) (lib/enumerative_combinatorics/combination_modint.hpp)
• Factorial (階乗) (lib/enumerative_combinatorics/factorial.hpp)
• Montmort Number (モンモール数) (lib/enumerative_combinatorics/montmort_number.hpp)
• Partition Function (分割数) (lib/enumerative_combinatorics/partition_function.hpp)
• Stirling Number of the Second Kind (第 2 種スターリング数) (lib/enumerative_combinatorics/stirling_number_2nd.hpp)
• Subset Sum (lib/enumerative_combinatorics/subset_sum.hpp)

lib/geometry

• Geometry (幾何ライブラリ) (lib/geometry/geometry.hpp)

lib/graph

• T-join Problem (lib/graph/T_join.hpp)
• Assignment Problem (割当て問題) (lib/graph/assignment_problem.hpp)
• Auxiliary Tree (lib/graph/auxiliary_tree.hpp)
• Bellman-Ford Algorithm (ベルマン-フォード法) (lib/graph/bellman_ford.hpp)
• Biconnected Components (二重頂点連結成分分解) (lib/graph/biconnected_components.hpp)
• lib/graph/bipartite_matching.hpp
• Cartesian Tree (デカルト木) (lib/graph/cartesian_tree.hpp)
• Chromatic Number (彩色数) (lib/graph/chromatic_number.hpp)
• Connected Components of Complement Graph (補グラフの連結成分分解) (lib/graph/connected_components_of_complement_graph.hpp)
• Counting Spanning Tree (全域木の数え上げ) (lib/graph/counting_spanning_tree.hpp)
• Dijkstra's Algorithm (ダイクストラ法) (lib/graph/dijkstra.hpp)
• Dinic's Algorithm (lib/graph/dinic.hpp)
• Enumerate Cliques (クリークの列挙) (lib/graph/enumerate_cliques.hpp)
• Enumerate Triangles (lib/graph/enumerate_triangles.hpp)
• Eulerian Trail (オイラー小道) (lib/graph/eulerian_trail.hpp)
• Grid BFS (二次元グリッド上の幅優先探索) (lib/graph/grid-bfs.cpp)
• Heavy Light Decomposition (重軽分解) (lib/graph/heavy_light_decomposition.hpp)
• Interval Graph (区間グラフ) (lib/graph/interval_graph.hpp)
• Low Link (lib/graph/lowlink.hpp)
• Manhattan MST (lib/graph/manhattanMST.hpp)
• Maximum Independent Set (最大独立集合) (lib/graph/maximum_independent_set.hpp)
• Minimum Diameter Spanning Tree (最小直径全域木) (lib/graph/minimum_diameter_spanning_tree.hpp)
• Primal-Dual Algorithm (lib/graph/primal_dual.hpp)
• lib/graph/reachable_query.hpp
• Rerooting (全方位木DP) (lib/graph/rerooting.hpp)
• lib/graph/rooted_tree_topological_order_with_minimum_inversions.hpp
• Strongly Connected Component (強連結成分分解) (lib/graph/scc.hpp)
• Steiner Tree (シュタイナー木) (lib/graph/steiner_tree.hpp)
• Topological Sort (lib/graph/topological_sort.hpp)
• Tree Diameter (木の直径) (lib/graph/tree_diameter.hpp)
• Two Edge Connected Components (二重辺連結成分分解) (lib/graph/two_edge_connected_components.hpp)
• 2-SAT (lib/graph/two_sat.hpp)
• Floyd-Warshall Algorithm (ワーシャルフロイド法) (lib/graph/warshall_floyd.hpp)

lib/math

• Arbitrary Modint (lib/math/arbitrary_modint.hpp)
• Baby-step giant-step (lib/math/baby-step_giant-step.hpp)
• Bell Number (ベル数) (lib/math/bell_number.hpp)
• Bernoulli Number (ベルヌーイ数) (lib/math/bernoulli_number.hpp)
• BigInt (多倍長整数) (lib/math/bigint.hpp)
• Binary Basis (lib/math/binarybasis.hpp)
• Combination (二項係数) (lib/math/combination.hpp)
• Convert Base (進数変換) (lib/math/convert_base.hpp)
• Chinese Remainder Theorem (中国剰余定理) (lib/math/crt.hpp)
• Enumerate Quotients (商列挙) (lib/math/enumerate_quotients.hpp)
• Fraction (lib/math/fraction.hpp)
• lib/math/kth_root_integer.hpp
• Math Table (lib/math/math_table.hpp)
• Matrix (lib/math/matrix.hpp)
• Mod Calculation (lib/math/modcalc.hpp)
• ModInt (lib/math/modint.hpp)
• lib/math/pow_sum.hpp
• Smallest Prime Factor (lib/math/prime-factor.hpp)
• 素数判定、約数列挙 (lib/math/prime.hpp)
• Prime Sieve (エラトステネスの篩) (lib/math/prime_sieve.hpp)
• Primitive Root (原子根) (lib/math/primitive_root.hpp)
• Rational Approximation (有理数近似) (lib/math/rational_approximation.hpp)
• Pollard's Rho (lib/math/rho.hpp)
• lib/math/utils.hpp

lib/others

• Binary GCD (lib/others/binary_gcd.hpp)
• Compression (座標圧縮) (lib/others/compression.hpp)
• Doubling (ダブリング) (lib/others/doubling.hpp)
• Exhaustive Search (bit 全探索) (lib/others/exhaustive_search.hpp)
• lib/others/golden_section_search.hpp
• Maximum Rectangle (最大長方形) (lib/others/maximum_rectangle.hpp)
• lib/others/others.hpp
• Random (乱数生成) (lib/others/random.hpp)
• lib/others/run_length_encoding.hpp
• val_range (lib/others/val_range.hpp)
• lib/others/zorbrist_hash.hpp

lib/polynomial

• Bostan-Mori (lib/polynomial/bostan_mori.hpp)
• Formal Power Series (形式的冪級数) (lib/polynomial/formal_power_series.hpp)
• Multipoint Evaluation (多点評価) (lib/polynomial/multipoint_evaluation.hpp)
• Polynomial Interpolation (多項式補間) (lib/polynomial/polynomial_interpolation.hpp)
• Product of Polynomial Sequence (多項式列の総積) (lib/polynomial/product_of_polynomial_sequence.hpp)
• Taylor Shift (lib/polynomial/taylor_shift.hpp)

lib/string

• calc-next (lib/string/calc_next.hpp)
• LCP Array (lib/string/lcp_array.hpp)
• Lyndon Factorization (lib/string/lyndon_factorization.hpp)
• Manacher (lib/string/manacher.hpp)
• lib/string/permutation.cpp
• Rolling Hash (lib/string/rolling_hash.hpp)
• Run Enumerate (lib/string/run_enumerate.hpp)
• SA-IS (lib/string/sa_is.hpp)
• lib/string/suffix_array.hpp
• Wildcard Pattern Matching (lib/string/wildcard_pattern_matching.hpp)
• Z Algorithm (lib/string/z_algorithm.hpp)

lib

• lib/template.cpp

Verification Files

test/aoj/alds1

• test/aoj/alds1/alds1_10_c.test.cpp
• test/aoj/alds1/alds1_14_b.test.cpp
• test/aoj/alds1/alds1_1_c.test.cpp
• test/aoj/alds1/alds1_5_a.test.cpp
• test/aoj/alds1/alds1_5_d.test.cpp

test/aoj/cgl

• test/aoj/cgl/cgl_3_a.test.cpp

test/aoj/dsl

• test/aoj/dsl/dsl_1_b.test.cpp
• test/aoj/dsl/dsl_1_b_1.test.cpp
• test/aoj/dsl/dsl_5_b.test.cpp
• test/aoj/dsl/dsl_5_b_cs2d.test.cpp

test/aoj/grl

• test/aoj/grl/grl_1_b.test.cpp
• test/aoj/grl/grl_1_c.test.cpp
• test/aoj/grl/grl_5_a.test.cpp
• test/aoj/grl/grl_7_a.test.cpp

test/aoj/ntl

• test/aoj/ntl/ntl_1_a.test.cpp
• test/aoj/ntl/ntl_1_b.test.cpp
• test/aoj/ntl/ntl_2_a.test.cpp
• test/aoj/ntl/ntl_2_b.test.cpp
• test/aoj/ntl/ntl_2_c.test.cpp
• test/aoj/ntl/ntl_2_d.test.cpp
• test/aoj/ntl/ntl_2_e.test.cpp
• test/aoj/ntl/ntl_2_f.test.cpp

test/library_checker/convolution

• test/library_checker/convolution/bitwise_and_convolution.test.cpp
• test/library_checker/convolution/bitwise_and_convolution_1.test.cpp
• test/library_checker/convolution/bitwise_xor_convolution.test.cpp
• test/library_checker/convolution/convolution.test.cpp
• test/library_checker/convolution/convolution_mod_1000000007.test.cpp
• test/library_checker/convolution/convolution_mod_2_64.test.cpp
• test/library_checker/convolution/gcd_convolution.test.cpp
• test/library_checker/convolution/lcm_convolution.test.cpp

test/library_checker/data_structure

• test/library_checker/data_structure/area_of_union_of_rectangles.test.cpp
• test/library_checker/data_structure/associative_array.test.cpp
• test/library_checker/data_structure/deque_operate_all_composite.test.cpp
• test/library_checker/data_structure/double_ended_priority_queue.test.cpp
• test/library_checker/data_structure/dynamic_point_set_rectangle_affine_rectangle_sum.test.cpp
• test/library_checker/data_structure/line_add_get_min.test.cpp
• test/library_checker/data_structure/ordered_set.test.cpp
• test/library_checker/data_structure/persistent_queue.test.cpp
• test/library_checker/data_structure/persistent_unionfind.test.cpp
• test/library_checker/data_structure/persistent_unionfind_1.test.cpp
• test/library_checker/data_structure/point_add_range_sum.test.cpp
• test/library_checker/data_structure/point_add_rectangle_sum.test.cpp
• test/library_checker/data_structure/point_add_rectangle_sum_rt.test.cpp
• test/library_checker/data_structure/point_set_range_composite_large_array.test.cpp
• test/library_checker/data_structure/point_set_range_composite_large_array_1.test.cpp
• test/library_checker/data_structure/point_set_range_frequency.test.cpp
• test/library_checker/data_structure/queue_operate_all_composite.test.cpp
• test/library_checker/data_structure/range_affine_point_get.test.cpp
• test/library_checker/data_structure/range_affine_range_sum.test.cpp
• test/library_checker/data_structure/range_chmin_chmax_add_range_sum.test.cpp
• test/library_checker/data_structure/range_kth_smallest.test.cpp
• test/library_checker/data_structure/range_parallel_unionfind.test.cpp
• test/library_checker/data_structure/range_set_range_composite.test.cpp
• test/library_checker/data_structure/rectangle_add_point_get.test.cpp
• test/library_checker/data_structure/rectangle_sum.test.cpp
• test/library_checker/data_structure/segment_add_get_min.test.cpp
• test/library_checker/data_structure/set_xor_min.test.cpp
• test/library_checker/data_structure/static_range_count_distinct.test.cpp
• test/library_checker/data_structure/static_range_frequency.test.cpp
• test/library_checker/data_structure/static_range_inversions_query.test.cpp
• test/library_checker/data_structure/static_range_mode_query.test.cpp
• test/library_checker/data_structure/static_range_sum.test.cpp
• test/library_checker/data_structure/static_rmq.test.cpp
• test/library_checker/data_structure/static_rmq_1.test.cpp
• test/library_checker/data_structure/static_rmq_2.test.cpp
• test/library_checker/data_structure/unionfind.test.cpp
• test/library_checker/data_structure/unionfind_1.test.cpp
• test/library_checker/data_structure/unionfind_with_potential.test.cpp
• test/library_checker/data_structure/unionfind_with_potential_non_commutative_group.test.cpp

test/library_checker/enumerative_combinatorics

• test/library_checker/enumerative_combinatorics/binomial_coefficient_prime_mod.test.cpp
• test/library_checker/enumerative_combinatorics/binomial_coefficient_prime_mod_1.test.cpp
• test/library_checker/enumerative_combinatorics/factorial.test.cpp
• test/library_checker/enumerative_combinatorics/many_factorials.test.cpp
• test/library_checker/enumerative_combinatorics/montmort_number_mod.test.cpp
• test/library_checker/enumerative_combinatorics/number_of_subsequences.test.cpp
• test/library_checker/enumerative_combinatorics/partition_function.test.cpp
• test/library_checker/enumerative_combinatorics/sharp_p_subset_sum.test.cpp
• test/library_checker/enumerative_combinatorics/stirling_number_of_the_second_kind.test.cpp
• test/library_checker/enumerative_combinatorics/stirling_number_of_the_second_kind_fixed_k.test.cpp

test/library_checker/geometry

• test/library_checker/geometry/closest_pair.test.cpp
• test/library_checker/geometry/count_points_in_triangle.test.cpp
• test/library_checker/geometry/furthest_pair.test.cpp
• test/library_checker/geometry/manhattanmst.test.cpp
• test/library_checker/geometry/sort_points_by_argument.test.cpp
• test/library_checker/geometry/static_convex_hull.test.cpp

test/library_checker/graph

• test/library_checker/graph/assignment.test.cpp
• test/library_checker/graph/biconnected_components.test.cpp
• test/library_checker/graph/bipartitematching.test.cpp
• test/library_checker/graph/chromatic_number.test.cpp
• test/library_checker/graph/connected_components_of_complement_graph.test.cpp
• test/library_checker/graph/connected_components_of_complement_graph_1.test.cpp
• test/library_checker/graph/counting_spanning_tree_directed.test.cpp
• test/library_checker/graph/counting_spanning_tree_undirected.test.cpp
• test/library_checker/graph/cycle_detection.test.cpp
• test/library_checker/graph/cycle_detection_undirected.test.cpp
• test/library_checker/graph/enumerate_cliques.test.cpp
• test/library_checker/graph/enumerate_triangles.test.cpp
• test/library_checker/graph/eulerian_trail_directed.test.cpp
• test/library_checker/graph/eulerian_trail_undirected.test.cpp
• test/library_checker/graph/maximum_independent_set.test.cpp
• test/library_checker/graph/minimum_diameter_spanning_tree.test.cpp
• test/library_checker/graph/minimum_spanning_tree.test.cpp
• test/library_checker/graph/scc.test.cpp
• test/library_checker/graph/shortest_path.test.cpp
• test/library_checker/graph/two_edge_connected_components.test.cpp

test/library_checker/linear_algebra

• test/library_checker/linear_algebra/inverse_matrix.test.cpp
• test/library_checker/linear_algebra/matrix_det.test.cpp
• test/library_checker/linear_algebra/matrix_product.test.cpp
• test/library_checker/linear_algebra/matrix_rank.test.cpp
• test/library_checker/linear_algebra/pow_of_matrix.test.cpp

test/library_checker/number_theory

• test/library_checker/number_theory/bell_number.test.cpp
• test/library_checker/number_theory/bernoulli_number.test.cpp
• test/library_checker/number_theory/discrete_logarithm_mod.test.cpp
• test/library_checker/number_theory/enumerate_primes.test.cpp
• test/library_checker/number_theory/enumerate_quotients.test.cpp
• test/library_checker/number_theory/factorize.test.cpp
• test/library_checker/number_theory/kth_root_integer.test.cpp
• test/library_checker/number_theory/primality_test.test.cpp
• test/library_checker/number_theory/primitive_root.test.cpp
• test/library_checker/number_theory/rational_approximation.test.cpp
• test/library_checker/number_theory/sqrt_mod.test.cpp

test/library_checker/other

• test/library_checker/other/kth_term_of_linearly_recurrent_sequence.test.cpp
• test/library_checker/other/longest_increasing_subsequence.test.cpp
• test/library_checker/other/two_sat.test.cpp

test/library_checker/polynomial

• test/library_checker/polynomial/division_of_polynomials.test.cpp
• test/library_checker/polynomial/exp_of_formal_power_series.test.cpp
• test/library_checker/polynomial/inv_of_formal_power_series.test.cpp
• test/library_checker/polynomial/log_of_formal_power_series.test.cpp
• test/library_checker/polynomial/multipoint_evaluation.test.cpp
• test/library_checker/polynomial/polynomial_interpolation.test.cpp
• test/library_checker/polynomial/polynomial_taylor_shift.test.cpp
• test/library_checker/polynomial/pow_of_formal_power_series.test.cpp
• test/library_checker/polynomial/product_of_polynomial_sequence.test.cpp
• test/library_checker/polynomial/sqrt_of_formal_power_series.test.cpp

test/library_checker/sample

• test/library_checker/sample/many_aplusb_128bit.test.cpp

test/library_checker/set_power_series

• test/library_checker/set_power_series/subset_convolution.test.cpp

test/library_checker/string

• test/library_checker/string/enumerate_palindromes.test.cpp
• test/library_checker/string/lyndon_factorization.test.cpp
• test/library_checker/string/number_of_substrings.test.cpp
• test/library_checker/string/number_of_substrings_1.test.cpp
• test/library_checker/string/runenumerate.test.cpp
• test/library_checker/string/suffixarray.test.cpp
• test/library_checker/string/suffixarray_1.test.cpp
• test/library_checker/string/wildcard_pattern_matching.test.cpp
• test/library_checker/string/z_algorithm.test.cpp

test/library_checker/tree

• test/library_checker/tree/cartesian_tree.test.cpp
• test/library_checker/tree/jump_on_tree.test.cpp
• test/library_checker/tree/lca_hl.test.cpp
• test/library_checker/tree/rooted_tree_topological_order_with_minimum_inversions.test.cpp
• test/library_checker/tree/tree_diameter.test.cpp
• test/library_checker/tree/tree_path_composite_sum.test.cpp
• test/library_checker/tree/vertex_add_path_sum.test.cpp
• test/library_checker/tree/vertex_add_subtree_sum.test.cpp
• test/library_checker/tree/vertex_set_path_composite.test.cpp

test/yukicoder

• test/yukicoder/yuki_1008.test.cpp
• test/yukicoder/yuki_117.test.cpp
• test/yukicoder/yuki_1464.test.cpp
• test/yukicoder/yuki_184.test.cpp
• test/yukicoder/yuki_186.test.cpp
• test/yukicoder/yuki_187.test.cpp
• test/yukicoder/yuki_206.test.cpp
• test/yukicoder/yuki_2078.test.cpp
• test/yukicoder/yuki_2087.test.cpp
• test/yukicoder/yuki_2119.test.cpp
• test/yukicoder/yuki_2304.test.cpp
• test/yukicoder/yuki_2712.test.cpp
• test/yukicoder/yuki_2809.test.cpp
• test/yukicoder/yuki_2946.test.cpp
• test/yukicoder/yuki_3022.test.cpp
• test/yukicoder/yuki_416.test.cpp
• test/yukicoder/yuki_888.test.cpp
• test/yukicoder/yuki_888_1.test.cpp
• test/yukicoder/yuki_901.test.cpp