Nim积总不能一直打四次暴力吧！
用SG定理等东西，可以证明 \((N, \oplus, \otimes)\) 构成一个域。（证明很难，我不会）
其中 \(\oplus\) 为异或, \(x \otimes y = \mathop{\textrm{mex}}_{1 \leq i < x, 1 \leq j < y} \left\{ (i \otimes y) \oplus (x \otimes j) \oplus (i \otimes j)\right\}\)，即暴力对子状态计算。
然后还有优美的性质，能使计算 \(\otimes\) 做到 \(O(\textrm{poly} (\log))\)：
对于一个费马数 \(M = 2^{2^a}\)，对于一个 \(y\)，有以下两个性质：
- \(M \otimes y = M \times y ~~~ (M > y)\)
- \(M \otimes M = M \oplus \frac{M}{2}\)
有俩 \(\log\) 的做法广为流传。但是因为不太常用，我人也懒，所以搞了一个不知是三个还是两个 \(\log\) 的东西（反正贼好写）：
int normalnimproduct(int x, int y) ;
int nimproduct(int x, int y) {
if (x == 1) return y;
if (x < y) return normalnimproduct(y, x);
int M = 1 << (1 << (int) std::log2((int) std::log2(x)));
int d1 = nimproduct(x / M, y / M);
int d2 = nimproduct(x / M, y % M);
return (M * (d1 ^ d2)) ^ nimproduct(M >> 1, d1);
}
int normalnimproduct(int x, int y) {
int res = 0;
for (; x; x &= x - 1) res ^= nimproduct(x & -x, y);
return res;
}
其中 nimproduct 的 \(x\) 是二的幂。貌似存幂会跑得快一点。
根据 09论文 里，nimproduct 正确性证明如下：
我们保证 \(x \geq y\)，记 \(x = PM, y = SM + T\)，其中 \(M\) 是最大的满足 \(M < x\) 且为费马数的数。
显然有 \(P, S, T < M\)。然后有：
\[\begin{align*}
& (P \times M) \otimes (S \times M + T) \\
= & (P \otimes M) \otimes ((S \otimes M) \oplus T) \\
= & (M \otimes M \otimes P \otimes S) \oplus (M \otimes P \otimes T) \\
= & ((M \oplus \frac{M}{2}) \otimes P \otimes S) \oplus (M \otimes P \otimes T) \\
= & (M \otimes ((P \otimes S) \oplus (P \otimes T))) \oplus (\frac{M}{2} \otimes (P \otimes S)) \\
= & (M \times ((P \otimes S) \oplus (P \otimes T))) \oplus (\frac{M}{2} \otimes (P \otimes S))
\end{align*}
\]
& (P \times M) \otimes (S \times M + T) \\
= & (P \otimes M) \otimes ((S \otimes M) \oplus T) \\
= & (M \otimes M \otimes P \otimes S) \oplus (M \otimes P \otimes T) \\
= & ((M \oplus \frac{M}{2}) \otimes P \otimes S) \oplus (M \otimes P \otimes T) \\
= & (M \otimes ((P \otimes S) \oplus (P \otimes T))) \oplus (\frac{M}{2} \otimes (P \otimes S)) \\
= & (M \times ((P \otimes S) \oplus (P \otimes T))) \oplus (\frac{M}{2} \otimes (P \otimes S))
\end{align*}
\]
记 \(d1 = P \otimes S, d2 = P \otimes T\)，就有
\[x \otimes y = (M \times (d1 \oplus d2)) \oplus (\frac{M}{2} \otimes d1)
\]
\]
normalnimproduct 的正确性因为结合律显然。
然后这样写，就偷懒成功了（好记好写）。
实际上论文里另一个函数推法类似。反正如果考试遇到连预处理一个范围以内这种方法都跑不过的话，那就慢慢推常见做法吧。