Submit Info #31761

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

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
large_00 AC 9703 ms 20.12 MiB
large_few_00 AC 995 ms 2.36 MiB
power_of_two_00 AC 3 ms 0.68 MiB
random_00 AC 4248 ms 20.14 MiB
random_01 AC 4246 ms 20.12 MiB
random_few_00 AC 426 ms 2.62 MiB
random_few_01 AC 427 ms 2.69 MiB
small_00 AC 522 ms 5.86 MiB
small_few_00 AC 48 ms 1.05 MiB

// https://judge.yosupo.jp/problem/nim_product_64 #include <bits/stdc++.h> using namespace std; template<class C>constexpr int sz(const C&c){return int(c.size());} using ll=long long;using ld=long double;constexpr const char nl='\n',sp=' '; template <class T> T addNim(T a, T b) { static_assert(is_unsigned<T>::value, "T must be an unsigned integral type"); return a ^ b; } template <class T, const int BITS> T initNim(T prod[BITS][BITS]) { for (int i = 0; i < BITS; i++) fill(prod[i], prod[i] + BITS, T()); return T(); } template <class T, const int BITS> T mulNimPow2(T prod[BITS][BITS], int i, int j) { static_assert(is_unsigned<T>::value, "T must be an unsigned integral type"); T &res = prod[i][j]; if (res) return res; if (!(i & j)) return res = T(1) << (i | j); int a = (i & j) & -(i & j); return res = mulNimPow2(prod, i ^ a, j) ^ mulNimPow2(prod, (i ^ a) | (a - 1), (j ^ a) | (i & (a - 1))); } template <class T> T mulNim(T a, T b) { static_assert(is_unsigned<T>::value, "T must be an unsigned integral type"); static constexpr const int BITS = 8 * sizeof(T); static T prod[BITS][BITS]; static T ZERO = initNim(prod); T res = ZERO; for (int i = 0; i < BITS; i++) if ((a >> i) & 1) for (int j = 0; j < BITS; j++) if ((b >> j) & 1) res = addNim(res, mulNimPow2(prod, i, j)); return res; } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); // freopen("err.txt", "w", stderr); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T; cin >> T; for (int ti = 0; ti < T; ti++) { uint64_t a, b; cin >> a >> b; cout << mulNim(a, b) << nl; } return 0; }