Submit Info #38352

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

ケース詳細
Name Status Time Memory
example_00 AC 22 ms 1.25 MiB
large_00 AC 1665 ms 20.77 MiB
large_few_00 AC 184 ms 3.23 MiB
power_of_two_00 AC 27 ms 1.35 MiB
random_00 AC 1656 ms 20.75 MiB
random_01 AC 1647 ms 20.73 MiB
random_few_00 AC 186 ms 3.17 MiB
random_few_01 AC 188 ms 3.24 MiB
small_00 AC 948 ms 6.67 MiB
small_few_00 AC 116 ms 1.67 MiB

#include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() #define make_unique(x) sort((x).begin(), (x).end()); (x).erase(unique((x).begin(), (x).end()), (x).end()) #define imie(x) #x << ": " << x using namespace std; using li = long long; using LI = __int128_t; using ld = long double; using ull = unsigned long long; struct Nimber { ull x; const static array<array<ull, 256>, 256> small; const static array<array<array<ull, 256>, 8>, 8> prec; Nimber(ull _x = 0): x(_x) {} static ull mult_pwrs(unsigned x, unsigned y) { if (!(x & y)) { return 1ull << (x ^ y); } auto z = x & y; ull ans = 1ull << (x ^ y); for (ull t = z; t; t ^= 1ull << __builtin_ctzll(t)) { unsigned b = __builtin_ctzll(t); b = 1u << b; ans = nim_mult_stupid(ans, (1ull << b) | (1ull << (b - 1))); } return ans; } static ull nim_mult_stupid(ull a, ull b) { if (a < b) swap(a, b); if (b == 0) return 0; if (b == 1) return a; int p = 32; while (max(a, b) < (1ULL << p)) p /= 2; ull power = 1ULL << p; if (a >= power && b >= power) { ull ans = 0; ans ^= nim_mult_stupid(a % power, b % power); ans ^= nim_mult_stupid(a / power, b % power) * power; ans ^= nim_mult_stupid(a % power, b / power) * power; auto x = nim_mult_stupid(a / power, b / power); ans ^= x * power; ans ^= nim_mult_stupid(x, power / 2); return ans; } else { return nim_mult_stupid(a / power, b) * power ^ nim_mult_stupid(a % power, b); } } Nimber operator +(const Nimber& ot) const { return x ^ ot.x; } Nimber operator *(const Nimber& ot) const { ull ans = 0; for (int i = 0; i < 8; ++i) { for (int j = 0; j < 8; ++j) { ans ^= prec[i][j][small[(x >> (8 * i)) & 255][(ot.x >> (8 * j)) & 255]]; } } return ans; } Nimber& operator +=(const Nimber& ot) { x ^= ot.x; return *this; } Nimber& operator *=(const Nimber& ot) { *this = *this * ot; return *this; } }; const array<array<ull, 256>, 256> Nimber::small = []() { array<array<ull, 256>, 256> res; for (int i = 0; i < 256; ++i) { for (int j = 0; j < 256; ++j) { res[i][j] = nim_mult_stupid(i, j); } } return res; }(); const array<array<array<ull, 256>, 8>, 8> Nimber::prec = []() { array<array<array<ull, 256>, 8>, 8> res; for (int i = 0; i < 8; ++i) { for (int j = 0; j < 8; ++j) { ull cur = mult_pwrs(8 * i, 8 * j); for (int k = 0; k < 256; ++k) { res[i][j][k] = nim_mult_stupid(cur, k); } } } return res; }(); ull nim_multiply(ull a, ull b) { return (Nimber(a) * Nimber(b)).x; } #define all(x) (x).begin(), (x).end() #define itn int #define make_unique(x) sort((x).begin(), (x).end()); (x).erase(unique((x).begin(), (x).end()), (x).end()) inline int nxt() { int x; cin >> x; return x; } void solve() { ull a, b; cin >> a >> b; cout << nim_multiply(a, b) << "\n"; } int main() { int t = nxt(); while (t--) { solve(); } return 0; }