library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub maspypy/library

:heavy_check_mark: nt/nimber/nimber_log.hpp

Depends on

Verified with

Code

#include "nt/nimber/base.hpp"
#include "ds/hashmap.hpp"
#include "mod/crt3.hpp"

// primitive root
const Nimber64 root_64 = u64(1) << 32 | 6;
const Nimber32 root_32 = 2147483651;
const Nimber16 root_16 = 41899;

u64 nimber_log(Nimber16 x) {
  assert(x != 0);
  u32 ans = u32(37991) * NIM_PRODUCT::L[x.val];
  return ans % 65535;
}

u64 nimber_log(Nimber32 x) {
  using F = Nimber32;
  assert(x != 0);
  static HashMap<u32> MP(330);
  static F g = 0;
  if (len(MP) == 0) {
    // build
    g = root_32.pow(65535); // 65537 乗根
    F gg = g.pow(200);
    F pow = 1;
    FOR(i, 330) MP[pow.val] = i, pow *= gg;
  }
  u64 a = [&]() -> u32 {
    F x1 = x.pow(65535);
    FOR(i, 200) {
      u32 k = MP.get(x1.val, -1);
      if (k != u32(-1)) { return (65537 + 200 * k - i) % 65537; }
      x1 *= g;
    }
    assert(0);
    return 0;
  }();
  u64 b = nimber_log(Nimber16(x.pow(65537).val));
  return CRT2<u64, 65535, 65537>(b, a);
}

u64 nimber_log(Nimber64 x) {
  using F = Nimber64;
  assert(x != 0);
  const u64 mod1 = u32(-1);
  const u64 mod2 = mod1 + 2;
  const u32 p1 = 641;
  const u32 p2 = 6700417;
  static HashMap<u32> MP1(3400);
  static HashMap<u32> MP2(641);
  static F g1, g2;
  if (len(MP1) == 0) {
    g1 = root_64.pow(mod1 * p1); // p2 乗根
    g2 = root_64.pow(mod1 * p2); // p1 乗根
    F gg = g1.pow(2000);
    F pow = 1;
    FOR(i, 3400) MP1[pow.val] = i, pow *= gg;
    pow = 1;
    FOR(i, 641) MP2[pow.val] = i, pow *= g2;
  }
  u64 a1 = [&]() -> u64 {
    F x1 = x.pow(mod1 * p1);
    FOR(i, 2000) {
      u32 k = MP1.get(x1.val, -1);
      if (k != u32(-1)) { return (p2 + 2000 * k - i) % p2; }
      x1 *= g1;
    }
    assert(0);
    return 0;
  }();
  u64 a2 = MP2[x.pow(mod1 * p2).val];
  u64 b = nimber_log(Nimber32(x.pow(mod2).val));
  u64 a = CRT2<u64, p1, p2>(a2, a1);
  u128 ans = u128(a) * (u64(-1) - mod1) + u128(b) * mod2;
  if (ans & 1) ans += u64(-1);
  return (ans / 2) % u64(-1);
}

