Submit Info #47208

Problem Lang User Status Time Memory
Nim Product ($\mathbb{F}_{2^{64}}$) cpp Haar AC 871 ms 20.34 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.68 MiB
large_00 AC 826 ms 20.33 MiB
large_few_00 AC 87 ms 2.68 MiB
power_of_two_00 AC 5 ms 0.80 MiB
random_00 AC 860 ms 20.30 MiB
random_01 AC 871 ms 20.34 MiB
random_few_00 AC 90 ms 2.80 MiB
random_few_01 AC 91 ms 2.68 MiB
small_00 AC 681 ms 6.18 MiB
small_few_00 AC 73 ms 1.18 MiB

#include <bits/stdc++.h> namespace haar_lib { uint8_t nim_product_4(uint8_t a, uint8_t b) { constexpr static uint32_t mask = 0b11; constexpr static uint8_t p[4][4] = { {0, 0, 0, 0}, {0, 1, 2, 3}, {0, 2, 3, 1}, {0, 3, 1, 2} }; uint8_t au = a >> 2; uint8_t al = a & mask; uint8_t bu = b >> 2; uint8_t bl = b & mask; return ((p[au][bu] ^ p[al][bu] ^ p[au][bl]) << 2) ^ (p[au][p[bu][1 << 1]] ^ p[al][bl]); } uint8_t nim_product_8(uint8_t a, uint8_t b) { static bool check[256][256] = {}; static uint8_t memo[256][256] = {}; if (check[a][b]) return memo[a][b]; check[a][b] = true; constexpr static uint32_t mask = 0xf; uint8_t au = a >> 4; uint8_t al = a & mask; uint8_t bu = b >> 4; uint8_t bl = b & mask; return memo[a][b] = ((nim_product_4(au, bu) ^ nim_product_4(al, bu) ^ nim_product_4(au, bl)) << 4) ^ (nim_product_4(au, nim_product_4(bu, 1 << 3)) ^ nim_product_4(al, bl)); } uint16_t nim_product_16(uint16_t a, uint16_t b) { constexpr static uint32_t mask = 0xff; uint8_t au = a >> 8; uint8_t al = a & mask; uint8_t bu = b >> 8; uint8_t bl = b & mask; return ((uint16_t)(nim_product_8(au, bu) ^ nim_product_8(al, bu) ^ nim_product_8(au, bl)) << 8) ^ (nim_product_8(au, nim_product_8(bu, 1 << 7)) ^ nim_product_8(al, bl)); } uint32_t nim_product_32(uint32_t a, uint32_t b) { constexpr static uint32_t mask = 0xffff; uint16_t au = a >> 16; uint16_t al = a & mask; uint16_t bu = b >> 16; uint16_t bl = b & mask; return ((uint32_t)(nim_product_16(au, bu) ^ nim_product_16(al, bu) ^ nim_product_16(au, bl)) << 16) ^ (nim_product_16(au, nim_product_16(bu, 1 << 15)) ^ nim_product_16(al, bl)); } uint64_t nim_product_64(uint64_t a, uint64_t b) { constexpr static uint64_t mask = 0xffffffff; uint64_t au = a >> 32; uint64_t al = a & mask; uint64_t bu = b >> 32; uint64_t bl = b & mask; return ((uint64_t)(nim_product_32(au, bu) ^ nim_product_32(al, bu) ^ nim_product_32(au, bl)) << 32) ^ (nim_product_32(au, nim_product_32(bu, 1 << 31)) ^ nim_product_32(al, bl)); } } namespace hl = haar_lib; int main() { std::cin.tie(0); std::ios::sync_with_stdio(false); int T; std::cin >> T; while (T--) { uint64_t A, B; std::cin >> A >> B; std::cout << hl::nim_product_64(A, B) << "\n"; } return 0; }