additive_group

コンセプト · ポテンシャル付き素集合データ構造（可換・非可換どちらの群でも可）

template <class T>
concept additive_group = requires(const T &a) {
    T(0);
    { a + a } -> std::convertible_to<T>;
    { -a } -> std::convertible_to<T>;
};

概要

加法的に書かれた可換群か（合成 +・逆元 単項 -・単位元 T(0)）

int や modint など +/- を持つ型はこちらで扱う。 modint のように */inv() も持つ環型でも、ポテンシャル差は加法とみなす （T(0) を単位元とする）ため加法群を優先する。

計算量

• コンパイル時の型制約のため実行時コストなし

関連項目

• multiplicative_group — 乗法的に書かれた群か（合成 *・逆元 .inv()・単位元 T()）
• group_identity — 群 T の単位元
• group_op — 群 T の二項演算 a・b
• group_inv — 群 T の逆元 $a^{-1}$
• group — potentialized_union_find が扱える群
• potentialized_union_find — ポテンシャル付き素集合データ構造（可換・非可換どちらの群でも可）