Submit Info #15229

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

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
large_00 AC 340 ms 87.42 MiB
large_few_00 AC 37 ms 9.42 MiB
power_of_two_00 AC 4 ms 0.94 MiB
random_00 AC 366 ms 86.30 MiB
random_01 AC 364 ms 86.30 MiB
random_few_00 AC 40 ms 9.30 MiB
random_few_01 AC 41 ms 9.30 MiB
small_00 AC 153 ms 26.65 MiB
small_few_00 AC 16 ms 2.93 MiB

#include <bits/stdc++.h> #define lg2 std::__lg #define ctz __builtin_ctz typedef unsigned int u32; typedef unsigned long long u64; struct istream { static const int size = 1 << 26; static const u32 b = 0x30303030; char buf[size], *vin; istream() : vin(buf - 1) {fread(buf, 1, size, stdin);} inline istream & operator >> (u64 &x) { x = *++vin & 15, ++ vin; u32*& idx = (u32*&)vin; for(; (*idx & b) == b; ++idx) { *idx ^= b; *idx = (*idx >> 8 & 0x00ff00ff) + (*idx & 0x00ff00ff) * 10; x = x * 10000 + (*idx & 65535) * 100 + (*idx >> 16); } for(; isdigit(*vin); ++vin) x = x * 10 + (*vin & 15); return *this; } } cin; struct ostream { static const int size = 1 << 27; char buf[size], *vout; u32 map[10000]; ostream () { for (int i = 0; i < 10000; ++i) map[i] = i % 10 + 48 << 24 | i / 10 % 10 + 48 << 16 | i / 100 % 10 + 48 << 8 | i / 1000 + 48; vout = buf + size; } ~ostream () {fwrite(vout, 1, buf + size - vout, stdout);} inline ostream & operator << (u64 x) { for (; x >= 10000; x /= 10000) *--(u32*&)vout = map[x % 10000]; do *--vout = x % 10 + 48; while (x /= 10); return *this; } inline ostream & operator << (char x) {return *--vout = x, *this;} inline ostream & operator << (const char *s) {const int L = strlen(s); return memcpy(vout -= L, s, L), *this;} } cout; namespace nimber_theory { constexpr u32 magic = 0x6cb4cd43u, magic1 = 0xb65a66a1u, n2f[32] = {0x00000001u, 0x78e2f1aeu, 0x6da3dc30u, 0x14435161u, 0x125a5b58u, 0x6dc8c9b5u, 0x6bc4a973u, 0x0776707cu, 0x00067f9fu, 0x071d0e42u, 0x7e91fd5au, 0x06606108u, 0x0673731fu, 0x6baed635u, 0x7efae8a0u, 0x78e2f1a8u, 0x6da3dc32u, 0xe586b23du, 0xce0695feu, 0x4427020cu, 0x4f701fc3u, 0xdce7e316u, 0xd1853220u, 0x76080269u, 0x7e9d0264u, 0x085a7d8cu, 0x84af09acu, 0x0dbbd2c5u, 0x721c0e9eu, 0xafbf5dc2u, 0xe8a1efd5u, 0xe4fab7d2u}, f2n[32] = {0x00000001u, 0x00010004u, 0x00018006u, 0x8003300eu, 0x00015e4fu, 0x5e4aa561u, 0xde480f07u, 0x442422a3u, 0x0001f76cu, 0xf7699aedu, 0x776b00d3u, 0xdd5fed5cu, 0xa922473du, 0xd19724a0u, 0x61cd4f5fu, 0xca4b192du, 0x0001118bu, 0x118ec4b7u, 0x918ca59au, 0xc0ab5f59u, 0x4fc5cea0u, 0xe0b71b33u, 0xabfe8354u, 0x1fbfb828u, 0xe6e66373u, 0xdbcbecc6u, 0xa0dad03cu, 0x40757290u, 0x5247d335u, 0xa918215eu, 0xb70d914cu, 0x5c487122u}; inline u32 nimber2field(u32 x) {u32 y = 0; for (; x; x &= x - 1) y ^= n2f[ctz(x)]; return y;} inline u32 field2nimber(u32 x) {u32 y = 0; for (; x; x &= x - 1) y ^= f2n[ctz(x)]; return y;} inline u32 product(u32 x, u32 y) { int b; u64 z = 0; for (; y; y &= y - 1) z ^= (u64)x << ctz(y); for (; z > UINT_MAX; z ^= 0x16cb4cd43ull << (lg2(z) - 32)); return (u32)z; } } u64 ans[1000001]; inline u64 np(u64 A, u64 B) { using namespace nimber_theory; u32 a = nimber2field(A), b = nimber2field(B), c = nimber2field(A >> 32), d = nimber2field(B >> 32), e = product(a, b); return (u64)field2nimber(product(a ^ c, b ^ d) ^ e) << 32 | field2nimber(product(product(c, d), 3841636306u) ^ e); } int main() { int i, T; u64 a, b; cin >> a, T = a; for (i = 0; i < T; ++i) cin >> a >> b, ans[i] = np(a, b); for (i = T - 1; i >= 0; --i) cout << '\n' << ans[i]; return 0; }