Submit Info #4543

Problem Lang User Status Time Memory
Nim Product ($\mathbb{F}_{2^{64}}$) d hos AC 757 ms 21.77 MiB

ケース詳細
Name Status Time Memory
example_00 AC 0 ms 1.43 MiB
large_00 AC 736 ms 21.77 MiB
large_few_00 AC 80 ms 4.14 MiB
power_of_two_00 AC 7 ms 2.16 MiB
random_00 AC 753 ms 21.77 MiB
random_01 AC 757 ms 21.67 MiB
random_few_00 AC 81 ms 4.17 MiB
random_few_01 AC 81 ms 4.16 MiB
small_00 AC 486 ms 7.67 MiB
small_few_00 AC 54 ms 2.67 MiB

import std.conv, std.functional, std.range, std.stdio, std.string; import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons; import core.bitop; class EOFException : Throwable { this() { super("EOF"); } } string[] tokens; string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; } int readInt() { return readToken.to!int; } long readLong() { return readToken.to!long; } real readReal() { return readToken.to!real; } bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } } bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } } int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; } int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); } int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); } // 2^i \otimes 2^j, a \otimes b ulong[][] NIM_MUL_BASE; ubyte[][] NIM_MUL_SMALL; // (2^8)^i \otimes (2^8)^j \otimes a ulong[][][] NIM_MUL_TABLE; void prepareNimber() { import core.bitop : bsr; NIM_MUL_BASE = new ulong[][](64, 64); foreach (i; 0 .. 64) { NIM_MUL_BASE[0][i] = NIM_MUL_BASE[i][0] = 1UL << i; } foreach (i; 1 .. 64) foreach (j; 1 .. 64) { const n = bsr(i | j); if (i < 1 << n) { NIM_MUL_BASE[i][j] = NIM_MUL_BASE[i][j ^ 1 << n] << (1 << n); } else if (j < 1 << n) { NIM_MUL_BASE[i][j] = NIM_MUL_BASE[i ^ 1 << n][j] << (1 << n); } else { foreach (k; 0 .. 64) { if (NIM_MUL_BASE[i ^ 1 << n][j ^ 1 << n] & 1UL << k) { NIM_MUL_BASE[i][j] ^= NIM_MUL_BASE[k][1 << n]; NIM_MUL_BASE[i][j] ^= NIM_MUL_BASE[k][(1 << n) - 1]; } } } } NIM_MUL_SMALL = new ubyte[][](256, 256); foreach (i; 0 .. 8) foreach (j; 0 .. 8) { NIM_MUL_SMALL[1 << i][1 << j] = cast(ubyte)(NIM_MUL_BASE[i][j]); } foreach (a; 1 .. 256) foreach (b; 1 .. 256) { if (b & b - 1) { NIM_MUL_SMALL[a][b] = NIM_MUL_SMALL[a][b & -b] ^ NIM_MUL_SMALL[a][b & b - 1]; } else { NIM_MUL_SMALL[a][b] = NIM_MUL_SMALL[a & -a][b] ^ NIM_MUL_SMALL[a & a - 1][b]; } } NIM_MUL_TABLE = new ulong[][][](8, 8, 256); foreach (i; 0 .. 8) foreach (j; 0 .. 8) { foreach (k; 0 .. 8) { NIM_MUL_TABLE[i][j][1 << k] = NIM_MUL_BASE[8 * i][8 * j + k]; } foreach (a; 1 .. 256) { NIM_MUL_TABLE[i][j][a] = NIM_MUL_TABLE[i][j][a & -a] ^ NIM_MUL_TABLE[i][j][a & a - 1]; } } } ulong nimMul(ulong a, ulong b) { ulong c; foreach (i; 0 .. 8) foreach (j; 0 .. 8) { c ^= NIM_MUL_TABLE[i][j][ NIM_MUL_SMALL[(a >> (8 * i)) & 255][(b >> (8 * j)) & 255]]; } return c; } void main() { prepareNimber(); try { for (; ; ) { const numCases = readInt(); foreach (caseId; 0 .. numCases) { const A = readToken.to!ulong; const B = readToken.to!ulong; const ans = nimMul(A, B); writeln(ans); } } } catch (EOFException e) { } }