test/yosupo/nim_product_64.test.cpp

• View this file on GitHub
• Last update: 2022-04-18 22:20:33+09:00
• Problem: https://judge.yosupo.jp/problem/nim_product_64

Depends on

• Nimber (math/nimber.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/nim_product_64"

#include "../../math/nimber.hpp"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (int i = (int)(s); i < (int)(t); ++i)
#define revrep(i, t, s) for (int i = (int)(t)-1; i >= (int)(s); --i)
#define all(x) begin(x), end(x)
template <typename T> bool chmax(T& a, const T& b) { return a < b ? (a = b, 1) : 0; }
template <typename T> bool chmin(T& a, const T& b) { return a > b ? (a = b, 1) : 0; }

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    int T;
    cin >> T;
    while (T--) {
        Nimber A, B;
        cin >> A >> B;
        cout << A*B << "\n";
    }
}

#line 1 "test/yosupo/nim_product_64.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/nim_product_64"

#line 2 "math/nimber.hpp"
#include <iostream>
#include <array>

class Nimber {
    using ull = unsigned long long;

public:
    Nimber(ull x = 0) noexcept : x(x) {}
    ull value() const noexcept { return x; }

    Nimber operator+(const Nimber& r) const noexcept { return x ^ r.x; }
    Nimber operator*(const Nimber& r) const noexcept {
        ull res = 0;
        for (int i = 0; i < 8; ++i) {
            ull a = (x >> (8 * i)) & 255;
            for (int j = 0; j < 8; ++j) {
                ull b = (r.x >> (8 * j)) & 255;
                res ^= precalc[i][j][small[a][b]];
            }
        }
        return res;
    }

    Nimber& operator+=(const Nimber& r) noexcept { return *this = *this + r; }
    Nimber& operator*=(const Nimber& r) noexcept { return *this = *this * r; }
    bool operator==(const Nimber& r) const noexcept { return x == r.x; }
    bool operator!=(const Nimber& r) const noexcept { return x != r.x; }
    bool operator<(const Nimber& r) const { return x < r.x; };
    bool operator>(const Nimber& r) const { return x > r.x; };
    bool operator<=(const Nimber& r) const { return x <= r.x; };
    bool operator>=(const Nimber& r) const { return x >= r.x; };
    friend std::ostream& operator<<(std::ostream& os, const Nimber& r) { return os << r.x; }
    friend std::istream& operator>>(std::istream& is, Nimber& r) {
        ull t;
        is >> t;
        r = Nimber(t);
        return is;
    }

private:
    const static std::array<std::array<ull, 256>, 256> small;
    const static std::array<std::array<std::array<ull, 256>, 8>, 8> precalc;

    static ull mul_naive(ull x, ull y) {
        if (x <= 1 || y <= 1) return x * y;
        for (int k = 5; ; --k) {
            int shift = 1 << k;
            ull mask = (1ULL << shift) - 1;
            if (std::max(x, y) > mask) {
                ull v00 = mul_naive(x & mask, y & mask);
                ull v01 = mul_naive(x & mask, y >> shift);
                ull v10 = mul_naive(x >> shift, y & mask);
                ull v11 = mul_naive(x >> shift, y >> shift);
                return v00 ^ ((v01 ^ v10 ^ v11) << shift) ^ mul_naive(v11, 1ULL << (shift - 1));
            }
        }
    }

    ull x;
};

const std::array<std::array<Nimber::ull, 256>, 256> Nimber::small = []() {
    std::array<std::array<ull, 256>, 256> ret;
    for (int i = 0; i < 256; ++i) {
        for (int j = 0; j < 256; ++j) {
            ret[i][j] = mul_naive(i, j);
        }
    }
    return ret;
}();

const std::array<std::array<std::array<Nimber::ull, 256>, 8>, 8> Nimber::precalc = []() {
    std::array<std::array<std::array<ull, 256>, 8>, 8> ret;
    for (int i = 0; i < 8; ++i) {
        for (int j = 0; j < 8; ++j) {
            ull p = mul_naive(1ULL << (8 * i), 1ULL << (8 * j));
            for (int k = 0; k < 256; ++k) {
                ret[i][j][k] = mul_naive(p, k);
            }
        }
    }
    return ret;
}();
#line 4 "test/yosupo/nim_product_64.test.cpp"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (int i = (int)(s); i < (int)(t); ++i)
#define revrep(i, t, s) for (int i = (int)(t)-1; i >= (int)(s); --i)
#define all(x) begin(x), end(x)
template <typename T> bool chmax(T& a, const T& b) { return a < b ? (a = b, 1) : 0; }
template <typename T> bool chmin(T& a, const T& b) { return a > b ? (a = b, 1) : 0; }

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    int T;
    cin >> T;
    while (T--) {
        Nimber A, B;
        cin >> A >> B;
        cout << A*B << "\n";
    }
}

Back to top page