game/number_and_star.hpp

• View this file on GitHub
• Last update: 2026-08-19 06:34:57+09:00
• Include: #include "game/number_and_star.hpp"

Depends on

• game/dyadic_rational.hpp
• other/bit.hpp
• other/mex.hpp

Required by

• game/solve_partizan_game.hpp

Verified with

• test/1_mytest/partizan.test.cpp

Code

#include "game/dyadic_rational.hpp"
#include "other/mex.hpp"

struct Number_And_Star {
  using A = Dyadic_Rational<ll>;
  // a + *b
  A a;
  int b;
  using T = Number_And_Star;

  Number_And_Star(A a = 0, ll b = 0) : a(a), b(b) {}
  T& operator+=(const T& p) {
    a += p.a, b ^= p.b;
    return *this;
  }
  T& operator-=(const T& p) {
    a -= p.a, b ^= p.b;
    return *this;
  }
  T operator-() const { return T(-a, b); }
  bool operator==(const T& p) const { return (a == p.a && b == p.b); }

  // {計算できたか, 値}
  static pair<bool, T> from_options(vc<T> left_ops, vc<T> right_ops) {
    A xl = -A::infinity(), xr = A::infinity();
    vc<int> Lb, Rb;
    for (auto&& t: left_ops) {
      if (chmax(xl, t.a)) Lb.clear();
      if (xl == t.a) Lb.eb(t.b);
    }
    for (auto&& t: right_ops) {
      if (chmin(xr, t.a)) Rb.clear();
      if (xr == t.a) Rb.eb(t.b);
    }
    int Lm = mex(Lb), Rm = mex(Rb);
    if (xl < xr) {
      A a = A::simplest(xl, xr, Lm == 0, Rm == 0);
      return {true, T(a, 0)};
    }
    if (xl == xr) {
      if (Lm == Rm) return {true, T(xl, Lm)};
    }
    return {false, T(0, 0)};
  }

  string to_string() {
    string x = a.to_string();
    x += " + *";
    x += ::to_string(b);
    return x;
  }

  // L, R はそれぞれ自分手番のときに勝てるか？
  pair<bool, bool> outcome() {
    if (a > 0) return {1, 0};
    if (a < 0) return {0, 1};
    if (b == 0) return {0, 0};
    return {1, 1};
  }
};

#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) {
  return T(1) << k;
}
template <typename T>
bool has_kth_bit(T x, int k) {
  return x >> k & 1;
}

template <typename UINT>
struct all_bit {
  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 {
  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) { 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);
  }
};
#line 1 "other/mex.hpp"
int mex(const vc<int>& A) {
  int n = len(A);
  vc<bool> aru(n + 1);
  for (auto& x: A)
    if (x < n) aru[x] = 1;
  int mex = 0;
  while (aru[mex]) ++mex;
  return mex;
}
#line 3 "game/number_and_star.hpp"

struct Number_And_Star {
  using A = Dyadic_Rational<ll>;
  // a + *b
  A a;
  int b;
  using T = Number_And_Star;

  Number_And_Star(A a = 0, ll b = 0) : a(a), b(b) {}
  T& operator+=(const T& p) {
    a += p.a, b ^= p.b;
    return *this;
  }
  T& operator-=(const T& p) {
    a -= p.a, b ^= p.b;
    return *this;
  }
  T operator-() const { return T(-a, b); }
  bool operator==(const T& p) const { return (a == p.a && b == p.b); }

  // {計算できたか, 値}
  static pair<bool, T> from_options(vc<T> left_ops, vc<T> right_ops) {
    A xl = -A::infinity(), xr = A::infinity();
    vc<int> Lb, Rb;
    for (auto&& t: left_ops) {
      if (chmax(xl, t.a)) Lb.clear();
      if (xl == t.a) Lb.eb(t.b);
    }
    for (auto&& t: right_ops) {
      if (chmin(xr, t.a)) Rb.clear();
      if (xr == t.a) Rb.eb(t.b);
    }
    int Lm = mex(Lb), Rm = mex(Rb);
    if (xl < xr) {
      A a = A::simplest(xl, xr, Lm == 0, Rm == 0);
      return {true, T(a, 0)};
    }
    if (xl == xr) {
      if (Lm == Rm) return {true, T(xl, Lm)};
    }
    return {false, T(0, 0)};
  }

  string to_string() {
    string x = a.to_string();
    x += " + *";
    x += ::to_string(b);
    return x;
  }

  // L, R はそれぞれ自分手番のときに勝てるか？
  pair<bool, bool> outcome() {
    if (a > 0) return {1, 0};
    if (a < 0) return {0, 1};
    if (b == 0) return {0, 0};
    return {1, 1};
  }
};

Back to top page