代数的構造 (src/Math/Algebra.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-09-21 22:51:54+09:00
• Include: #include "src/Math/Algebra.hpp"

群の演算をoperator+やoperator-にしてBITやポテンシャルUFに乗せたり，半環にして行列に乗せたりするために用意した．

struct M{
  using T = int;
  static inline T o = 0;
  static inline T i = 1;
  static T add(T a,T b){return a+b;}
  static T neg(T a){return -a;}
  static T mul(T a,T b){return a*b;}
};

Verify

• AtCoder Beginner Contest 009 D - 漸化式 (bitwise xor and 半環)
  
• DISCO presents ディスカバリーチャンネル コードコンテスト2020 本戦 B - Hawker on Graph (max+の一次関数の加法合成の半環)
  
• 競プロ典型 90 問　068 - Paired Information（★5） (affine, 非可換群)

Depends on

• detection idiom (src/Internal/detection_idiom.hpp)

Verified with

• test/atcoder/abc236_g.test.cpp
• test/sample_test/abc009_4.test.cpp
• test/sample_test/ddcc2020_final_b.test.cpp
• test/sample_test/typical90_bp.test.cpp
• test/sample_test/typical90_bp.UFPU.test.cpp
• test/yosupo/unionfind_with_potential_non_commutative_group.test.cpp
• test/yosupo/unionfind_with_potential_non_commutative_group.UFPU.test.cpp
• test/yukicoder/1340.test.cpp
• test/yukicoder/1502.test.cpp
• test/yukicoder/1502.UFPU.test.cpp

Code

#pragma once
#include "src/Internal/detection_idiom.hpp"
template <class M> struct Algebra {
 using T= typename M::T;
 _DETECT_BOOL(has_zero, decltype(T::o));
 _DETECT_BOOL(has_one, decltype(T::i));
 static inline T zero= has_zero_v<M> ? M::o : T();
 static inline T one= has_one_v<M> ? M::i : T();
 T x;
 Algebra(): x(zero) {}
 Algebra(bool y): x(y ? one : zero) {}
 template <class U, typename= std::enable_if_t<std::is_convertible_v<U, T>>> Algebra(U y): x(y) {}
 Algebra &operator+=(const Algebra &r) { return *this= *this + r; }
 Algebra &operator-=(const Algebra &r) { return *this= *this - r; }
 Algebra &operator*=(const Algebra &r) { return *this= *this * r; }
 Algebra operator+(const Algebra &r) const { return Algebra(M::add(x, r.x)); }
 Algebra operator-(const Algebra &r) const { return Algebra(M::add(x, M::neg(r.x))); }
 Algebra operator*(const Algebra &r) const { return Algebra(M::mul(x, r.x)); }
 Algebra operator-() const { return Algebra(M::neg(x)); }
 bool operator==(const Algebra &r) const { return x == r.x; }
 bool operator!=(const Algebra &r) const { return x != r.x; }
 friend std::istream &operator>>(std::istream &is, Algebra &r) { return is >> r.x, is; }
 friend std::ostream &operator<<(std::ostream &os, const Algebra &r) { return os << r.x; }
};

#line 2 "src/Internal/detection_idiom.hpp"
#include <type_traits>
#define _DETECT_BOOL(name, ...) \
 template <class, class= void> struct name: std::false_type {}; \
 template <class T> struct name<T, std::void_t<__VA_ARGS__>>: std::true_type {}; \
 template <class T> static constexpr bool name##_v= name<T>::value
#define _DETECT_TYPE(name, type1, type2, ...) \
 template <class T, class= void> struct name { \
  using type= type2; \
 }; \
 template <class T> struct name<T, std::void_t<__VA_ARGS__>> { \
  using type= type1; \
 }
#line 3 "src/Math/Algebra.hpp"
template <class M> struct Algebra {
 using T= typename M::T;
 _DETECT_BOOL(has_zero, decltype(T::o));
 _DETECT_BOOL(has_one, decltype(T::i));
 static inline T zero= has_zero_v<M> ? M::o : T();
 static inline T one= has_one_v<M> ? M::i : T();
 T x;
 Algebra(): x(zero) {}
 Algebra(bool y): x(y ? one : zero) {}
 template <class U, typename= std::enable_if_t<std::is_convertible_v<U, T>>> Algebra(U y): x(y) {}
 Algebra &operator+=(const Algebra &r) { return *this= *this + r; }
 Algebra &operator-=(const Algebra &r) { return *this= *this - r; }
 Algebra &operator*=(const Algebra &r) { return *this= *this * r; }
 Algebra operator+(const Algebra &r) const { return Algebra(M::add(x, r.x)); }
 Algebra operator-(const Algebra &r) const { return Algebra(M::add(x, M::neg(r.x))); }
 Algebra operator*(const Algebra &r) const { return Algebra(M::mul(x, r.x)); }
 Algebra operator-() const { return Algebra(M::neg(x)); }
 bool operator==(const Algebra &r) const { return x == r.x; }
 bool operator!=(const Algebra &r) const { return x != r.x; }
 friend std::istream &operator>>(std::istream &is, Algebra &r) { return is >> r.x, is; }
 friend std::ostream &operator<<(std::ostream &os, const Algebra &r) { return os << r.x; }
};

Back to top page