algebraic-structure/group.hpp

View this file on GitHub
Last update: 2026-06-28 15:32:36+09:00
Include: #include "algebraic-structure/group.hpp"

Depends on

Required by

Verified with

verify/union-find/LC_unionfind_with_potential.test.cpp

Code

#pragma once
#include "algebraic-structure/monoid.hpp"

#ifdef __cpp_concepts
template <class G>
concept Group = Monoid<G> && requires(typename G::value_type x) {
  { G::inv(x) } -> same_as<typename G::value_type>;
};
#endif

template <class T>
struct AddGroup {
  using value_type = T;
  static T op(T x, T y) { return x + y; }
  static T e() { return T(0); }
  static T inv(T x) { return -x; }
};
template <class T>
struct MulGroup {
  using value_type = T;
  static T op(T x, T y) { return x * y; }
  static T e() { return T(1); }
  static T inv(T x) { return T(1) / x; }
};

#line 2 "algebraic-structure/util.hpp"
#ifdef __cpp_concepts
#define REQUIRES(...) requires __VA_ARGS__
#else
#define REQUIRES(...)
#endif
#line 3 "algebraic-structure/magma.hpp"

#ifdef __cpp_concepts
template <class M>
concept Magma = requires(typename M::value_type x, typename M::value_type y) {
  typename M::value_type;
  { M::op(x, y) } -> same_as<typename M::value_type>;
};
#endif

template <class T>
struct AddMagma {
  using value_type = T;
  static T op(T x, T y) { return x + y; }
};
template <class T>
struct MulMagma {
  using value_type = T;
  static T op(T x, T y) { return x * y; }
};
template <class T, T id>
struct MaxMagma {
  using value_type = T;
  static T op(T x, T y) { return x > y ? x : y; }
};
template <class T, T id>
struct MinMagma {
  using value_type = T;
  static T op(T x, T y) { return x < y ? x : y; }
};
#line 3 "algebraic-structure/monoid.hpp"

#ifdef __cpp_concepts
template <class M>
concept Monoid = Magma<M> && requires {
  { M::e() } -> same_as<typename M::value_type>;
};
#endif

template <class T>
struct AddMonoid {
  using value_type = T;
  static T op(T x, T y) { return x + y; }
  static T e() { return T(0); }
};
template <class T>
struct MulMonoid {
  using value_type = T;
  static T op(T x, T y) { return x * y; }
  static T e() { return T(1); }
};
template <class T, T id>
struct MaxMonoid {
  using value_type = T;
  static T op(T x, T y) { return x > y ? x : y; }
  static T e() { return id; }
};
template <class T, T id>
struct MinMonoid {
  using value_type = T;
  static T op(T x, T y) { return x < y ? x : y; }
  static T e() { return id; }
};
#line 3 "algebraic-structure/group.hpp"

#ifdef __cpp_concepts
template <class G>
concept Group = Monoid<G> && requires(typename G::value_type x) {
  { G::inv(x) } -> same_as<typename G::value_type>;
};
#endif

template <class T>
struct AddGroup {
  using value_type = T;
  static T op(T x, T y) { return x + y; }
  static T e() { return T(0); }
  static T inv(T x) { return -x; }
};
template <class T>
struct MulGroup {
  using value_type = T;
  static T op(T x, T y) { return x * y; }
  static T e() { return T(1); }
  static T inv(T x) { return T(1) / x; }
};