半環ライブラリ
(math/semiring.hpp)

• View this file on GitHub
• Last update: 2021-01-01 23:05:31+09:00
• Include: #include "math/semiring.hpp"

半環ライブラリ

概要

半環(semiring, rig)とは集合$R$と二つの二項演算(加法$+$と乗法$\cdot$)からなる代数的構造である。$R,+,\cdot$は以下の関係を満たしている。

• $(R, +)$は$0$を単位元とする可換モノイドをなす
• $(R, \cdot)$は$1$を単位元とするモノイドをなす
• $+,\cdot$に対して分配法則が成り立つ
• $\forall r\in R$を$0$倍すると$0$になる

特にmax-plus半環/min-plus半環はトロピカル半環と呼ばれていて、グラフ上の最短経路の計算などに利用される。

テンプレート

• U: 集合$R$
• add: 二項演算$(R,+)$
• mul: 二項演算$(R,\cdot)$
• i0(): 単位元$0$
• i1(): 単位元$1$

// max-plus semiring
/**
using U = long long;
U add(U a, U b) { return max(a, b); }
U mul(U a, U b) { return a + b; }
U i0() { return -infLL; }
U i1() { return 0; }
using rig = semiring<U, add, mul, i0, i1>;
//*/

// min-plus semiring
/**
using U = long long;
U add(U a, U b) { return min(a, b); }
U mul(U a, U b) { return a + b; }
U i0() { return infLL; }
U i1() { return 0; }
using rig = semiring<U, add, mul, i0, i1>;
//*/

// max(x + a, b)
// verify: DDCC2020-final-b
/**
using U = pair<long long, long long>;
U add(U a, U b) {
  long long f = max(a.first, b.first);
  long long g = max(a.second, b.second);
  return U(f, g);
}
U mul(U a, U b) {
  long long f = a.first + b.first;
  long long g = max(a.second + b.first, b.second);
  return U(f, g);
}
U i0() { return U(-infLL, -infLL); }
U i1() { return U(0, -infLL); }
using rig = semiring<U, add, mul, i0, i1>;
//*/

// xor-and semiring
/**
using U = unsigned long long;
U add(U a, U b) { return a ^ b; }
U mul(U a, U b) { return a & b; }
U i0() { return 0; }
U i1() { return U(-1); }
using rig = semiring<U, add, mul, i0, i1>;
//*/

Verified with

• verify/verify-unit-test/semiring.test.cpp
• verify/verify-yuki/yuki-1340-semiring.test.cpp
• verify/verify-yuki/yuki-1460.test.cpp

Code

#pragma once

template <typename T, T (*add)(T, T), T (*mul)(T, T), T (*I0)(), T (*I1)()>
struct semiring {
  T x;
  semiring() : x(I0()) {}
  semiring(T y) : x(y) {}
  static T id0() { return I0(); }
  static T id1() { return I1(); }

  semiring &operator+=(const semiring &p) {
    if (x == I0()) return *this = p;
    if (p.x == I0()) return *this;
    return *this = add(x, p.x);
  }

  semiring &operator*=(const semiring &p) {
    if (x == I0() || p.x == I0()) return *this = I0();
    if (x == I1()) return *this = p;
    if (p.x == I1()) return *this;
    return *this = mul(x, p.x);
  }

  semiring operator+(const semiring &p) const { return semiring(*this) += p; }
  semiring operator*(const semiring &p) const { return semiring(*this) *= p; }
  bool operator==(const semiring &p) const { return x == p.x; }
  bool operator!=(const semiring &p) const { return x != p.x; }
  friend ostream &operator<<(ostream &os, const semiring &p) {
    return os << p.x;
  }
};

template <typename rig, int N>
struct Mat {
  using Array = array<array<rig, N>, N>;
  Array A;

  Mat() {
    for (int i = 0; i < N; i++) A[i].fill(rig::id0());
  }
  int height() const { return N; }
  int width() const { return N; }
  inline const array<rig, N> &operator[](int k) const { return A[k]; }
  inline array<rig, N> &operator[](int k) { return A[k]; }

  static Mat I() {
    Mat m;
    for (int i = 0; i < N; i++) m[i][i] = rig::id1();
    return m;
  }