// 最小解. ちょうど -1 を false の意味に使える.
template <typename F>
u64 nimber_log(F x, F y) {
  u64 X = nimber_log(x), Y = nimber_log(y);
  // X*n = Y mod (2^64-1)
  u64 mod = -1;
  u64 a = X, b = mod;
  i128 u = 1, v = 0, t;
  while (b > 0) {
    t = a / b;
    swap(a -= t * b, b), swap(u -= t * v, v);
  }
  if (Y % a != 0) return -1;
  if (u < 0) u += mod;
  return (Y / a) * u % (mod / a);
}
#line 2 "nt/nimber/nimber_impl.hpp"
namespace NIM_PRODUCT {
u16 E[65535 * 2 + 7];
u16 L[65536];
u64 S[4][65536];
u64 SR[4][65536];

u16 p16_15(u16 a, u16 b) { return (a && b ? E[u32(L[a]) + L[b] + 3] : 0); }
u16 p16_15_15(u16 a, u16 b) { return (a && b ? E[u32(L[a]) + L[b] + 6] : 0); }
u16 mul_15(u16 a) { return (a ? E[3 + L[a]] : 0); }
u16 mul_15_15(u16 a) { return (a ? E[6 + L[a]] : 0); }
u32 p32_mul_31(u32 a, u32 b) {
  u16 al = a & 65535, ah = a >> 16, bl = b & 65535, bh = b >> 16;
  u16 x = p16_15(al, bl);
  u16 y = p16_15_15(ah, bh);
  u16 z = p16_15(al ^ ah, bl ^ bh);
  return u32(y ^ z) << 16 | mul_15(z ^ x);
}
u32 mul_31(u32 a) {
  u16 al = a & 65535, ah = a >> 16;
  return u32(mul_15(al ^ ah)) << 16 | mul_15_15(ah);
}

u16 prod(u16 a, u16 b) { return (a && b ? E[u32(L[a]) + L[b]] : 0); }
u32 prod(u32 a, u32 b) {
  u16 al = a & 65535, ah = a >> 16, bl = b & 65535, bh = b >> 16;
  u16 c = prod(al, bl);
  return u32(prod(u16(al ^ ah), u16(bl ^ bh)) ^ c) << 16 | (p16_15(ah, bh) ^ c);
}
u64 prod(u64 a, u64 b) {
  u32 al = a & 0xffffffff, ah = a >> 32, bl = b & 0xffffffff, bh = b >> 32;
  u32 c = prod(al, bl);
  return u64(prod(al ^ ah, bl ^ bh) ^ c) << 32 ^ (p32_mul_31(ah, bh) ^ c);
}

u16 square(u16 a) { return S[0][a]; }
u32 square(u32 a) { return S[0][a & 65535] ^ S[1][a >> 16]; }
u64 square(u64 a) { return S[0][a & 65535] ^ S[1][a >> 16 & 65535] ^ S[2][a >> 32 & 65535] ^ S[3][a >> 48 & 65535]; }
u16 sqrt(u16 a) { return SR[0][a]; }
u32 sqrt(u32 a) { return SR[0][a & 65535] ^ SR[1][a >> 16]; }
u64 sqrt(u64 a) { return SR[0][a & 65535] ^ SR[1][a >> 16 & 65535] ^ SR[2][a >> 32 & 65535] ^ SR[3][a >> 48 & 65535]; }

// inv: 2^16 の共役が 2^16+1 であることなどを使う. x^{-1}=y(xy)^{-1} という要領.

u16 inverse(u16 a) { return E[65535 - L[a]]; }
u32 inverse(u32 a) {
  if (a < 65536) return inverse(u16(a));
  u16 al = a & 65535, ah = a >> 16;
  u16 norm = prod(al, al ^ ah) ^ E[L[ah] * 2 + 3];
  int k = 65535 - L[norm];
  al = (al ^ ah ? E[L[al ^ ah] + k] : 0), ah = E[L[ah] + k];
  return al | u32(ah) << 16;
}
u64 inverse(u64 a) {
  if (a <= u32(-1)) return inverse(u32(a));
  u32 al = a & 0xffffffff, ah = a >> 32;
  u32 norm = prod(al, al ^ ah) ^ mul_31(square(ah));
  u32 i = inverse(norm);
  return prod(al ^ ah, i) | u64(prod(ah, i)) << 32;
}

void __attribute__((constructor)) init_nim_table() {
  // 2^16 未満のところについて原始根 10279 での指数対数表を作る

  // 2^k との積

  u16 tmp[] = {10279, 15417, 35722, 52687, 44124, 62628, 15661, 5686, 3862, 1323, 334, 647, 61560, 20636, 4267, 8445};
  u16 nxt[65536];
  FOR(i, 16) {
    FOR(s, 1 << i) { nxt[s | 1 << i] = nxt[s] ^ tmp[i]; }
  }
  E[0] = 1;
  FOR(i, 65534) E[i + 1] = nxt[E[i]];
  memcpy(E + 65535, E, 131070);
  memcpy(E + 131070, E, 14);
  FOR(i, 65535) L[E[i]] = i;
  FOR(t, 4) {
    FOR(i, 16) {
      int k = 16 * t + i;
      u64 X = prod(u64(1) << k, u64(1) << k);
      FOR(s, 1 << i) S[t][s | 1 << i] = S[t][s] ^ X;
    }
  }
  FOR(t, 4) {
    FOR(i, 16) {
      int k = 16 * t + i;
      u64 X = u64(1) << k;
      FOR(63) X = square(X);
      FOR(s, 1 << i) SR[t][s | 1 << i] = SR[t][s] ^ X;
    }
  }
}
} // namespace NIM_PRODUCT

