nim_product.hpp¶
计算 64 位 nimber 的 nim 乘法；用于 Sprague–Grundy 值落在 nim 域乘法结构的博弈题。
\[
\displaystyle a \otimes b
\]
Complexity: Time: \(O(1)\) per 64-bit product after \(O(2^{16})\) preprocessing. Space: \(O(2^{16})\) bytes (71 KiB).
AC 记录：nim_product_64。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(1) per 64-bit product after O(2^16) preprocessing.
/// Space: O(2^16) bytes (71 KiB).
#include <array>
#include <bit>
#include <cassert>
#include <cstdint>
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 red = recursive_product(hh, u64(1) << (hal - 1), hal);
return (ll ^ red) ^ ((com ^ ll) << hal);
}
struct tables {
std::array<std::uint8_t, 65536> mul{};
// Blocks 0, 1..2, 3..6 reduce products in the 8-, 16-, and 32-bit fields.
std::array<std::array<std::uint32_t, 256>, 7> red{};
tables() {
for (unsigned a = 1; a < 256; ++a) {
for (unsigned b = 1; b < 256; ++b) {
unsigned p = b & (b - 1), q = a & (a - 1);
auto &v = mul[(a << 8) | b];
if (p) v = mul[(a << 8) | p] ^ mul[(a << 8) | (b ^ p)];
else if (q) v = mul[(q << 8) | b] ^ mul[((a ^ q) << 8) | b];
else v = std::uint8_t(recursive_product(a, b, 8));
}
}
for (int w = 8; w <= 32; w *= 2) {
for (int i = 0; i < w / 8; ++i) {
std::array<std::uint32_t, 8> bas{};
for (int j = 0; j < 8; ++j) {
bas[j] = std::uint32_t(recursive_product(
u64(1) << (i * 8 + j), u64(1) << (w - 1), w));
}
auto &t = red[w / 8 - 1 + i];
for (unsigned m = 1; m < 256; ++m)
t[m] = t[m & (m - 1)] ^ bas[std::countr_zero(m)];
}
}
}
template<int w> u64 product(u64 a, u64 b) const {
if constexpr (w == 8) {
return mul[(a << 8) | b];
} else {
constexpr int h = w / 2;
constexpr u64 mask = (u64(1) << h) - 1;
u64 al = a & mask, ah = a >> h, bl = b & mask, bh = b >> h;
u64 lo = product<h>(al, bl), hi = product<h>(ah, bh);
u64 mid = product<h>(al ^ ah, bl ^ bh), r = 0;
// Multiply hi by 2^(h-1), a linear map over the binary field.
for (int i = 0; i < h / 8; ++i)
r ^= red[h / 8 - 1 + i][(hi >> (i * 8)) & 255];
return lo ^ r ^ ((mid ^ lo) << h);
}
}
};
} // namespace nim_product_internal
/// @brief Compute the 64-bit nim product. For alpha=2^h, the quadratic
/// extension satisfies alpha^2=alpha xor 2^(h-1). Three half-width products
/// per level reduce a query to 27 byte products. Small linear tables handle
/// multiplication by 2^(h-1); all tables are initialized on the first use.
inline std::uint64_t nim_product(std::uint64_t a, std::uint64_t b) {
if (a == 0 || b == 0) return 0;
static const nim_product_internal::tables tbl;
return tbl.product<64>(a, b);
}
} // namespace noya
// NOYA_NIM_PRODUCT_HPP
#ifndef NOYA_NIM_PRODUCT_HPP
#define NOYA_NIM_PRODUCT_HPP 1
/// @complexity Time: O(1) per 64-bit product after O(2^16) preprocessing.
/// Space: O(2^16) bytes (71 KiB).
#include <array>
#include <bit>
#include <cassert>
#include <cstdint>
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 red = recursive_product(hh, u64(1) << (hal - 1), hal);
return (ll ^ red) ^ ((com ^ ll) << hal);
}
struct tables {
std::array<std::uint8_t, 65536> mul{};
// Blocks 0, 1..2, 3..6 reduce products in the 8-, 16-, and 32-bit fields.
std::array<std::array<std::uint32_t, 256>, 7> red{};
tables() {
for (unsigned a = 1; a < 256; ++a) {
for (unsigned b = 1; b < 256; ++b) {
unsigned p = b & (b - 1), q = a & (a - 1);
auto &v = mul[(a << 8) | b];
if (p) v = mul[(a << 8) | p] ^ mul[(a << 8) | (b ^ p)];
else if (q) v = mul[(q << 8) | b] ^ mul[((a ^ q) << 8) | b];
else v = std::uint8_t(recursive_product(a, b, 8));
}
}
for (int w = 8; w <= 32; w *= 2) {
for (int i = 0; i < w / 8; ++i) {
std::array<std::uint32_t, 8> bas{};
for (int j = 0; j < 8; ++j) {
bas[j] = std::uint32_t(recursive_product(
u64(1) << (i * 8 + j), u64(1) << (w - 1), w));
}
auto &t = red[w / 8 - 1 + i];
for (unsigned m = 1; m < 256; ++m)
t[m] = t[m & (m - 1)] ^ bas[std::countr_zero(m)];
}
}
}
template<int w> u64 product(u64 a, u64 b) const {
if constexpr (w == 8) {
return mul[(a << 8) | b];
} else {
constexpr int h = w / 2;
constexpr u64 mask = (u64(1) << h) - 1;
u64 al = a & mask, ah = a >> h, bl = b & mask, bh = b >> h;
u64 lo = product<h>(al, bl), hi = product<h>(ah, bh);
u64 mid = product<h>(al ^ ah, bl ^ bh), r = 0;
// Multiply hi by 2^(h-1), a linear map over the binary field.
for (int i = 0; i < h / 8; ++i)
r ^= red[h / 8 - 1 + i][(hi >> (i * 8)) & 255];
return lo ^ r ^ ((mid ^ lo) << h);
}
}
};
} // namespace nim_product_internal
/// @brief Compute the 64-bit nim product. For alpha=2^h, the quadratic
/// extension satisfies alpha^2=alpha xor 2^(h-1). Three half-width products
/// per level reduce a query to 27 byte products. Small linear tables handle
/// multiplication by 2^(h-1); all tables are initialized on the first use.
inline std::uint64_t nim_product(std::uint64_t a, std::uint64_t b) {
if (a == 0 || b == 0) return 0;
static const nim_product_internal::tables tbl;
return tbl.product<64>(a, b);
}
} // namespace noya
#endif // NOYA_NIM_PRODUCT_HPP
/// @complexity Time: O(1) per 64-bit product after O(2^16) preprocessing.
/// Space: O(2^16) bytes (71 KiB).
#include <array>
#include <bit>
#include <cassert>
#include <cstdint>
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 red = recursive_product(hh, u64(1) << (hal - 1), hal);
return (ll ^ red) ^ ((com ^ ll) << hal);
}
struct tables {
std::array<std::uint8_t, 65536> mul{};
// Blocks 0, 1..2, 3..6 reduce products in the 8-, 16-, and 32-bit fields.
std::array<std::array<std::uint32_t, 256>, 7> red{};
tables() {
for (unsigned a = 1; a < 256; ++a) {
for (unsigned b = 1; b < 256; ++b) {
unsigned p = b & (b - 1), q = a & (a - 1);
auto &v = mul[(a << 8) | b];
if (p) v = mul[(a << 8) | p] ^ mul[(a << 8) | (b ^ p)];
else if (q) v = mul[(q << 8) | b] ^ mul[((a ^ q) << 8) | b];
else v = std::uint8_t(recursive_product(a, b, 8));
}
}
for (int w = 8; w <= 32; w *= 2) {
for (int i = 0; i < w / 8; ++i) {
std::array<std::uint32_t, 8> bas{};
for (int j = 0; j < 8; ++j) {
bas[j] = std::uint32_t(recursive_product(
u64(1) << (i * 8 + j), u64(1) << (w - 1), w));
}
auto &t = red[w / 8 - 1 + i];
for (unsigned m = 1; m < 256; ++m)
t[m] = t[m & (m - 1)] ^ bas[std::countr_zero(m)];
}
}
}
template<int w> u64 product(u64 a, u64 b) const {
if constexpr (w == 8) {
return mul[(a << 8) | b];
} else {
constexpr int h = w / 2;
constexpr u64 mask = (u64(1) << h) - 1;
u64 al = a & mask, ah = a >> h, bl = b & mask, bh = b >> h;
u64 lo = product<h>(al, bl), hi = product<h>(ah, bh);
u64 mid = product<h>(al ^ ah, bl ^ bh), r = 0;
// Multiply hi by 2^(h-1), a linear map over the binary field.
for (int i = 0; i < h / 8; ++i)
r ^= red[h / 8 - 1 + i][(hi >> (i * 8)) & 255];
return lo ^ r ^ ((mid ^ lo) << h);
}
}
};
} // namespace nim_product_internal
/// @brief Compute the 64-bit nim product. For alpha=2^h, the quadratic
/// extension satisfies alpha^2=alpha xor 2^(h-1). Three half-width products
/// per level reduce a query to 27 byte products. Small linear tables handle
/// multiplication by 2^(h-1); all tables are initialized on the first use.
inline std::uint64_t nim_product(std::uint64_t a, std::uint64_t b) {
if (a == 0 || b == 0) return 0;
static const nim_product_internal::tables tbl;
return tbl.product<64>(a, b);
}
} // namespace noya
// NOYA_NIM_PRODUCT_HPP