game/dyadic_rational.hpp

• View this file on GitHub
• Last update: 2026-08-29 09:24:19+09:00
• Include: #include "game/dyadic_rational.hpp"

Depends on

• other/bit.hpp

Required by

• game/number_and_star.hpp
• game/solve_partizan_game.hpp

Verified with

• test/1_mytest/dyadic_rational.test.cpp
• test/1_mytest/partizan.test.cpp

Code

#include "other/bit.hpp"

// a+b/2^M の形で持つ
template <typename INTEGER>
struct Dyadic_Rational {
  using X = Dyadic_Rational;
  INTEGER a, b;
  static constexpr int M = std::numeric_limits<INTEGER>::digits - 2;

  Dyadic_Rational(INTEGER a = 0) : a(a), b(0) {}

  // x + y / z
  Dyadic_Rational(INTEGER x, INTEGER y, INTEGER z) : a(x), b(y) {
    auto [q, r] = divmod(b, z);
    a += q;
    b = r;
    b *= (INTEGER(1) << M) / z;
  }

  // x/y
  Dyadic_Rational(INTEGER x, INTEGER y) : Dyadic_Rational(0, x, y) {}

  static X from_ab(INTEGER a, INTEGER b) {
    X x(a);
    x.b = b;
    return x;
  }

  // 比較
  bool operator==(X const& rhs) const { return (a == rhs.a && b == rhs.b); }
  bool operator!=(X const& rhs) const { return !(*this == rhs); }
  bool operator<(X const& rhs) const {
    return (a < rhs.a) || (a == rhs.a && b < rhs.b);
  }
  bool operator<=(X const& rhs) const {
    return (a < rhs.a) || (a == rhs.a && b <= rhs.b);
  }
  bool operator>(X const& rhs) const {
    return (a > rhs.a) || (a == rhs.a && b > rhs.b);
  }
  bool operator>=(X const& rhs) const {
    return (a > rhs.a) || (a == rhs.a && b >= rhs.b);
  }

  // 加法
  friend X operator+(const X& x, const X& y) {
    INTEGER a = x.a + y.a, b = x.b + y.b;
    while (b >= INTEGER(1) << M) {
      ++a;
      b -= INTEGER(1) << M;
    }
    return from_ab(a, b);
  }
  friend X operator-(const X& x, const X& y) {
    INTEGER a = x.a - y.a, b = x.b - y.b;
    while (b < 0) {
      --a;
      b += INTEGER(1) << M;
    }
    return from_ab(a, b);
  }
  friend X operator-(const X& x) {
    INTEGER a = -x.a, b = -x.b;
    while (b < 0) {
      --a;
      b += INTEGER(1) << M;
    }
    return from_ab(a, b);
  }
  X& operator+=(const X& x) { return (*this) = (*this) + x; }
  X& operator-=(const X& x) { return (*this) = (*this) - x; }

  static X simplest(X x, X y, bool include_x = false, bool include_y = false) {
    if (include_x && x != -infinity()) {
      // eps を引く, あとでもっと小さい eps を使っている !
      x = x - from_ab(0, 2);
    }
    if (include_y && y != infinity()) {
      // eps を足す
      y = y + from_ab(0, 2);
    }
    assert(x < y);
    if (y.a < 0) return -simplest(-y, -x);
    {
      INTEGER l = x.a + 1;
      INTEGER r = (y.b == 0 ? y.a - 1 : y.a);
      if (l <= 0 && 0 <= r) return X(0);
      if (l <= r && 0 <= l) return X(l);
      if (l <= r && r <= 0) return X(r);
    }

    INTEGER l = x.b + 1;
    INTEGER r = (y.b == 0 ? (INTEGER(1) << M) - 1 : y.b - 1);
    if (l == r) return from_ab(x.a, l);
    int k = topbit(l ^ r);
    r &= ~((INTEGER(1) << k) - 1);
    return from_ab(x.a, r);
  }

  static constexpr X infinity() { return from_ab(INTEGER(1) << M, 0); }

  string to_string() {
    ll x = a, y = b, z = INTEGER(1) << M;
    while (y % 2 == 0 && z % 2 == 0) {
      y /= 2, z /= 2;
    }
    y += x * z;
    return std::to_string(y) + "/" + std::to_string(z);
  }
};

#line 1 "other/bit.hpp"