#line 3 "nt/nimber/base.hpp"

template <typename UINT>
struct Nimber {
  using F = Nimber;
  UINT val;

  constexpr Nimber(UINT x = 0) : val(x) {}
  F &operator+=(const F &p) {
    val ^= p.val;
    return *this;
  }
  F &operator-=(const F &p) {
    val ^= p.val;
    return *this;
  }
  F &operator*=(const F &p) {
    val = NIM_PRODUCT::prod(val, p.val);
    return *this;
  }
  F &operator/=(const F &p) {
    *this *= p.inverse();
    return *this;
  }
  F operator-() const { return *this; }
  F operator+(const F &p) const { return F(*this) += p; }
  F operator-(const F &p) const { return F(*this) -= p; }
  F operator*(const F &p) const { return F(*this) *= p; }
  F operator/(const F &p) const { return F(*this) /= p; }
  bool operator==(const F &p) const { return val == p.val; }
  bool operator!=(const F &p) const { return val != p.val; }
  F inverse() const { return NIM_PRODUCT::inverse(val); }
  F pow(u64 n) const {
    assert(n >= 0);
    UINT ret = 1, mul = val;
    while (n > 0) {
      if (n & 1) ret = NIM_PRODUCT::prod(ret, mul);
      mul = NIM_PRODUCT::square(mul);
      n >>= 1;
    }
    return F(ret);
  }
  F square() { return F(NIM_PRODUCT::square(val)); }
  F sqrt() { return F(NIM_PRODUCT::sqrt(val)); }
};

#ifdef FASTIO
template <typename T>
void rd(Nimber<T> &x) {
  fastio::rd(x.val);
}
template <typename T>
void wt(Nimber<T> &x) {
  fastio::wt(x.val);
}
#endif

using Nimber16 = Nimber<u16>;
using Nimber32 = Nimber<u32>;
using Nimber64 = Nimber<u64>;
#line 2 "ds/hashmap.hpp"

// u64 -> Val

template <typename Val>
struct HashMap {
  // n は入れたいものの個数で ok

  HashMap(u32 n = 0) { build(n); }
  void build(u32 n) {
    u32 k = 8;
    while (k < n * 2) k *= 2;
    cap = k / 2, mask = k - 1;
    key.resize(k), val.resize(k), used.assign(k, 0);
  }

  // size を保ったまま. size=0 にするときは build すること.

  void clear() {
    used.assign(len(used), 0);
    cap = (mask + 1) / 2;
  }
  int size() { return len(used) / 2 - cap; }

  int index(const u64& k) {
    int i = 0;
    for (i = hash(k); used[i] && key[i] != k; i = (i + 1) & mask) {}
    return i;
  }

  Val& operator[](const u64& k) {
    if (cap == 0) extend();
    int i = index(k);
    if (!used[i]) { used[i] = 1, key[i] = k, val[i] = Val{}, --cap; }
    return val[i];
  }

  Val get(const u64& k, Val default_value) {
    int i = index(k);
    return (used[i] ? val[i] : default_value);
  }

  bool count(const u64& k) {
    int i = index(k);
    return used[i] && key[i] == k;
  }

  // f(key, val)

