CP-templates

template used for online programming contest. some of the code are not written by myself, and these codes would contain reference to the original sources.

the “KACTL” in the reference of template code is from https://github.com/kth-competitive-programming/kactl

Library Files

actedmonoid

• actedmonoid/actedMonoid_addMax.cpp
• actedmonoid/actedMonoid_addMin.cpp
• actedmonoid/actedMonoid_addMinCnt.cpp
• actedmonoid/actedMonoid_addSum.cpp
• actedmonoid/actedMonoid_affineSum.cpp
• actedmonoid/actedMonoid_setMax.cpp
• actedmonoid/actedMonoid_setMin.cpp
• actedmonoid/actedMonoid_setSum.cpp

combi

• combi/bell_number.cpp
• combi/bernoulliNumber.cpp
• combi/binom.cpp
• combi/chromaticNumber.cpp
• combi/countEulerianCircuit.cpp
• combi/countSpanningForest.cpp
• combi/pathCounting.cpp
• combi/stirlingFirst.cpp
• combi/stirlingFirstModP.cpp
• combi/stirlingSecond.cpp
• combi/stirlingSecondCol.cpp
• combi/stirlingSecondModP.cpp

default

• default/t.cpp
• default/t_icpc.cpp
• default/tt.cpp
• default/ttt.cpp

dp

• dp/alienDP.cpp
• dp/dynamicTreeDP.cpp
• dp/rerooting_DP.cpp

ds/DSU

• ds/DSU/DSU.cpp
• ds/DSU/bipartite_DSU.cpp
• ds/DSU/potential_DSU.cpp
• ds/DSU/queue_DSU.cpp
• ds/DSU/rollback_DSU.cpp

ds

• ds/RMQ.cpp
• ds/binaryTrie.cpp
• ds/deque_aggregation.cpp
• ds/doubleEndedPQ.cpp
• ds/doubling.cpp
• ds/dynamicMedian.cpp
• ds/fast_set.cpp
• ds/fenwickTree.cpp
• ds/fenwickTree2D.cpp
• ds/hashTable.cpp
• ds/lineContainer.cpp
• ds/pSum2D.cpp
• ds/pbdsSet.cpp
• ds/persistentTreap.cpp
• ds/slidingWindowAggregation.cpp
• ds/slope_trick.cpp
• ds/sparseTable.cpp
• ds/sparseTable2D.cpp
• ds/treap.cpp
• ds/waveletMatrix.cpp

ds_problem

• ds_problem/area_of_union_of_rectangles.cpp
• ds_problem/frequency_of_tree_distance.cpp
• ds_problem/pointAddRectangleSum.cpp
• ds_problem/point_set_range_frequency.cpp
• ds_problem/rangeCountDistinct.cpp
• ds_problem/rectangleAddPointGet.cpp
• ds_problem/rectangleSum.cpp
• ds_problem/zero_one_on_tree.cpp

enumerate

• enumerate/enumerate_bit.cpp
• enumerate/enumerate_cartesian_product.cpp
• enumerate/enumerate_label_tree.cpp
• enumerate/enumerate_twelvefold.cpp
• enumerate/enumerate_unlabel_rooted_tree.cpp

geometry

• geometry/closest_pair.cpp
• geometry/convex_hull.cpp
• geometry/dynamic_hull.cpp
• geometry/in_hull.cpp
• geometry/line.cpp
• geometry/manhattanMST.cpp
• geometry/minkowski.cpp
• geometry/point.cpp

graph/connectivity

• graph/connectivity/BCC.cpp
• graph/connectivity/ECC.cpp
• graph/connectivity/SCC.cpp
• graph/connectivity/incrementalSCC.cpp

graph/flow

• graph/flow/Dinic.cpp
• graph/flow/MCMF.cpp

graph/functional_graph

• graph/functional_graph/func_graph.cpp
• graph/functional_graph/functionalGraphDistance.cpp

graph/matching

• graph/matching/hopcroftKarp.cpp
• graph/matching/hungarian.cpp
• graph/matching/minimumVertexCover.cpp

