問題概要
（非想定解などで）定数倍バトルになることを複数回経験したので，Library Checker 最速周辺の実装を勉強しました．過去に取り組んだときには最速実装が理解できなくて知らない知識かと思っていたが，そんなことはなかった．
基本的な解法
- 参考文献
$x,y<2^{64}$ のとき，上位ビットと下位ビットに分けて $x=x_0\oplus 2^{32}x_1$, $y=y_0\oplus 2^{32}y_1$ ($x_i,y_i<2^{32}$) とします．すると
$$x\otimes y = x_0\otimes y_0 \oplus (x_0\otimes y_0\oplus(x_0\oplus x_1)\otimes(y_0\oplus y_1))\cdot 2^{32}\oplus x_1\otimes y_1\otimes 2^{31}$$
となります．$\otimes$ は式に $5$ 個現れていますが，$x_0\otimes y_0$ が重複しており，結局 $32$ bit の場合の積 $4$ 回に帰着できていることが分かります．
これをやっていくと，計算回数はおおよそ bit 数の $2$ 乗に比例します．$64$ bit では雑に $4096$ 回程度の関数呼び出しがあるということになります．
なお，$4$ 回の積のうちひとつ $2^{31}$ をかけるという特殊な形で，特にこの下位 $16$ bit は消えるので，もう少し計算量を抑えることも可能です．
解法
小さい場合の計算結果を適切に前計算します．
解法1
$2^{64}$ 未満の整数はすべて $2^8$ 未満の整数 $x_0, \ldots, x_7$ を用いて $x = \bigoplus_{0\leq i<8} x_i2^{8i}$ と書けます．
したがって，$i,j<8, a,b<256$ の場合の $(2^ia)\otimes (2^jb)$ を前計算しておけば，配列参照 $64$ 回で答を求めることができます．
- 解答例（141ms, suisen さん）
解法2
$x,y< 256$ の場合の $x\otimes y$ をすべて前計算しておきます．あとは冒頭で述べた通りの再帰的な計算を 8bit になるまでやります．
- 解答例（98ms，momoyuuさん）
私の数えたところでは，$56$ 回の配列参照に帰着しています．
解法3
$x,y<2^{16}$ の場合の計算を高速に行えるような前計算として，原始根による指数・対数表を作ります．
Fermat の小定理や原始根の存在は，$\text{mod }p$ の場合が有名かと思いますが，その場合とほぼ同じ証明が一般の有限体でもできて，$q$ 元体では Fermat の小定理 $x^q=x$ や 原始根（$0$ 以外の要素全体が $\{1,r,\ldots,r^{q-2}\}$ となる $r$）の存在が成り立ちます（nimber の場合は $q=2^{16}, 2^{64}$ などとしてください）．
$16$ bit の nimber に関する適当な原始根 $r$ をとり，$E[i]=r^i$, $L[r^i]=i$ となるテーブルを作成しておきます．すると，$x\otimes y = E[L[x]+L[y]]$ のように積が計算可能になります．
ついでに，$x\otimes y \otimes 2^{15}$ や $x\otimes 2^{15}\otimes 2^{15}$ といった計算も，$E[L[x]+L[y]+L[2^{15}]]$ や $E[L[x]+L[2^{15}]+L[2^{15}]]$ のように行えることになります．
$64$ bit の場合は再帰的に計算して，$16$ bit に到達したらこの配列参照を利用します．
私の実装では，$64$ bit の Nimber product に対して配列参照 $29$ 回だと思います．
指数表は，$E[L[a]+L[b]]$ のような計算を可能にするため少し $2*65536$ より大きく前計算しています．kaze さんの実装では $E[L[x]+L[y]+L[2^{15}]]$ 等に備えて $3$ 倍とっています．
原始根はたくさんあり（$\text{euler_phi}(65535)$ 個で，半分くらい原始根）選択によって $L[2^{15}]=3$ にまで小さくできます．私と maroonrk さんの提出ではこれをやっています．
原始根による指数対数表を作るところにはいくつかの実装方法があります．
maroonrk さんは，愚直な nim product を反復しています．
私は，原始根を $r$ として $r\otimes 2^i$ を前計算したもの $16$ 個を埋め込んでおき，それを利用して $x<2^{16}$ に対するすべての $r\otimes x$ を得ています（かなり理解しやすい方法のつもり）．
kaze さんの実装例がなかなか理解できなかったのですが，Nimber と同型な有限体を多項式を利用して作り，そっちで構築した原始根の指数対数表を同型で Nimber にうつしてくるということをやっていると思います．
$f(x)\in \mathbb{F}_2[x]$ を $d$ 次既約多項式とするとき，$\mathbb{F}_2[x]/(f)$ は $2^d$ 元体です．また素数べき $q$ に対して $q$ 元体はすべて同型であることをが知られていて，Nimber の場合と適当な線形変換でうつりあうので，この線形変換を埋め込んでいます．$f$ を $x$ が原始根になるように選べば，$\mathbb{F}_2[x]/(f)$ における指数表の作成は，$g(x)\mapsto xg(x)\bmod f(x)$ という繰り返しで行えて，これは topbit があるとき何かを XOR するというタイプの操作の繰り返しで実装できます．
