Submit Info #7035

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

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.72 MiB
large_00 AC 913 ms 20.60 MiB
large_few_00 AC 99 ms 3.05 MiB
power_of_two_00 AC 4 ms 1.05 MiB
random_00 AC 925 ms 20.67 MiB
random_01 AC 923 ms 20.57 MiB
random_few_00 AC 101 ms 3.07 MiB
random_few_01 AC 101 ms 3.07 MiB
small_00 AC 200 ms 6.57 MiB
small_few_00 AC 24 ms 1.57 MiB

#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; using ull=unsigned long long; ull memo[1<<8][1<<8]; ull nimproduct(ull a, ull b){ if(a==0 || b==0) return 0; if(a==1) return b; else if(b==1) return a; if(a<(1<<8) && b<(1<<8) && memo[a][b]) return memo[a][b]; ull a0, a1, b0, b1, c=max(a, b); int k; if(c<(1<<2)) k=2; else if(c<(1<<4)) k=4; else if(c<(1<<8)) k=8; else if(c<(1<<16)) k=16; else if(c<(1ull<<32)) k=32; else k=64; a0=a&((1ull<<(k>>1))-1), a1=a>>(k>>1); b0=b&((1ull<<(k>>1))-1), b1=b>>(k>>1); ull c00=nimproduct(a0, b0), c01=nimproduct(a0, b1), c10=nimproduct(a1, b0), c11=nimproduct(a1, b1); ull ans=((c11^c01^c10)<<(k>>1))^(nimproduct(c11, 1ull<<((k>>1)-1)))^c00; if(c<(1<<8)) memo[a][b]=ans; return ans; } int main() { int t; scanf("%d", &t); while(t--){ ull a, b; scanf("%llu %llu", &a, &b); printf("%llu\n", nimproduct(a, b)); } return 0; }