graph/minimum_spanning_tree

• graph/minimum_spanning_tree/Kruskal.cpp
• graph/minimum_spanning_tree/Prim.cpp

graph/misc

• graph/misc/2sat.cpp
• graph/misc/MIS.cpp
• graph/misc/complementConnectivity.cpp
• graph/misc/cycleDetection.cpp
• graph/misc/eulerianTrail.cpp
• graph/misc/steinerTree.cpp
• graph/misc/topoSort.cpp

graph/shortest_path

• graph/shortest_path/BFS_01.cpp
• graph/shortest_path/BFS_grid.cpp
• graph/shortest_path/Bellman_Ford.cpp
• graph/shortest_path/Dijkstra.cpp
• graph/shortest_path/Floyd_Warshall.cpp
• graph/shortest_path/path_recover.cpp

icpc

• icpc/BerlekampMassey.cpp
• icpc/Bostan_Mori.cpp
• icpc/aux_tree.cpp
• icpc/eliminate_double.cpp
• icpc/eliminate_mod.cpp
• icpc/eliminate_mod2.cpp
• icpc/lazySegtree.cpp
• icpc/multieval_and_interpolate.cpp
• icpc/polyope.cpp
• icpc/short_lca.cpp
• icpc/zkwBinarySearch.cpp

linalg

• linalg/matrixMint.cpp
• linalg/xorBasis.cpp
• linalg/xorBasis2.cpp

misc

• misc/LIS.cpp
• misc/arrayUtility.cpp
• misc/bigint.cpp
• misc/compression.cpp
• misc/random.cpp
• misc/sharpPSubsetSum.cpp

modint

• modint/MontgomeryModInt.cpp
• modint/dynamicMontgomeryModInt.cpp
• modint/dynamicSimpleMint.cpp

numtheory

• numtheory/crt.cpp
• numtheory/dirichlet_convolution.cpp
• numtheory/divisor_enumeration.cpp
• numtheory/exgcd.cpp
• numtheory/factorize_pollard_rho.cpp
• numtheory/factorize_sqrt.cpp
• numtheory/gcd_convolution.cpp
• numtheory/lcm_convolution.cpp
• numtheory/linear_sieve.cpp
• numtheory/mu_array.cpp
• numtheory/phi_array.cpp
• numtheory/primality_array.cpp
• numtheory/prime_table.cpp
• numtheory/primitive_root.cpp
• numtheory/quotient_enumerate.cpp
• numtheory/sqrt_mod.cpp
• numtheory/sum_of_floor_of_linear.cpp
• numtheory/zeta_mobius_on_divisibility_lattice.cpp

poly

• poly/BerlekampMassey.cpp
• poly/BostanMori.cpp
• poly/FFT.cpp
• poly/FFTmod.cpp
• poly/FPS.cpp
• poly/FPSsqrt.cpp
• poly/NTT.cpp
• poly/NTT2D.cpp
• poly/NTTanymod.cpp
• poly/NTTmint.cpp
• poly/chirp_Z_transform.cpp
• poly/compositionalInverse.cpp
• poly/kthTermOfPowers.cpp
• poly/min_plus_convolution.cpp
• poly/mulConvolution.cpp
• poly/pref_suf_prod_eval.cpp
• poly/semiOnlineConvolution.cpp
• poly/sparsePolyope.cpp
• poly/taylorShift.cpp

segtree

• segtree/dualSegmentTree.cpp
• segtree/lazySegmentTree.cpp
• segtree/lichaoSegmentTree.cpp
• segtree/persistentSegmentTree.cpp
• segtree/rangeSetSegmentTree.cpp
• segtree/segmentTree.cpp
• segtree/segmentTree2D.cpp
• segtree/segmentTreeLazyDynamic.cpp
• segtree/ultraLazySegmentTree.cpp

setfunc

• setfunc/FWHT.cpp
• setfunc/fastSubsetTransform.cpp
• setfunc/fastZetaTransform.cpp

