Submit Info #40278

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

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
large_00 AC 2822 ms 20.17 MiB
large_few_00 AC 283 ms 2.67 MiB
power_of_two_00 AC 2 ms 0.74 MiB
random_00 AC 2849 ms 20.22 MiB
random_01 AC 2850 ms 20.17 MiB
random_few_00 AC 289 ms 2.67 MiB
random_few_01 AC 288 ms 2.62 MiB
small_00 AC 311 ms 6.12 MiB
small_few_00 AC 29 ms 1.10 MiB

#include <bits/stdc++.h> using ull = uint64_t; ull _nimProd2[64][64]; bool allNimProd2() { for (int i = 0; i < 64; i++) { for (int j = 0; j < 64; j++) { if ((i & j) == 0) { _nimProd2[i][j] = 1ull << (i|j); } else { int a = (i&j) & -(i&j); _nimProd2[i][j] = _nimProd2[i ^ a][j] ^ _nimProd2[(i ^ a) | (a-1)][(j ^ a) | (i & (a-1))]; } } } return true; } auto _allNimProd2 = allNimProd2(); ull nimProd(ull x, ull y) { ull res = 0; for (int i = 0; i < 64 && (x >> i); i++) if ((x >> i) & 1) for (int j = 0; j < 64 && (y >> j); j++) if ((y >> j) & 1) res ^= _nimProd2[i][j]; return res; } int main() { using namespace std; ios_base::sync_with_stdio(false), cin.tie(nullptr); int T; cin >> T; while (T--) { uint64_t a, b; cin >> a >> b; cout << nimProd(a, b) << '\n'; } return 0; }