cp-library

メモ

Library Files

src

• template (src/base.hpp)
• debug template (src/debug.hpp)

src/convolution

• Relaxed Convolution (src/convolution/RelaxedConvolution.hpp)
• Convolution (Arbitary mod) (src/convolution/convolution_arbitary_mod.hpp)
• GCD Convolution (src/convolution/gcd_convolution.hpp)
• Min Plus Convolution (Convex and Arbitary) (src/convolution/min_plus_convolution_convex_arbitrary.hpp)
• Min Plus Convolution (Convex and Convex) (src/convolution/min_plus_convolution_convex_convex.hpp)
• Subset Convolution (src/convolution/subset_convolution.hpp)

src/datastructure

• Binary Trie (src/datastructure/BinaryTrie.hpp)
• Convex Hull Trick (Add-Monotonic Slope Optimization) (src/datastructure/ConvexHullTrick.hpp)
• Cumulative Sum (2D) (src/datastructure/CumulativeSum2D.hpp)
• Line Container (based on kactl) (src/datastructure/LineContainer.hpp)
• Mo's Algorithm (src/datastructure/Mo.hpp)
• Offline Dynamic Connectivity (src/datastructure/OfflineDynamicConnectivity.hpp)
• Partially Persistent Union Find (src/datastructure/PartiallyPersistentUnionFind.hpp)
• Potentialized Union Find (src/datastructure/PotentializedUnionFind.hpp)
• Range Tree (src/datastructure/RangeTree.hpp)
• Sliding Window Aggregation (src/datastructure/SlidingWindowAggregation.hpp)
• Slope Trick (src/datastructure/SlopeTrick.hpp)
• Sparse Table (src/datastructure/SparseTable.hpp)
• Union Find with Undo Operation (src/datastructure/UndoUnionFind.hpp)
• Union Find (Disjoint Set Union) (src/datastructure/UnionFind.hpp)

src/enumerative_combinatorics

• Bell Number (src/enumerative_combinatorics/bell_number.hpp)

src/geometry

• Circle (src/geometry/Circle.hpp)
• Line (src/geometry/Line.hpp)
• Point (src/geometry/Point.hpp)
• Point (3D) (src/geometry/Point3D.hpp)
• Polygon (src/geometry/Polygon.hpp)
• Counter Clockwise (src/geometry/ccw.hpp)
• Circumcircle (src/geometry/circumcircle.hpp)
• Closest Pair (src/geometry/closest_pair.hpp)
• Contain (src/geometry/contain.hpp)
• Convex Cut (src/geometry/convex_cut.hpp)
• Convex Diameter (src/geometry/convex_diameter.hpp)
• Convex Hull (src/geometry/convex_hull.hpp)
• Crosspoint (src/geometry/crosspoint.hpp)
• Distance (src/geometry/distance.hpp)
• Furthest Pair (src/geometry/furthest_pair.hpp)
• Incircle (src/geometry/incircle.hpp)
• projection (src/geometry/projection.hpp)
• reflection (src/geometry/reflection.hpp)
• Sort Points by Argument (src/geometry/sort_points_by_argument.hpp)

src/graph

• Bellman Ford (src/graph/BellmanFord.hpp)
• Bipartite Matching (src/graph/BipartiteMatching.hpp)
• Cycle Detection (Directed) (src/graph/DirectedCycleDetection.hpp)
• Directed Shortest Cycle (src/graph/DirectedShortestCycle.hpp)
• Edge Matching (src/graph/EdgeMatching.hpp)
• Eulerian Trail (src/graph/EulerianTrail.hpp)
• Functional Graph (src/graph/FunctionalGraph.hpp)
• LowLink (with Two Edge Connected Components, Bi Connected Components) (src/graph/LowLink.hpp)
• Primal Dual on DAG (Minimum Cost Flow with Negative Edges) (src/graph/PrimalDualonDAG.hpp)
• Range Edge Graph (src/graph/RangeEdgeGraph.hpp)
• Strongly Connected Components (src/graph/StronglyConnectedComponents.hpp)
• 2-SAT (src/graph/TwoSAT.hpp)
• Cycle Detection (Undirected) (src/graph/UndirectedCycleDetection.hpp)
• Undirected Shortest Cycle (src/graph/UndirectedShortestCycle.hpp)
• Shortest Path on Complement Graph (src/graph/complement_graph_shortest_path.hpp)
• Count Cliques (src/graph/count_clique.hpp)
• Enuemrate $C_3$, Count $C_4, K_4$ (src/graph/count_graphs.hpp)
• Count Independent Sets (src/graph/count_independent_set.hpp)
• Enumerate Cliques (src/graph/enumerate_cliques.hpp)