string

• string/AhoCorasick.cpp
• string/KMP.cpp
• string/KMPA.cpp
• string/Manacher.cpp
• string/longestCommonSubstring.cpp
• string/palindromicTree.cpp
• string/rollingHash.cpp
• string/suffixArray.cpp
• string/wildcardPatternMatcing.cpp
• string/zFunc.cpp

tree

• tree/HLD.cpp
• tree/LCA.cpp
• tree/auxiliary_tree.cpp
• tree/cartesian_tree.cpp
• tree/centroid_tree.cpp
• tree/prufer_recover.cpp
• tree/static_top_tree.cpp
• tree/tree.cpp
• tree/tree_diameter.cpp
• tree/tree_hash.cpp
• tree/weighted_tree_diameter.cpp

Verification Files

test

• test/Z_algorithm.test.cpp
• test/addition_of_big_integers.test.cpp
• test/addition_of_big_integers_2.test.cpp
• test/aho_corasick.test.cpp
• test/area_of_union_of_rectangles.test.cpp
• test/assignment.test.cpp
• test/assignment_problem.test.cpp
• test/associative_array.test.cpp
• test/bell_number.test.cpp
• test/bernoulli_number.test.cpp
• test/biconnected_components.test.cpp
• test/binomial_coefficient_prime_mod.test.cpp
• test/bipartitematching.test.cpp
• test/bipartitematching_2.test.cpp
• test/cartesian_tree.test.cpp
• test/chromatic_number.test.cpp
• test/closest_pair.test.cpp
• test/compositional_inverse_of_formal_power_series_large.test.cpp
• test/connected_components_of_complement_graph.test.cpp
• test/convolution.test.cpp
• test/convolution_1e9+7.test.cpp
• test/counting_eulerian_circuits.test.cpp
• test/counting_spanning_tree_directed.test.cpp
• test/counting_spanning_tree_undirected.test.cpp
• test/cycle_detection_directed.test.cpp
• test/cycle_detection_undirected.test.cpp
• test/deque_operate_all_composite.test.cpp
• test/determinant_of_matrix.test.cpp
• test/division_of_polynomials.test.cpp
• test/double_ended_priority_queue.test.cpp
• test/dynamic_sequence_range_affine_range_sum.test.cpp
• test/enumerate_palindromes.test.cpp
• test/enumerate_primes.test.cpp
• test/enumerate_quotients.test.cpp
• test/eulerian_trail_directed.test.cpp
• test/eulerian_trail_undirected.test.cpp
• test/exp_of_formal_power_series.test.cpp
• test/exp_of_formal_power_series_sparse.test.cpp
• test/factorize.test.cpp
• test/find_linear_recurrence.test.cpp
• test/frequency_table_of_tree_distance.test.cpp
• test/gcd_convolution.test.cpp
• test/incremental_scc.test.cpp
• test/inv_of_formal_power_series.test.cpp
• test/inv_of_formal_power_series_sparse.test.cpp
• test/inverse_matrix.test.cpp
• test/jump_on_tree.test.cpp
• test/jump_on_tree_2.test.cpp
• test/jump_on_tree_3.test.cpp
• test/kth_term_of_linearly_recurrent_sequence.test.cpp
• test/lca.test.cpp
• test/lca_2.test.cpp
• test/lca_3.test.cpp
• test/lca_4.test.cpp
• test/lcm_convolution.test.cpp
• test/line_add_get_min.test.cpp
• test/log_of_formal_power_series.test.cpp
• test/log_of_formal_power_series_sparse.test.cpp
• test/longest_common_substring.test.cpp
• test/longest_increasing_subsequence.test.cpp
• test/matching_on_bipartite_graph.test.cpp
• test/matrix_product.test.cpp
• test/matrix_rank.test.cpp
• test/matrix_rank_mod_2.test.cpp
• test/maximum_independent_set.test.cpp
• test/min_plus_convolution_convex_arbitrary.test.cpp
• test/minimum_spanning_tree_Kruskal.test.cpp
• test/minimum_spanning_tree_Prim.test.cpp
• test/minimum_steiner_tree.test.cpp
• test/mul_modp_convolution.test.cpp
• test/multiplication_of_big_intergers.test.cpp
• test/multiplication_of_big_intergers_2.test.cpp
• test/multipoint_evaluation.test.cpp
• test/multipoint_evaluation_on_geometric_sequence.test.cpp
• test/mytest_auxiliary_tree.test.cpp
• test/mytest_enumerate_twelvefold.test.cpp
• test/mytest_prime_table.test.cpp
• test/mytest_tree.test.cpp
• test/mytest_tree_diameter.test.cpp
• test/persistent_unionfind.test.cpp
• test/point_add_range_sum.test.cpp
• test/point_add_rectangle_sum.test.cpp
• test/point_set_range_composite.test.cpp
• test/point_set_range_frequency.test.cpp
• test/point_set_tree_path_composite_sum_fixed_root.test.cpp
• test/polynomial_interpolation.test.cpp
• test/polynomial_taylor_shift.test.cpp
• test/pow_of_formal_power_series.test.cpp
• test/pow_of_formal_power_series_sparse.test.cpp
• test/pow_of_matrix.test.cpp
• test/predecessor_problem.test.cpp
• test/primality_test.test.cpp
• test/primitive_root.test.cpp
• test/product_of_polynomial_sequence.test.cpp
• test/queue_operate_all_composite.test.cpp
• test/range_add_range_min.test.cpp
• test/range_affine_point_get.test.cpp
• test/range_affine_range_sum.test.cpp
• test/range_kth_smallest.test.cpp
• test/range_kth_smallest2.test.cpp
• test/range_reverse_range_sum.test.cpp
• test/range_set_range_composite.test.cpp
• test/rectangle_add_point_get.test.cpp
• test/rectangle_sum.test.cpp
• test/rooted_tree_isomorphism_classification.test.cpp
• test/segment_add_get_min.test.cpp
• test/set_xor_min.test.cpp
• test/sharp_p_subset_sum.test.cpp
• test/shortest_path_dense.test.cpp
• test/shortest_path_sparse.test.cpp
• test/sqrt_of_formal_power_series.test.cpp
• test/sqrt_of_formal_power_series_sparse.test.cpp
• test/static_RMQ.test.cpp
• test/static_RMQ_2.test.cpp
• test/static_convex_hull.test.cpp
• test/static_range_count_distinct.test.cpp
• test/static_range_frequency.test.cpp
• test/stirling_number_of_first_kind_small_p_large_n.test.cpp
• test/stirling_number_of_second_kind_small_p_large_n.test.cpp
• test/stirling_number_of_the_first_kind.test.cpp
• test/stirling_number_of_the_second_kind.test.cpp
• test/stirling_number_of_the_second_kind_fixed_k.test.cpp
• test/strongly_connected_components.test.cpp
• test/subset_convolution.test.cpp
• test/system_of_linear_equations.test.cpp
• test/tree_diameter.test.cpp
• test/tree_path_composite_sum.test.cpp
• test/two_edge_connected_components.test.cpp
• test/two_sat.test.cpp
• test/unionfind.test.cpp
• test/unionfind_with_potential.test.cpp
• test/unionfind_with_potential_non_commutative_group.test.cpp
• test/vertex_add_path_sum.test.cpp
• test/vertex_add_range_contour_sum_on_tree.test.cpp
• test/vertex_add_subtree_sum.test.cpp
• test/vertex_get_range_contour_add_on_tree.test.cpp
• test/vertex_set_path_composite.test.cpp
• test/wildcard_pattern_matching.test.cpp
• test/yuki_1097.test.cpp
• test/yuki_1344.test.cpp
• test/yuki_1868.test.cpp
• test/yuki_2544.test.cpp
• test/yuki_2606.test.cpp
• test/yuki_2613.test.cpp
• test/yuki_2654.test.cpp