nim_product.hpp

SECTIONMath INCLUDEnoya/nim_product.hpp

计算 64 位 nimber 的 nim 乘法；用于 Sprague–Grundy 值落在 nim 域乘法结构的博弈题。

\[ \displaystyle a \otimes b \]

Complexity: Time: O(64) per product after O(2^22) preprocessing. Space: O(2^25) bytes (32 MiB).

AC 记录：nim_product_64。

跳到代码 · GitHub ↗

Implementation

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(64) per product after O(2^22) preprocessing.
/// Space: O(2^25) bytes (32 MiB).

#include <array>
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <vector>

namespace noya {

namespace nim_product_internal {

using u64 = std::uint64_t;

inline u64 recursive_product(u64 a, u64 b, int lg) {
  assert(lg >= 1 && lg <= 64 && (lg & (lg - 1)) == 0);
  if (a == 0 || b == 0) {
    return 0;
  }
  if (a == 1) {
    return b;
  }
  if (b == 1) {
    return a;
  }
  if (lg == 1) {
    return a & b;
  }

  int hal = lg / 2;
  u64 mas = (u64(1) << hal) - 1;
  u64 al = a & mas;
  u64 ah = a >> hal;
  u64 bl = b & mas;
  u64 bh = b >> hal;

  u64 ll = recursive_product(al, bl, hal);
  u64 hh = recursive_product(ah, bh, hal);
  u64 com = recursive_product(al ^ ah, bl ^ bh, hal);
  u64 cro = com ^ ll ^ hh;
  u64 red = recursive_product(hh, u64(1) << (hal - 1), hal);
  return (ll ^ red) ^ ((cro ^ hh) << hal);
}

inline const std::vector<u64> &byte_table() {
  static const std::vector<u64> tbl = [] {
    std::array<std::array<u64, 64>, 64> bas{};
    for (int a = 0; a < 64; a++) {
      for (int b = a; b < 64; b++) {
        u64 val = recursive_product(u64(1) << a, u64(1) << b, 64);
        bas[a][b] = bas[b][a] = val;
      }
    }

    std::vector<u64> res(std::size_t(8) * 8 * 256 * 256);
    std::array<std::array<u64, 8>, 256> rc{};
    for (int ba = 0; ba < 8; ba++) {
      for (int bb = 0; bb < 8; bb++) {
        rc = {};
        for (unsigned mas = 1; mas < 256; mas++) {
          unsigned bit = std::countr_zero(mas);
          unsigned pre = mas & (mas - 1);
          for (int sb = 0; sb < 8; sb++) {
            rc[mas][sb] = rc[pre][sb] ^ bas[ba * 8 + int(bit)][bb * 8 + sb];
          }
        }
        std::size_t blk = std::size_t(ba * 8 + bb) << 16;
        for (unsigned va = 0; va < 256; va++) {
          for (unsigned vb = 1; vb < 256; vb++) {
            unsigned bit = std::countr_zero(vb);
            unsigned pre = vb & (vb - 1);
            res[blk | (std::size_t(va) << 8) | vb] =
                res[blk | (std::size_t(va) << 8) | pre] ^ rc[va][bit];
          }
        }
      }
    }
    return res;
  }();
  return tbl;
}

} // namespace nim_product_internal

/// @brief Compute the 64-bit nim product. Nimbers with twice as many bits form
/// a quadratic extension of the lower field: for alpha=2^m,
/// alpha^2=alpha xor 2^(m-1). Recursing on this identity generates all products
/// of binary basis elements. Bilinearity then groups eight basis elements at a
/// time into a 32 MiB byte-pair table, so one query needs 8*8 lookups and XORs.
inline std::uint64_t nim_product(std::uint64_t a, std::uint64_t b) {
  const std::vector<std::uint64_t> &tbl = nim_product_internal::byte_table();
  std::uint64_t res = 0;
  for (int ba = 0; ba < 8; ba++) {
    unsigned va = unsigned(a >> (ba * 8)) & 255;
    for (int bb = 0; bb < 8; bb++) {
      unsigned vb = unsigned(b >> (bb * 8)) & 255;
      std::size_t idx =
          (std::size_t(ba * 8 + bb) << 16) | (std::size_t(va) << 8) | vb;
      res ^= tbl[idx];
    }
  }
  return res;
}

} // namespace noya

