Nimber
(src/math/Nimber.hpp)

• View this file on GitHub
• Last update: 2023-01-12 22:28:24+09:00
• Include: #include "src/math/Nimber.hpp"

概要

排他的論理和 (XOR) $\oplus$ を加法，Nim product $\otimes$ を乗法とすると $2^{2^n}$ 未満の非負整数の上に体を成す．

Nim product については $n \otimes 2^{2^k} = n 2^{2^k}\ (n < 2^{2^k})$ 及び $2^{2^k} \otimes 2^{2^k} = (3 / 2) 2^{2^k}$ が成立することから，$a \oplus b$ について $a = a_u 2^{32} + a_l,\ b = b_u 2^{32} + b_l$ とすると，

\[\begin{aligned} &&& a \otimes b \\ &=&& (a_u 2^{32} + a_l) \otimes (b_u 2^{32} + b_l) \\ &=&& (a_u \otimes 2^{32} \oplus a_l) \otimes (b_u \otimes 2^{32} \oplus b_l) \quad (\because n 2^{2^k} = n \otimes 2^{2^k}) \\ &=&& (a_u \otimes 2^{32} \otimes b_u \otimes 2^{32}) \oplus (a_u \otimes 2^{32} \otimes b_l) \oplus (a_l \otimes b_u \otimes 2^{32}) \oplus (a_l \otimes b_l) \\ &=&& (a_u \otimes b_u \otimes (2^{32} + 2^{31})) \oplus ((a_u \otimes b_l \oplus a_l \otimes b_u) \otimes 2^{32}) \oplus (a_l \otimes b_l) \quad (\because 2^{2^k} \otimes 2^{2^k} = (3 / 2) 2^{2^k}) \\ &=&& (a_u \otimes b_u \otimes (2^{32} \oplus 2^{31})) \oplus ((a_u \otimes b_l \oplus a_l \otimes b_u) \otimes 2^{32}) \oplus (a_l \otimes b_l) \\ &=&& ((a_u \otimes b_u \oplus a_u \otimes b_l \oplus a_l \otimes b_u) \otimes 2^{32}) \oplus (a_u \otimes b_u \otimes 2^{31}) \oplus (a_l \otimes b_l) \\ &=&& ((a_u \otimes b_u \oplus a_u \otimes b_l \oplus a_l \otimes b_u) \times 2^{32}) \oplus (a_u \otimes b_u \otimes 2^{31}) \oplus (a_l \otimes b_l) \\ \end{aligned}\]

が成立するから再帰的に計算可能である．

問題例

• AtCoder Beginner Contest 274 Ex - XOR Sum of Arrays
• The 2nd Universal Cup. Stage 5: Northern D. Two Missing Numbers

Links

• Nim product - kyopro_friends’ diary
  • 代数的性質の証明について詳しい．
• Nimberの乗法・Sqrt・逆元・二次方程式 - でも今日はSRMあるから

Verified with

• test/yosupo/nim_product_64.test.cpp

Code

#pragma once
#include <algorithm>
#include <array>

namespace Nimber64 {

struct nim {
    const static std::array<std::array<unsigned char, 256>, 256> small;
    const static std::array<std::array<std::array<nim, 256>, 8>, 8> precalc;
    unsigned long long v;

    nim() : v(0) {}

    nim(unsigned long long _v) : v(_v) {}

    nim& operator+=(const nim& rhs) {
        v ^= rhs.v;
        return *this;
    }

    nim& operator-=(const nim& rhs) {
        v ^= rhs.v;
        return *this;
    }

    nim& operator*=(const nim& rhs) {
        nim res;
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                res += precalc[i][j][small[(v >> (8 * i)) & 255][(rhs.v >> (8 * j)) & 255]];
            }
        }
        return *this = res;
    }

    const nim operator+(const nim& rhs) const { return nim(*this) += rhs; }

    const nim operator-(const nim& rhs) const { return nim(*this) -= rhs; }

    const nim operator*(const nim& rhs) const { return nim(*this) *= rhs; }
};