src/math

• Nimber (src/math/Nimber.hpp)
• Simplex (src/math/Simplex.hpp)
• binary gcd (src/math/binary_gcd.hpp)
• Binomial Coefficients (src/math/binomial.hpp)
• Counting Primes (src/math/counting_primes.hpp)
• Discrete Logarithm (src/math/discrete_logarithm.hpp)
• Elementary Math (src/math/elementary_math.hpp)
• Exp of Set Power Series (src/math/exp_of_set_power_series.hpp)
• Longest Increasing Subsequence (LIS) (src/math/longest_increasing_subsequence.hpp)
• Number of Increasing Sequences Between Two Sequences (src/math/number_of_increasing_sequences_between_two_sequences.hpp)
• Set Function (FZT, FMT, FWHT) (src/math/set_function.hpp)
• Sum of Multiplicative Function (src/math/sum_of_multiplicative_function.hpp)

src/matrix

• Matrix on $\mathbb{F}_2$ (src/matrix/F2Matrix.hpp)
• Matrix (src/matrix/Matrix.hpp)
• Square Matrix (src/matrix/SquareMatrix.hpp)
• Characteristic Polynomial / $\det(M_0 + x M_1)$ (src/matrix/characteristic_polynomial.hpp)

src/optimization

• Binary Optimization (Project Selection Problem) (src/optimization/BinaryOptimization.hpp)
• $K$-ary Optimization (src/optimization/KaryOptimization.hpp)
• Subset Sum $\mathrm{O}(NS), \mathrm{O}(N a _ {\max})$ (src/optimization/SubsetSum.hpp)
• Golden Section Search (src/optimization/golden_section_search.hpp)
• Hungarian (Assignment Problem) (src/optimization/hungarian.hpp)
• Max Flow (Lower Bound Constraints) (src/optimization/maxflow_lowerbound.hpp)
• Minimum Cost b-flow (src/optimization/min_cost_b_flow.hpp)
• $d$-edge Shortest Path on Monge Graph (src/optimization/monge_d_edge_shortest_path.hpp)
• Monotone Minima (src/optimization/monotone_minima.hpp)
• SMAWK Algotirhm (src/optimization/smawk.hpp)

src/polynomial