  template <typename F>
  void enumerate_all(F f) {
    FOR(i, len(used)) if (used[i]) f(key[i], val[i]);
  }

private:
  u32 cap, mask;
  vc<u64> key;
  vc<Val> val;
  vc<bool> used;

  u64 hash(u64 x) {
    static const u64 FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
    x += FIXED_RANDOM;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return (x ^ (x >> 31)) & mask;
  }

  void extend() {
    vc<pair<u64, Val>> dat;
    dat.reserve(len(used) / 2 - cap);
    FOR(i, len(used)) {
      if (used[i]) dat.eb(key[i], val[i]);
    }
    build(2 * len(dat));
    for (auto& [a, b]: dat) (*this)[a] = b;
  }
};
#line 2 "mod/crt3.hpp"

constexpr u32 mod_pow_constexpr(u64 a, u64 n, u32 mod) {
  a %= mod;
  u64 res = 1;
  FOR(32) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod, n /= 2;
  }
  return res;
}

template <typename T, u32 p0, u32 p1>
T CRT2(u64 a0, u64 a1) {
  static_assert(p0 < p1);
  static constexpr u64 x0_1 = mod_pow_constexpr(p0, p1 - 2, p1);
  u64 c = (a1 - a0 + p1) * x0_1 % p1;
  return a0 + c * p0;
}

template <typename T, u32 p0, u32 p1, u32 p2>
T CRT3(u64 a0, u64 a1, u64 a2) {
  static_assert(p0 < p1 && p1 < p2);
  static constexpr u64 x1 = mod_pow_constexpr(p0, p1 - 2, p1);
  static constexpr u64 x2 = mod_pow_constexpr(u64(p0) * p1 % p2, p2 - 2, p2);
  static constexpr u64 p01 = u64(p0) * p1;
  u64 c = (a1 - a0 + p1) * x1 % p1;
  u64 ans_1 = a0 + c * p0;
  c = (a2 - ans_1 % p2 + p2) * x2 % p2;
  return T(ans_1) + T(c) * T(p01);
}

template <typename T, u32 p0, u32 p1, u32 p2, u32 p3>
T CRT4(u64 a0, u64 a1, u64 a2, u64 a3) {
  static_assert(p0 < p1 && p1 < p2 && p2 < p3);
  static constexpr u64 x1 = mod_pow_constexpr(p0, p1 - 2, p1);
  static constexpr u64 x2 = mod_pow_constexpr(u64(p0) * p1 % p2, p2 - 2, p2);
  static constexpr u64 x3 = mod_pow_constexpr(u64(p0) * p1 % p3 * p2 % p3, p3 - 2, p3);
  static constexpr u64 p01 = u64(p0) * p1;
  u64 c = (a1 - a0 + p1) * x1 % p1;
  u64 ans_1 = a0 + c * p0;
  c = (a2 - ans_1 % p2 + p2) * x2 % p2;
  u128 ans_2 = ans_1 + c * static_cast<u128>(p01);
  c = (a3 - ans_2 % p3 + p3) * x3 % p3;
  return T(ans_2) + T(c) * T(p01) * T(p2);
}

template <typename T, u32 p0, u32 p1, u32 p2, u32 p3, u32 p4>
T CRT5(u64 a0, u64 a1, u64 a2, u64 a3, u64 a4) {
  static_assert(p0 < p1 && p1 < p2 && p2 < p3 && p3 < p4);
  static constexpr u64 x1 = mod_pow_constexpr(p0, p1 - 2, p1);
  static constexpr u64 x2 = mod_pow_constexpr(u64(p0) * p1 % p2, p2 - 2, p2);
  static constexpr u64 x3 = mod_pow_constexpr(u64(p0) * p1 % p3 * p2 % p3, p3 - 2, p3);
  static constexpr u64 x4 = mod_pow_constexpr(u64(p0) * p1 % p4 * p2 % p4 * p3 % p4, p4 - 2, p4);
  static constexpr u64 p01 = u64(p0) * p1;
  static constexpr u64 p23 = u64(p2) * p3;
  u64 c = (a1 - a0 + p1) * x1 % p1;
  u64 ans_1 = a0 + c * p0;
  c = (a2 - ans_1 % p2 + p2) * x2 % p2;
  u128 ans_2 = ans_1 + c * static_cast<u128>(p01);
  c = static_cast<u64>(a3 - ans_2 % p3 + p3) * x3 % p3;
  u128 ans_3 = ans_2 + static_cast<u128>(c * p2) * p01;
  c = static_cast<u64>(a4 - ans_3 % p4 + p4) * x4 % p4;
  return T(ans_3) + T(c) * T(p01) * T(p23);
}
#line 4 "nt/nimber/nimber_log.hpp"

