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/tt.cpp
• default/ttt.cpp

dp

• dp/alienDP.cpp
• dp/dynamicTreeDP.cpp
• dp/rerootingDP.cpp

ds

• ds/CHT.cpp
• ds/DSU.cpp
• ds/DSUrollback.cpp
• ds/LCA.cpp
• ds/RMQ.cpp
• ds/STT_pathAggregate.cpp
• auxiliaryTree (ds/auxiliaryTree.cpp)
• ds/binaryTrie.cpp
• ds/bipartiteDSU.cpp
• ds/centroidTree.cpp
• ds/doubleEndedPQ.cpp
• ds/doubling.cpp
• ds/dynamicHull.cpp
• ds/dynamicMedian.cpp
• ds/eulerTour.cpp
• ds/eulerTour2.cpp
• ds/fastJump.cpp
• ds/fenwickTree.cpp
• ds/fenwickTree2D.cpp
• ds/hashTable.cpp
• ds/heavyLightDecomposition.cpp
• ds/lineContainer.cpp
• ds/monoidDSU.cpp
• ds/pSum2D.cpp
• ds/pbdsSet.cpp
• ds/persistentTreap.cpp
• ds/potentialDSU.cpp
• ds/slidingWindowAggregation.cpp
• ds/slope_trick.cpp
• ds/smallToLargeDSU.cpp
• ds/sparseTable.cpp
• ds/sparseTable2D.cpp
• ds/staticTopTree.cpp
• treap (ds/treap.cpp)
• waveletMatrix (ds/waveletMatrix.cpp)
• ds/waveletMatrixWithMonoid.cpp

ds_problem

• ds_problem/area_of_union_of_rectangles.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

geometry

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

graph

• graph/0kBFS.cpp
• graph/2sat.cpp
• graph/BCC.cpp
• graph/BFS.cpp
• graph/Dijkstra.cpp
• graph/Dijkstra2.cpp
• graph/Dinic.cpp
• graph/ECC.cpp
• graph/Kruskal.cpp
• graph/MCMF.cpp
• graph/MIS.cpp
• graph/Prim.cpp
• graph/SCC.cpp
• graph/centroid.cpp
• graph/commutativePathComposition.cpp
• graph/complementConnectivity.cpp
• graph/cycleDetection.cpp
• graph/eulerianTrail.cpp
• graph/func_graph.cpp
• graph/functionalGraphDistance.cpp
• graph/gridBFS.cpp
• graph/hopcroftKarp.cpp
• graph/hungarian.cpp
• graph/incrementalSCC.cpp
• graph/minimumVertexCover.cpp
• graph/steinerTree.cpp
• graph/topoSort.cpp
• graph/treeDiameter.cpp
• graph/treeHash.cpp

icpc

• icpc/aux_tree.cpp
• icpc/eliminate_double.cpp
• icpc/eliminate_mod.cpp
• icpc/eliminate_mod2.cpp
• icpc/lazySegtree.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
• compression (misc/compression.cpp)
• misc/sharpPSubsetSum.cpp

modint

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

numtheory

• numtheory/crt.cpp
• numtheory/exgcd.cpp
• numtheory/fastFactorize.cpp
• numtheory/floorCeilSum.cpp
• numtheory/linearSieve.cpp
• numtheory/primitiveRoot.cpp
• numtheory/slowFactorize.cpp
• numtheory/sqrtMod.cpp
• numtheory/sumOfFloorOfLinear.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
• mulConvolution (poly/mulConvolution.cpp)
• poly/polyope.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

Verification Files

test

• test/Z_algorithm.test.cpp
• test/addition_of_big_integers.test.cpp
• test/addition_of_big_integers_2.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/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/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_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/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/kth_term_of_linearly_recurrent_sequence.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/lowest_common_ancestor.test.cpp
• test/lowest_common_ancestor_2.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.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/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/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_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.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_2544.test.cpp
• test/yuki_2606.test.cpp
• test/yuki_2613.test.cpp
• test/yuki_2654.test.cpp