• Bostan-Mori Algorithm (src/polynomial/BostanMori.hpp)
• Formal Power Series (src/polynomial/FormalPowerSeries.hpp)
• Power Projection (src/polynomial/coefficient_of_powers.hpp)
• Difference Product (Vandermonde's Determinant) (src/polynomial/difference_product.hpp)
• Lagrange Interpolation (src/polynomial/lagrange_interpolation.hpp)
• Multipoint Evaluation (src/polynomial/multipoint_evaluation.hpp)
• Shift of Sampling Points of Polynomial (src/polynomial/shift_of_sampling_points_of_polynomial.hpp)
• $\#_p$ Subset Sum (src/polynomial/subset_sum.hpp)

src/string

• Aho Corasick (src/string/AhoCorasick.hpp)
• Hash (reversible) (src/string/Hash.hpp)
• Manacher (Lonegest Palindromic Substring) (src/string/Manacher.hpp)
• Rolling Hash (src/string/RollingHash.hpp)
• Rolling Hash 2D (src/string/RollingHash2D.hpp)
• Trie (src/string/Trie.hpp)
• Z-Algorithm (src/string/Z_Algorithm.hpp)
• Run Enumerate (src/string/run_enumerate.hpp)
• Wildcard Pattern Matching (src/string/wildcard_pattern_matching.hpp)

src/tree

• Centroid Decomposition (src/tree/CentroidDecomposition.hpp)
• Scheduling Problem on Forest (src/tree/ForestScheduling.hpp)
• Heavy Light Decomposition (src/tree/HeavyLightDecomposition.hpp)
• Merge Process Tree (src/tree/MergeTree.hpp)
• Rerooting (src/tree/Rerooting.hpp)
• Static Top Tree (src/tree/StaticTopTree.hpp)
• Tree Diameter (src/tree/TreeDiameter.hpp)
• Counting Spanning Trees (src/tree/counting_spanning_trees.hpp)

src/util

• Dice (src/util/Dice.hpp)
• Random Number Generator (src/util/RandomNumberGenerator.hpp)
• src/util/RandomUndirectedGraphGenarator.hpp
• Rational Number (src/util/Rational.hpp)
• modint (input/output) (src/util/modint.hpp)
• Stack Extend (src/util/stack_extend.hpp)

Verification Files

test/aoj

• test/aoj/1131.test.cpp
• test/aoj/1181.test.cpp
• test/aoj/1615.test.cpp
• test/aoj/2903.test.cpp
• test/aoj/ALDS1_14_B.test.cpp
• test/aoj/ALDS1_14_C.test.cpp
• test/aoj/CGL_1_A.test.cpp
• test/aoj/CGL_1_B.test.cpp
• test/aoj/CGL_1_C.test.cpp
• test/aoj/CGL_2_A.test.cpp
• test/aoj/CGL_2_B.test.cpp
• test/aoj/CGL_2_C.test.cpp
• test/aoj/CGL_2_D.test.cpp
• test/aoj/CGL_3_A.test.cpp
• test/aoj/CGL_3_B.test.cpp
• test/aoj/CGL_3_C.test.cpp
• test/aoj/CGL_4_A.test.cpp
• test/aoj/CGL_4_B.test.cpp
• test/aoj/CGL_4_C.test.cpp
• test/aoj/CGL_5_A.test.cpp
• test/aoj/CGL_7_A.test.cpp
• test/aoj/CGL_7_B.test.cpp
• test/aoj/CGL_7_C.test.cpp
• test/aoj/CGL_7_D.test.cpp
• test/aoj/CGL_7_E.test.cpp
• test/aoj/DPL_5_E.test.cpp
• test/aoj/DSL_1_B.test.cpp
• test/aoj/DSL_5_B.test.cpp
• test/aoj/GRL_1_B.test.cpp
• test/aoj/GRL_3_A.test.cpp
• test/aoj/GRL_3_B.test.cpp
• test/aoj/GRL_5_B.test.cpp
• test/aoj/GRL_5_C.test.cpp
• test/aoj/ITP1_11_A.test.cpp
• test/aoj/ITP1_11_B.test.cpp
• test/aoj/ITP1_11_C.test.cpp
• test/aoj/ITP1_11_D.test.cpp
• test/aoj/NTL_1_A.test.cpp
• test/aoj/NTL_1_B.test.cpp
• test/aoj/NTL_1_C.test.cpp
• test/aoj/NTL_1_D.test.cpp
• test/aoj/NTL_1_E.test.cpp
• test/aoj/example.test.cpp

test/yosupo

• test/yosupo/aplusb.test.cpp
• test/yosupo/assignment.test.cpp
• test/yosupo/bell_number.test.cpp
• test/yosupo/binomial_coefficient_prime_mod.test.cpp
• test/yosupo/bipartitematching.test.cpp
• test/yosupo/bitwise_and_convolution.test.cpp
• test/yosupo/bitwise_xor_convolution.test.cpp
• test/yosupo/characteristic_polynomial.test.cpp
• test/yosupo/closest_pair.test.cpp
• test/yosupo/convolution_mod.relaxedconvolution.test.cpp
• test/yosupo/convolution_mod_1000000007.test.cpp
• test/yosupo/counting_primes.test.cpp
• test/yosupo/counting_spanning_tree_directed.test.cpp
• test/yosupo/counting_spanning_tree_undirected.test.cpp
• test/yosupo/cycle_detection.test.cpp
• test/yosupo/cycle_detection_undirected.test.cpp
• test/yosupo/discrete_logarithm_mod.test.cpp
• test/yosupo/division_of_polynomials.test.cpp
• test/yosupo/enumerate_cliques.test.cpp
• test/yosupo/enumerate_palindromes.test.cpp
• test/yosupo/enumerate_triangles.test.cpp
• test/yosupo/exp_of_formal_power_series.test.cpp
• test/yosupo/exp_of_set_power_series.test.cpp
• test/yosupo/frequency_table_of_tree_distance.test.cpp
• test/yosupo/furthest_pair.test.cpp
• test/yosupo/gcd_convolution.test.cpp
• test/yosupo/inv_of_formal_power_series.test.cpp
• test/yosupo/inverse_matrix.squarematrix.test.cpp
• test/yosupo/inverse_matrix.test.cpp
• test/yosupo/inverse_matrix_mod_2.test.cpp
• test/yosupo/jump_on_tree.test.cpp
• test/yosupo/kth_term_of_linearly_recurrent_sequence.test.cpp
• test/yosupo/line_add_get_min.test.cpp
• test/yosupo/log_of_formal_power_series.test.cpp
• test/yosupo/longest_increasing_subsequence.test.cpp
• test/yosupo/matrix_det.squarematrix.test.cpp
• test/yosupo/matrix_det.test.cpp
• test/yosupo/matrix_det_mod_2.test.cpp
• test/yosupo/matrix_product.test.cpp
• test/yosupo/matrix_product_mod_2.test.cpp
• test/yosupo/matrix_rank.test.cpp
• test/yosupo/min_plus_convolution_convex_arbitrary.smawk.test.cpp
• test/yosupo/min_plus_convolution_convex_arbitrary.test.cpp
• test/yosupo/min_plus_convolution_convex_convex.test.cpp
• test/yosupo/multipoint_evaluation.test.cpp
• test/yosupo/nim_product_64.test.cpp
• test/yosupo/number_of_increasing_sequences_between_two_sequences.test.cpp
• test/yosupo/persistent_unionfind.UndoUnionFind.test.cpp
• test/yosupo/point_add_rectangle_sum.test.cpp
• test/yosupo/point_set_tree_path_composite_sum_fixed_root.test.cpp
• test/yosupo/polynomial_taylor_shift.test.cpp
• test/yosupo/pow_of_formal_power_series.test.cpp
• test/yosupo/pow_of_formal_power_series_sparse.test.cpp
• test/yosupo/pow_of_matrix.squarematrix.test.cpp
• test/yosupo/pow_of_matrix.test.cpp
• test/yosupo/product_of_polynomial_sequence.test.cpp
• test/yosupo/queue_operate_all_composite.test.cpp
• test/yosupo/runenumerate.test.cpp
• test/yosupo/scc.test.cpp
• test/yosupo/set_xor_min.test.cpp
• test/yosupo/sharp_p_subset_sum.test.cpp
• test/yosupo/shift_of_sampling_points_of_polynomial.test.cpp
• test/yosupo/sort_points_by_argument.test.cpp
• test/yosupo/sqrt_of_formal_power_series.test.cpp
• test/yosupo/static_convex_hull.test.cpp
• test/yosupo/static_range_inversions_query.test.cpp
• test/yosupo/staticrmq.test.cpp
• test/yosupo/subset_convolution.test.cpp
• test/yosupo/sum_of_multiplicative_function.test.cpp
• test/yosupo/sum_of_totient_function.test.cpp
• test/yosupo/system_of_linear_equations.test.cpp
• test/yosupo/system_of_linear_equations_mod_2.test.cpp
• test/yosupo/tree_diameter.test.cpp
• test/yosupo/tree_path_composite_sum.test.cpp
• test/yosupo/two_edge_connected_components.test.cpp
• test/yosupo/two_sat.test.cpp
• test/yosupo/unionfind.test.cpp
• test/yosupo/vertex_add_path_sum.test.cpp
• test/yosupo/vertex_add_subtree_sum.test.cpp
• test/yosupo/vertex_set_path_composite.test.cpp
• test/yosupo/wildcard_pattern_matching.test.cpp
• test/yosupo/zalgorithm.test.cpp

test/yukicoder

• test/yukicoder/1240.test.cpp
• test/yukicoder/1269.test.cpp
• test/yukicoder/1289.test.cpp
• test/yukicoder/1320.test.cpp
• test/yukicoder/1678.test.cpp
• test/yukicoder/1907.test.cpp
• test/yukicoder/1984.test.cpp
• test/yukicoder/2513.test.cpp
• test/yukicoder/453.test.cpp
• test/yukicoder/583.test.cpp
• test/yukicoder/665.test.cpp
• test/yukicoder/952.test.cpp