Submit Info #47234

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

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.72 MiB
large_00 AC 730 ms 20.25 MiB
large_few_00 AC 77 ms 2.74 MiB
power_of_two_00 AC 4 ms 0.46 MiB
random_00 AC 726 ms 20.33 MiB
random_01 AC 721 ms 20.31 MiB
random_few_00 AC 76 ms 2.68 MiB
random_few_01 AC 75 ms 2.68 MiB
small_00 AC 558 ms 6.18 MiB
small_few_00 AC 60 ms 1.18 MiB

#include <bits/stdc++.h> namespace haar_lib { uint8_t p[16][16] = { {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15}, {0, 2, 3, 1, 8,10,11, 9,12,14,15,13, 4, 6, 7, 5}, {0, 3, 1, 2,12,15,13,14, 4, 7, 5, 6, 8,11, 9,10}, {0, 4, 8,12, 6, 2,14,10,11,15, 3, 7,13, 9, 5, 1}, {0, 5,10,15, 2, 7, 8,13, 3, 6, 9,12, 1, 4,11,14}, {0, 6,11,13,14, 8, 5, 3, 7, 1,12,10, 9,15, 2, 4}, {0, 7, 9,14,10,13, 3, 4,15, 8, 6, 1, 5, 2,12,11}, {0, 8,12, 4,11, 3, 7,15,13, 5, 1, 9, 6,14,10, 2}, {0, 9,14, 7,15, 6, 1, 8, 5,12,11, 2,10, 3, 4,13}, {0,10,15, 5, 3, 9,12, 6, 1,11,14, 4, 2, 8,13, 7}, {0,11,13, 6, 7,12,10, 1, 9, 2, 4,15,14, 5, 3, 8}, {0,12, 4, 8,13, 1, 9, 5, 6,10, 2,14,11, 7,15, 3}, {0,13, 6,11, 9, 4,15, 2,14, 3, 8, 5, 7,10, 1,12}, {0,14, 7, 9, 5,11, 2,12,10, 4,13, 3,15, 1, 8, 6}, {0,15, 5,10, 1,14, 4,11, 2,13, 7, 8, 3,12, 6, 9} }; 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] = ((p[au][bu] ^ p[al][bu] ^ p[au][bl]) << 4) ^ p[au][p[bu][1 << 3]] ^ p[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; }