Submit Info #49386

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

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.68 MiB
large_00 AC 2224 ms 20.58 MiB
large_few_00 AC 228 ms 3.05 MiB
power_of_two_00 AC 6 ms 0.68 MiB
random_00 AC 2248 ms 20.62 MiB
random_01 AC 2205 ms 20.59 MiB
random_few_00 AC 230 ms 3.04 MiB
random_few_01 AC 237 ms 3.05 MiB
small_00 AC 852 ms 6.55 MiB
small_few_00 AC 90 ms 1.55 MiB

#include <bits/stdc++.h> using namespace std; typedef unsigned long long ull; ull memo[1<<8][1<<8]; ull f(ull a,ull b){ if (min(a,b)<=1) return a*b; if (a<(1<<8) && b<(1<<8) && memo[a][b]){ return memo[a][b]; } ull m=max(a,b); int k; if(m<(1<<2)) k=1; else if(m<(1<<4)) k=2; else if(m<(1<<8)) k=3; else if(m<(1<<16)) k=4; else if(m<(1ull<<32)) k=5; else k=6; ull au=a>>(1ull<<(k-1)); ull al=a&((1ull<<(1<<(k-1)))-1); ull bu=b>>(1ull<<(k-1)); ull bl=b&ull((1ull<<(1<<(k-1)))-1); ull cu=f(au,bu)^f(al,bu)^f(au,bl); ull cl=f((1ull<<((1<<(k-1)))-1),f(au,bu))^f(al,bl); ull c=cu<<(1<<(k-1))|cl; if (m<(1<<8)) memo[a][b]=c; return c; } int main(void){ int T; cin>>T; for(int i=0;i<T;i++){ ull A,B; cin>>A>>B; cout<<f(A,B)<<endl; } }