#ifndef NOYA_NIM_PRODUCT_HPP
#define NOYA_NIM_PRODUCT_HPP 1

/// @complexity Time: O(64) per product after O(2^22) preprocessing.
/// Space: O(2^25) bytes (32 MiB).

#include <array>
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <vector>

namespace noya {

namespace nim_product_internal {

using u64 = std::uint64_t;

inline u64 recursive_product(u64 a, u64 b, int lg) {
  assert(lg >= 1 && lg <= 64 && (lg & (lg - 1)) == 0);
  if (a == 0 || b == 0) {
    return 0;
  }
  if (a == 1) {
    return b;
  }
  if (b == 1) {
    return a;
  }
  if (lg == 1) {
    return a & b;
  }

  int hal = lg / 2;
  u64 mas = (u64(1) << hal) - 1;
  u64 al = a & mas;
  u64 ah = a >> hal;
  u64 bl = b & mas;
  u64 bh = b >> hal;

  u64 ll = recursive_product(al, bl, hal);
  u64 hh = recursive_product(ah, bh, hal);
  u64 com = recursive_product(al ^ ah, bl ^ bh, hal);
  u64 cro = com ^ ll ^ hh;
  u64 red = recursive_product(hh, u64(1) << (hal - 1), hal);
  return (ll ^ red) ^ ((cro ^ hh) << hal);
}

inline const std::vector<u64> &byte_table() {
  static const std::vector<u64> tbl = [] {
    std::array<std::array<u64, 64>, 64> bas{};
    for (int a = 0; a < 64; a++) {
      for (int b = a; b < 64; b++) {
        u64 val = recursive_product(u64(1) << a, u64(1) << b, 64);
        bas[a][b] = bas[b][a] = val;
      }
    }

    std::vector<u64> res(std::size_t(8) * 8 * 256 * 256);
    std::array<std::array<u64, 8>, 256> rc{};
    for (int ba = 0; ba < 8; ba++) {
      for (int bb = 0; bb < 8; bb++) {
        rc = {};
        for (unsigned mas = 1; mas < 256; mas++) {
          unsigned bit = std::countr_zero(mas);
          unsigned pre = mas & (mas - 1);
          for (int sb = 0; sb < 8; sb++) {
            rc[mas][sb] = rc[pre][sb] ^ bas[ba * 8 + int(bit)][bb * 8 + sb];
          }
        }
        std::size_t blk = std::size_t(ba * 8 + bb) << 16;
        for (unsigned va = 0; va < 256; va++) {
          for (unsigned vb = 1; vb < 256; vb++) {
            unsigned bit = std::countr_zero(vb);
            unsigned pre = vb & (vb - 1);
            res[blk | (std::size_t(va) << 8) | vb] =
                res[blk | (std::size_t(va) << 8) | pre] ^ rc[va][bit];
          }
        }
      }
    }
    return res;
  }();
  return tbl;
}

} // namespace nim_product_internal

/// @brief Compute the 64-bit nim product. Nimbers with twice as many bits form
/// a quadratic extension of the lower field: for alpha=2^m,
/// alpha^2=alpha xor 2^(m-1). Recursing on this identity generates all products
/// of binary basis elements. Bilinearity then groups eight basis elements at a
/// time into a 32 MiB byte-pair table, so one query needs 8*8 lookups and XORs.
inline std::uint64_t nim_product(std::uint64_t a, std::uint64_t b) {
  const std::vector<std::uint64_t> &tbl = nim_product_internal::byte_table();
  std::uint64_t res = 0;
  for (int ba = 0; ba < 8; ba++) {
    unsigned va = unsigned(a >> (ba * 8)) & 255;
    for (int bb = 0; bb < 8; bb++) {
      unsigned vb = unsigned(b >> (bb * 8)) & 255;
      std::size_t idx =
          (std::size_t(ba * 8 + bb) << 16) | (std::size_t(va) << 8) | vb;
      res ^= tbl[idx];
    }
  }
  return res;
}

} // namespace noya

