えびちゃんライブラリ

えびちゃん のライブラリです。verification-helper で管理されています。

Library Files

!PREFACE!

• LICENSE
• TODO

DataStructure

• 単一更新セグメント木 (DataStructure/basic_segment_tree.cpp)
• rank/select 辞書 (DataStructure/bit_vector.cpp)
• 素集合データ構造 (DataStructure/disjoint_set.cpp)
• disjoint sparse table (DataStructure/disjoint_sparse_table.cpp)
• 動的ビットベクトル (DataStructure/dynamic_bitvector.cpp)
• fold 可能両端キュー (DataStructure/foldable_deque.cpp)
• fold 可能キュー (DataStructure/foldable_queue.cpp)
• 整数の区間の集合 (DataStructure/integral_intervals.cpp)
• Li-Chao tree (DataStructure/li_chao_tree.cpp)
• ポテンシャル関数 (DataStructure/potential_function.cpp)
• 矩形クエリ (DataStructure/rectangle_query.cpp)
• rollback 可能配列 (DataStructure/rollbackable_array.cpp)
• rollback 可能な素集合データ構造 (DataStructure/rollbackable_disjoint_set.cpp)
• 区間作用・区間和セグメント木 (DataStructure/segment_tree.cpp)
• sparse table (DataStructure/sparse_table.cpp)
• starry-sky tree (DataStructure/starry_sky_tree.cpp)
• ウェーブレット行列 (DataStructure/wavelet_matrix.cpp)

Graph

• 重みつきグラフの隣接リスト (Graph/adjacency_list.cpp)
• 容量つきグラフの隣接リスト (Graph/capacitated_adjacency_list.cpp)
• 最大流 (Dinitz 法) (Graph/dinitz.cpp)
• HL 分解 (Graph/hl_decomposition.cpp)
• 最深共通祖先 (segment tree) (Graph/lowest_common_ancestor_segment_tree.cpp)
• 最深共通祖先 (sparse table) (Graph/lowest_common_ancestor_sparse_table.cpp)
• 最深共通祖先 (squaring) (Graph/lowest_common_ancestor_squaring.cpp)
• 強連結成分分解 (Graph/scc.cpp)
• グラフ上の最短距離 (Graph/shortest_path.cpp)
• トポロジカルソート (Graph/topological_sort.cpp)
• 2-SAT (Graph/two_sat.cpp)

Graph/pre17

• グラフ上の最短距離 (Graph/pre17/shortest_path.cpp)

Math

• 素因数分解 (Math/factor.cpp)
• 線形計画法ソルバ (simplex 法) (Math/lp_solver.cpp)
• $i \bmod{n}$ の和 (Math/remainder_sum.cpp)

ModularArithmetic

• 連立合同式の解の構成 (ModularArithmetic/chinese_remaindering.cpp)
• 階乗の高速計算 (ModularArithmetic/factorial.cpp)
• Garner’s algorithm (ModularArithmetic/garner.cpp)
• 補間多項式 (ModularArithmetic/interpolation.cpp)
• 合同算術用クラス (ModularArithmetic/modint.cpp)
• 合同演算の前計算テーブル (ModularArithmetic/modtable.cpp)
• 合同算術の基本演算 (ModularArithmetic/operations.cpp)
• 多項式 (ModularArithmetic/polynomial.cpp)

String

• KMP 法 (String/knuth_morris_pratt_searcher.cpp)
• mod 2^61-1 のローリングハッシュ (String/rolling_hash_l61m1.cpp)
• 接尾辞配列 + induced sort (String/sa_is.cpp)
• 接尾辞配列 (String/suffix_array.cpp)
• ロリハを衝突させるやつ (tree attack) (String/tree_attack.cpp)
• Z algorithm (String/z_algorithm.cpp)

algorithm

• 木 DP (algorithm/dp_on_tree.cpp)
• Mo’s algorithm (algorithm/mo.cpp)
• 高速 Möbius 変換 (algorithm/moebius_transform.cpp)
• monotone minima (algorithm/monotone_minima.cpp)
• オンライン・オフライン変換 (algorithm/online_to_offline_optimization.cpp)
• 並列二分探索 (algorithm/parallel_binary_search.cpp)
• 黄金比分割の三分探索 (algorithm/ternary_search.cpp)
• 周期検出 (algorithm/tortoise_and_hare.cpp)

integer

• ビット演算 (integer/bit.cpp)
• 乗算との複合演算 (integer/fused_operations.cpp)
• 最大公約数 (integer/gcd.cpp)
• 整数の乗算の上位ワード (integer/mul_upper.cpp)
• オーバーフロー判定つき演算 (integer/overflow.cpp)
• 整数の平方根 (integer/sqrt.cpp)

misc/interface

• 作用のヘルパークラス (misc/interface/action.cpp)
• モノイドクラス (misc/interface/monoid.cpp)

utility

• 高速入出力 (utility/fast_io.cpp)
• 4-近傍 (utility/four_neighbor.cpp)
• 入出力 (utility/io.cpp)
• 型依存の定数 (utility/limits.cpp)
• ユーザ定義リテラル (utility/literals.cpp)
• 条件つき代入 (utility/set_if.cpp)

utility/action

• 区間最大値・区間加算用のヘルパークラス (utility/action/add_max.cpp)
• 区間最小値・区間加算用のヘルパークラス (utility/action/add_min.cpp)
• 区間和・区間加算用のヘルパークラス (utility/action/add_sum.cpp)
• 区間 Affine 変換・区間加算用のヘルパークラス (utility/action/affine_sum.cpp)
• 区間最小値・区間最小値更新用のヘルパークラス (utility/action/min_min.cpp)
• 区間和・区間代入用のヘルパークラス (utility/action/set_sum.cpp)