// primitive root
const Nimber64 root_64 = u64(1) << 32 | 6;
const Nimber32 root_32 = 2147483651;
const Nimber16 root_16 = 41899;

u64 nimber_log(Nimber16 x) {
  assert(x != 0);
  u32 ans = u32(37991) * NIM_PRODUCT::L[x.val];
  return ans % 65535;
}

u64 nimber_log(Nimber32 x) {
  using F = Nimber32;
  assert(x != 0);
  static HashMap<u32> MP(330);
  static F g = 0;
  if (len(MP) == 0) {
    // build
    g = root_32.pow(65535); // 65537 乗根
    F gg = g.pow(200);
    F pow = 1;
    FOR(i, 330) MP[pow.val] = i, pow *= gg;
  }
  u64 a = [&]() -> u32 {
    F x1 = x.pow(65535);
    FOR(i, 200) {
      u32 k = MP.get(x1.val, -1);
      if (k != u32(-1)) { return (65537 + 200 * k - i) % 65537; }
      x1 *= g;
    }
    assert(0);
    return 0;
  }();
  u64 b = nimber_log(Nimber16(x.pow(65537).val));
  return CRT2<u64, 65535, 65537>(b, a);
}

u64 nimber_log(Nimber64 x) {
  using F = Nimber64;
  assert(x != 0);
  const u64 mod1 = u32(-1);
  const u64 mod2 = mod1 + 2;
  const u32 p1 = 641;
  const u32 p2 = 6700417;
  static HashMap<u32> MP1(3400);
  static HashMap<u32> MP2(641);
  static F g1, g2;
  if (len(MP1) == 0) {
    g1 = root_64.pow(mod1 * p1); // p2 乗根
    g2 = root_64.pow(mod1 * p2); // p1 乗根
    F gg = g1.pow(2000);
    F pow = 1;
    FOR(i, 3400) MP1[pow.val] = i, pow *= gg;
    pow = 1;
    FOR(i, 641) MP2[pow.val] = i, pow *= g2;
  }
  u64 a1 = [&]() -> u64 {
    F x1 = x.pow(mod1 * p1);
    FOR(i, 2000) {
      u32 k = MP1.get(x1.val, -1);
      if (k != u32(-1)) { return (p2 + 2000 * k - i) % p2; }
      x1 *= g1;
    }
    assert(0);
    return 0;
  }();
  u64 a2 = MP2[x.pow(mod1 * p2).val];
  u64 b = nimber_log(Nimber32(x.pow(mod2).val));
  u64 a = CRT2<u64, p1, p2>(a2, a1);
  u128 ans = u128(a) * (u64(-1) - mod1) + u128(b) * mod2;
  if (ans & 1) ans += u64(-1);
  return (ans / 2) % u64(-1);
}

// 最小解. ちょうど -1 を false の意味に使える.
template <typename F>
u64 nimber_log(F x, F y) {
  u64 X = nimber_log(x), Y = nimber_log(y);
  // X*n = Y mod (2^64-1)
  u64 mod = -1;
  u64 a = X, b = mod;
  i128 u = 1, v = 0, t;
  while (b > 0) {
    t = a / b;
    swap(a -= t * b, b), swap(u -= t * v, v);
  }
  if (Y % a != 0) return -1;
  if (u < 0) u += mod;
  return (Y / a) * u % (mod / a);
}
Back to top page