int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
int popcnt_sgn(int x) { return (__builtin_parity(unsigned(x)) & 1 ? -1 : 1); }
int popcnt_sgn(u32 x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(ll x) { return (__builtin_parityll(x) & 1 ? -1 : 1); }
int popcnt_sgn(u64 x) { return (__builtin_parityll(x) & 1 ? -1 : 1); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }

template <typename T>
T kth_bit(int k) {
  assert(0 <= k && k < int(8 * sizeof(T)));
  return T(1) << k;
}
template <typename T>
bool has_kth_bit(T x, int k) {
  assert(0 <= k && k < int(8 * sizeof(T)));
  return x >> k & 1;
}

template <typename UINT>
struct all_bit {
  static_assert(is_unsigned<UINT>::value);
  UINT s;
  all_bit(UINT s) : s(s) {}
  struct iter {
    UINT s;
    int operator*() const { return lowbit(s); }
    void operator++() { s &= s - 1; }
    bool operator!=(nullptr_t) const { return s; }
  };
  iter begin() const { return {s}; }
  nullptr_t end() const { return nullptr; }
};

template <typename UINT>
struct all_subset {
  static_assert(is_unsigned<UINT>::value);
  UINT s;
  all_subset(UINT s) : s(s) {}
  struct iter {
    UINT s, t;
    bool done = false;
    UINT operator*() const { return t; }
    void operator++() {
      done = (t == 0);
      t = (t - 1) & s;
    }
    bool operator!=(nullptr_t) const { return !done; }
  };
  iter begin() const { return {s, s}; }
  nullptr_t end() const { return nullptr; }
};

constexpr u64 full_mask(int n) {
  assert(0 <= n && n <= 64);
  return n == 64 ? -1ULL : (1ULL << n) - 1;
}

u64 bit_reverse(u64 x) {
  x = ((x & 0x5555555555555555ULL) << 1) | ((x >> 1) & 0x5555555555555555ULL);
  x = ((x & 0x3333333333333333ULL) << 2) | ((x >> 2) & 0x3333333333333333ULL);
  x = ((x & 0x0f0f0f0f0f0f0f0fULL) << 4) | ((x >> 4) & 0x0f0f0f0f0f0f0f0fULL);
  x = ((x & 0x00ff00ff00ff00ffULL) << 8) | ((x >> 8) & 0x00ff00ff00ff00ffULL);
  x = ((x & 0x0000ffff0000ffffULL) << 16) | ((x >> 16) & 0x0000ffff0000ffffULL);
  x = (x << 32) | (x >> 32);
  return x;
}
#line 2 "game/dyadic_rational.hpp"

// a+b/2^M の形で持つ
template <typename INTEGER>
struct Dyadic_Rational {
  using X = Dyadic_Rational;
  INTEGER a, b;
  static constexpr int M = std::numeric_limits<INTEGER>::digits - 2;

  Dyadic_Rational(INTEGER a = 0) : a(a), b(0) {}

  // x + y / z
  Dyadic_Rational(INTEGER x, INTEGER y, INTEGER z) : a(x), b(y) {
    auto [q, r] = divmod(b, z);
    a += q;
    b = r;
    b *= (INTEGER(1) << M) / z;
  }

  // x/y
  Dyadic_Rational(INTEGER x, INTEGER y) : Dyadic_Rational(0, x, y) {}

  static X from_ab(INTEGER a, INTEGER b) {
    X x(a);
    x.b = b;
    return x;
  }

  // 比較
  bool operator==(X const& rhs) const { return (a == rhs.a && b == rhs.b); }
  bool operator!=(X const& rhs) const { return !(*this == rhs); }
  bool operator<(X const& rhs) const {
    return (a < rhs.a) || (a == rhs.a && b < rhs.b);
  }
  bool operator<=(X const& rhs) const {
    return (a < rhs.a) || (a == rhs.a && b <= rhs.b);
  }
  bool operator>(X const& rhs) const {
    return (a > rhs.a) || (a == rhs.a && b > rhs.b);
  }
  bool operator>=(X const& rhs) const {
    return (a > rhs.a) || (a == rhs.a && b >= rhs.b);
  }

  // 加法
  friend X operator+(const X& x, const X& y) {
    INTEGER a = x.a + y.a, b = x.b + y.b;
    while (b >= INTEGER(1) << M) {
      ++a;
      b -= INTEGER(1) << M;
    }
    return from_ab(a, b);
  }
  friend X operator-(const X& x, const X& y) {
    INTEGER a = x.a - y.a, b = x.b - y.b;
    while (b < 0) {
      --a;
      b += INTEGER(1) << M;
    }
    return from_ab(a, b);
  }
  friend X operator-(const X& x) {
    INTEGER a = -x.a, b = -x.b;
    while (b < 0) {
      --a;
      b += INTEGER(1) << M;
    }
    return from_ab(a, b);
  }
  X& operator+=(const X& x) { return (*this) = (*this) + x; }
  X& operator-=(const X& x) { return (*this) = (*this) - x; }

  static X simplest(X x, X y, bool include_x = false, bool include_y = false) {
    if (include_x && x != -infinity()) {
      // eps を引く, あとでもっと小さい eps を使っている !
      x = x - from_ab(0, 2);
    }
    if (include_y && y != infinity()) {
      // eps を足す
      y = y + from_ab(0, 2);
    }
    assert(x < y);
    if (y.a < 0) return -simplest(-y, -x);
    {
      INTEGER l = x.a + 1;
      INTEGER r = (y.b == 0 ? y.a - 1 : y.a);
      if (l <= 0 && 0 <= r) return X(0);
      if (l <= r && 0 <= l) return X(l);
      if (l <= r && r <= 0) return X(r);
    }

    INTEGER l = x.b + 1;
    INTEGER r = (y.b == 0 ? (INTEGER(1) << M) - 1 : y.b - 1);
    if (l == r) return from_ab(x.a, l);
    int k = topbit(l ^ r);
    r &= ~((INTEGER(1) << k) - 1);
    return from_ab(x.a, r);
  }

  static constexpr X infinity() { return from_ab(INTEGER(1) << M, 0); }

  string to_string() {
    ll x = a, y = b, z = INTEGER(1) << M;
    while (y % 2 == 0 && z % 2 == 0) {
      y /= 2, z /= 2;
    }
    y += x * z;
    return std::to_string(y) + "/" + std::to_string(z);
  }
};

Back to top page