utility/macro

• 等値判定のテスト用マクロ (utility/macro/assert_eq.cpp)
• スタック拡張マクロ（魔法） (utility/macro/stack_extend.cpp)

utility/make

• ラムダ式の再帰 (utility/make/fix_point.cpp)
• 多次元 vector の作成 (utility/make/vector.cpp)

utility/make/pre17

• 多次元 vector の作成 (utility/make/pre17/vector.cpp)

utility/monoid

• 一次関数の合成を得る演算のモノイド (utility/monoid/composite.cpp)
• 最大公約数を得る演算のモノイド (utility/monoid/gcd.cpp)
• 和と長さを得る演算のモノイド (utility/monoid/length.cpp)
• max を得る演算のモノイド (utility/monoid/max.cpp)
• 部分和の最大値を得る演算のモノイドクラス (utility/monoid/max_subsum.cpp)
• min を得る演算のモノイド (utility/monoid/min.cpp)
• ロリハの演算のモノイド (utility/monoid/rolling_hash.cpp)
• モノイドクラス (utility/monoid/set.cpp)

Verify Files

• test/aoj_0355.test.cpp
• test/aoj_0425.test.cpp
• test/aoj_0575.test.cpp
• test/aoj_0613.test.cpp
• test/aoj_1180.test.cpp
• test/aoj_1322.test.cpp
• test/aoj_1595.test.cpp
• test/aoj_2178.test.cpp
• test/aoj_2313.test.cpp
• test/aoj_2444.test.cpp
• test/aoj_2446.test.cpp
• test/aoj_2450.test.cpp
• test/aoj_2580.test.cpp
• test/aoj_2748.test.cpp
• test/aoj_2880.test.cpp
• test/aoj_2911.test.cpp
• test/aoj_2970.test.cpp
• test/aoj_2976.test.cpp
• test/aoj_3110.test.cpp
• test/aoj_3111.test.cpp
• test/aoj_3112.test.cpp
• test/aoj_3112_sa_is.test.cpp
• test/aoj_ALDS1_10_A.test.cpp
• test/aoj_ALDS1_14_B_kmp.test.cpp
• test/aoj_ALDS1_14_B_l61m1.test.cpp
• test/aoj_ALDS1_14_B_z.test.cpp
• test/aoj_ALDS1_5_D.test.cpp
• test/aoj_DPL_1_D.test.cpp
• test/aoj_DPL_1_E.test.cpp
• test/aoj_DPL_5_A.test.cpp
• test/aoj_DPL_5_B.test.cpp
• test/aoj_DPL_5_C.test.cpp
• test/aoj_DPL_5_D.test.cpp
• test/aoj_DPL_5_E.test.cpp
• test/aoj_DPL_5_F.test.cpp
• test/aoj_DPL_5_G.test.cpp
• test/aoj_DPL_5_I.test.cpp
• test/aoj_DPL_5_J.test.cpp
• test/aoj_DPL_5_L.test.cpp
• test/aoj_DSL_1_A.test.cpp
• test/aoj_DSL_1_B.test.cpp
• test/aoj_DSL_2_A.test.cpp
• test/aoj_DSL_2_B.test.cpp
• test/aoj_DSL_2_G.test.cpp
• test/aoj_DSL_2_H.test.cpp
• test/aoj_DSL_2_I.test.cpp
• test/aoj_DSL_3_D.test.cpp
• test/aoj_GRL_5_C_segment_tree.test.cpp
• test/aoj_GRL_5_C_sparse_table.test.cpp
• test/aoj_GRL_5_C_squaring.test.cpp
• test/aoj_GRL_5_D.test.cpp
• test/aoj_GRL_5_E.test.cpp
• test/mini/fused_operations.test.cpp
• test/yc_1036.test.cpp
• test/yc_1036_disjoint_sparse_table.test.cpp
• test/yc_1036_sparse_table.test.cpp
• test/yc_3014.test.cpp
• test/yc_306.test.cpp
• test/yc_306_maximize.test.cpp
• test/yc_502.test.cpp
• test/yc_551.test.cpp
• test/yc_703_onoff.test.cpp
• test/yc_704_onoff.test.cpp
• test/yc_705_onoff.test.cpp
• test/yc_752.test.cpp
• test/yc_878.test.cpp
• test/yc_878_reversed.test.cpp
• test/yj_bipartitematching.test.cpp
• test/yj_convolution_mod.test.cpp
• test/yj_convolution_mod_1000000007.test.cpp
• test/yj_convolution_mod_raw.test.cpp
• test/yj_inv_of_formal_power_series.test.cpp
• test/yj_lca_squaring.test.cpp
• test/yj_line_add_get_min_li_chao_tree.test.cpp
• test/yj_log_of_formal_power_series.test.cpp
• test/yj_many_aplusb.test.cpp
• test/yj_multipoint_evaluation.test.cpp
• test/yj_persistent_unionfind_rollback.test.cpp
• test/yj_point_add_range_sum.test.cpp
• test/yj_point_set_range_composite.test.cpp
• test/yj_polynomial_interpolation.test.cpp
• test/yj_queue_operate_all_composite.test.cpp
• test/yj_range_affine_range_sum.test.cpp
• test/yj_range_kth_smallest.test.cpp
• test/yj_rectangle_sum.test.cpp
• test/yj_scc.test.cpp
• test/yj_segment_add_get_min.test.cpp
• test/yj_static_range_sum.test.cpp
• test/yj_staticrmq.test.cpp
• test/yj_suffixarray.test.cpp
• test/yj_two_sat.test.cpp
• test/yj_unionfind.test.cpp
• test/yj_vertex_add_path_sum.test.cpp
• test/yj_vertex_set_path_composite.test.cpp
• test/yj_zalgorithm.test.cpp