#endif // NOYA_NIM_PRODUCT_HPP

#include <array>
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <vector>

/// @complexity Time: O(64) per product after O(2^22) preprocessing.
/// Space: O(2^25) bytes (32 MiB).

namespace noya {

namespace nim_product_internal {

using u64 = std::uint64_t;

inline u64 recursive_product(u64 a, u64 b, int lg) {
  assert(lg >= 1 && lg <= 64 && (lg & (lg - 1)) == 0);
  if (a == 0 || b == 0) {
    return 0;
  }
  if (a == 1) {
    return b;
  }
  if (b == 1) {
    return a;
  }
  if (lg == 1) {
    return a & b;
  }

  int hal = lg / 2;
  u64 mas = (u64(1) << hal) - 1;
  u64 al = a & mas;
  u64 ah = a >> hal;
  u64 bl = b & mas;
  u64 bh = b >> hal;

  u64 ll = recursive_product(al, bl, hal);
  u64 hh = recursive_product(ah, bh, hal);
  u64 com = recursive_product(al ^ ah, bl ^ bh, hal);
  u64 cro = com ^ ll ^ hh;
  u64 red = recursive_product(hh, u64(1) << (hal - 1), hal);
  return (ll ^ red) ^ ((cro ^ hh) << hal);
}

inline const std::vector<u64> &byte_table() {
  static const std::vector<u64> tbl = [] {
    std::array<std::array<u64, 64>, 64> bas{};
    for (int a = 0; a < 64; a++) {
      for (int b = a; b < 64; b++) {
        u64 val = recursive_product(u64(1) << a, u64(1) << b, 64);
        bas[a][b] = bas[b][a] = val;
      }
    }

    std::vector<u64> res(std::size_t(8) * 8 * 256 * 256);
    std::array<std::array<u64, 8>, 256> rc{};
    for (int ba = 0; ba < 8; ba++) {
      for (int bb = 0; bb < 8; bb++) {
        rc = {};
        for (unsigned mas = 1; mas < 256; mas++) {
          unsigned bit = std::countr_zero(mas);
          unsigned pre = mas & (mas - 1);
          for (int sb = 0; sb < 8; sb++) {
            rc[mas][sb] = rc[pre][sb] ^ bas[ba * 8 + int(bit)][bb * 8 + sb];
          }
        }
        std::size_t blk = std::size_t(ba * 8 + bb) << 16;
        for (unsigned va = 0; va < 256; va++) {
          for (unsigned vb = 1; vb < 256; vb++) {
            unsigned bit = std::countr_zero(vb);
            unsigned pre = vb & (vb - 1);
            res[blk | (std::size_t(va) << 8) | vb] =
                res[blk | (std::size_t(va) << 8) | pre] ^ rc[va][bit];
          }
        }
      }
    }
    return res;
  }();
  return tbl;
}

} // namespace nim_product_internal

/// @brief Compute the 64-bit nim product. Nimbers with twice as many bits form
/// a quadratic extension of the lower field: for alpha=2^m,
/// alpha^2=alpha xor 2^(m-1). Recursing on this identity generates all products
/// of binary basis elements. Bilinearity then groups eight basis elements at a
/// time into a 32 MiB byte-pair table, so one query needs 8*8 lookups and XORs.
inline std::uint64_t nim_product(std::uint64_t a, std::uint64_t b) {
  const std::vector<std::uint64_t> &tbl = nim_product_internal::byte_table();
  std::uint64_t res = 0;
  for (int ba = 0; ba < 8; ba++) {
    unsigned va = unsigned(a >> (ba * 8)) & 255;
    for (int bb = 0; bb < 8; bb++) {
      unsigned vb = unsigned(b >> (bb * 8)) & 255;
      std::size_t idx =
          (std::size_t(ba * 8 + bb) << 16) | (std::size_t(va) << 8) | vb;
      res ^= tbl[idx];
    }
  }
  return res;
}

} // namespace noya