  Mat &operator+=(const Mat &B) {
    for (int i = 0; i < N; i++)
      for (int j = 0; j < N; j++) A[i][j] += B[i][j];
    return (*this);
  }

  Mat &operator*=(const Mat &B) {
    Mat C;
    for (int i = 0; i < N; i++)
      for (int k = 0; k < N; k++)
        for (int j = 0; j < N; j++) C[i][j] += A[i][k] * B[k][j];
    A.swap(C.A);
    return (*this);
  }

  Mat &operator^=(long long k) {
    Mat B = Mat::I();
    for (; k; *this *= *this, k >>= 1)
      if (k & 1) B *= *this;
    A.swap(B.A);
    return (*this);
  }

  Mat operator+(const Mat &B) const { return (Mat(*this) += B); }
  Mat operator*(const Mat &B) const { return (Mat(*this) *= B); }
  Mat operator^(long long k) const { return (Mat(*this) ^= k); }

  friend ostream &operator<<(ostream &os, Mat &p) {
    for (int i = 0; i < N; i++) {
      os << "[";
      for (int j = 0; j < N; j++) {
        os << p[i][j].x << (j == N - 1 ? "]\n" : ",");
      }
    }
    return (os);
  }
};

/**
 * @brief 半環ライブラリ
 * @docs docs/math/semiring.md
 */

#line 2 "math/semiring.hpp"

template <typename T, T (*add)(T, T), T (*mul)(T, T), T (*I0)(), T (*I1)()>
struct semiring {
  T x;
  semiring() : x(I0()) {}
  semiring(T y) : x(y) {}
  static T id0() { return I0(); }
  static T id1() { return I1(); }

  semiring &operator+=(const semiring &p) {
    if (x == I0()) return *this = p;
    if (p.x == I0()) return *this;
    return *this = add(x, p.x);
  }

  semiring &operator*=(const semiring &p) {
    if (x == I0() || p.x == I0()) return *this = I0();
    if (x == I1()) return *this = p;
    if (p.x == I1()) return *this;
    return *this = mul(x, p.x);
  }

  semiring operator+(const semiring &p) const { return semiring(*this) += p; }
  semiring operator*(const semiring &p) const { return semiring(*this) *= p; }
  bool operator==(const semiring &p) const { return x == p.x; }
  bool operator!=(const semiring &p) const { return x != p.x; }
  friend ostream &operator<<(ostream &os, const semiring &p) {
    return os << p.x;
  }
};

template <typename rig, int N>
struct Mat {
  using Array = array<array<rig, N>, N>;
  Array A;

  Mat() {
    for (int i = 0; i < N; i++) A[i].fill(rig::id0());
  }
  int height() const { return N; }
  int width() const { return N; }
  inline const array<rig, N> &operator[](int k) const { return A[k]; }
  inline array<rig, N> &operator[](int k) { return A[k]; }

  static Mat I() {
    Mat m;
    for (int i = 0; i < N; i++) m[i][i] = rig::id1();
    return m;
  }

  Mat &operator+=(const Mat &B) {
    for (int i = 0; i < N; i++)
      for (int j = 0; j < N; j++) A[i][j] += B[i][j];
    return (*this);
  }

  Mat &operator*=(const Mat &B) {
    Mat C;
    for (int i = 0; i < N; i++)
      for (int k = 0; k < N; k++)
        for (int j = 0; j < N; j++) C[i][j] += A[i][k] * B[k][j];
    A.swap(C.A);
    return (*this);
  }

  Mat &operator^=(long long k) {
    Mat B = Mat::I();
    for (; k; *this *= *this, k >>= 1)
      if (k & 1) B *= *this;
    A.swap(B.A);
    return (*this);
  }

  Mat operator+(const Mat &B) const { return (Mat(*this) += B); }
  Mat operator*(const Mat &B) const { return (Mat(*this) *= B); }
  Mat operator^(long long k) const { return (Mat(*this) ^= k); }

  friend ostream &operator<<(ostream &os, Mat &p) {
    for (int i = 0; i < N; i++) {
      os << "[";
      for (int j = 0; j < N; j++) {
        os << p[i][j].x << (j == N - 1 ? "]\n" : ",");
      }
    }
    return (os);
  }
};

/**
 * @brief 半環ライブラリ
 * @docs docs/math/semiring.md
 */

Back to top page