nim mul_naive(nim l, nim r) {
    unsigned long long a = l.v, b = r.v;
    if (a < b) std::swap(a, b);
    if (b == 0) return 0;
    if (b == 1) return a;
    int p = 32;
    while (std::max(a, b) < (1ULL << p)) p >>= 1;
    unsigned long long power = 1ULL << p;
    if (a >= power and b >= power) {
        nim res;
        res += mul_naive(a % power, b % power);
        res += mul_naive(a / power, b % power).v * power;
        res += mul_naive(a % power, b / power).v * power;
        auto x = mul_naive(a / power, b / power);
        res += x.v * power;
        res += mul_naive(x, power / 2);
        return res;
    } else
        return nim(mul_naive(a / power, b).v * power) + mul_naive(a % power, b);
}

const std::array<std::array<unsigned char, 256>, 256> nim::small = []() {
    std::array<std::array<unsigned char, 256>, 256> small;
    for (int i = 0; i < 256; i++) {
        for (int j = 0; j < 256; j++) {
            small[i][j] = (unsigned char)(mul_naive(i, j).v);
        }
    }
    return small;
}();

const std::array<std::array<std::array<nim, 256>, 8>, 8> nim::precalc = []() {
    std::array<std::array<std::array<nim, 256>, 8>, 8> precalc;
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            nim tmp = mul_naive(1ULL << (8 * i), 1ULL << (8 * j));
            for (int k = 0; k < 256; k++) precalc[i][j][k] = mul_naive(tmp, k);
        }
    }
    return precalc;
}();

}  // namespace Nimber64

#line 2 "src/math/Nimber.hpp"
#include <algorithm>
#include <array>

namespace Nimber64 {

struct nim {
    const static std::array<std::array<unsigned char, 256>, 256> small;
    const static std::array<std::array<std::array<nim, 256>, 8>, 8> precalc;
    unsigned long long v;

    nim() : v(0) {}

    nim(unsigned long long _v) : v(_v) {}

    nim& operator+=(const nim& rhs) {
        v ^= rhs.v;
        return *this;
    }

    nim& operator-=(const nim& rhs) {
        v ^= rhs.v;
        return *this;
    }

    nim& operator*=(const nim& rhs) {
        nim res;
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                res += precalc[i][j][small[(v >> (8 * i)) & 255][(rhs.v >> (8 * j)) & 255]];
            }
        }
        return *this = res;
    }

    const nim operator+(const nim& rhs) const { return nim(*this) += rhs; }

    const nim operator-(const nim& rhs) const { return nim(*this) -= rhs; }

    const nim operator*(const nim& rhs) const { return nim(*this) *= rhs; }
};

nim mul_naive(nim l, nim r) {
    unsigned long long a = l.v, b = r.v;
    if (a < b) std::swap(a, b);
    if (b == 0) return 0;
    if (b == 1) return a;
    int p = 32;
    while (std::max(a, b) < (1ULL << p)) p >>= 1;
    unsigned long long power = 1ULL << p;
    if (a >= power and b >= power) {
        nim res;
        res += mul_naive(a % power, b % power);
        res += mul_naive(a / power, b % power).v * power;
        res += mul_naive(a % power, b / power).v * power;
        auto x = mul_naive(a / power, b / power);
        res += x.v * power;
        res += mul_naive(x, power / 2);
        return res;
    } else
        return nim(mul_naive(a / power, b).v * power) + mul_naive(a % power, b);
}

const std::array<std::array<unsigned char, 256>, 256> nim::small = []() {
    std::array<std::array<unsigned char, 256>, 256> small;
    for (int i = 0; i < 256; i++) {
        for (int j = 0; j < 256; j++) {
            small[i][j] = (unsigned char)(mul_naive(i, j).v);
        }
    }
    return small;
}();

const std::array<std::array<std::array<nim, 256>, 8>, 8> nim::precalc = []() {
    std::array<std::array<std::array<nim, 256>, 8>, 8> precalc;
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            nim tmp = mul_naive(1ULL << (8 * i), 1ULL << (8 * j));
            for (int k = 0; k < 256; k++) precalc[i][j][k] = mul_naive(tmp, k);
        }
    }
    return precalc;
}();

}  // namespace Nimber64

Back to top page