Nim积总不能一直打四次暴力吧！
用SG定理等东西，可以证明 ((N, oplus, otimes)) 构成一个域。（证明很难，我不会）
其中 (oplus) 为异或, (x otimes y = mathop{ extrm{mex}}_{1 leq i < x, 1 leq j < y} left{ (i otimes y) oplus (x otimes j) oplus (i otimes j) ight})，即暴力对子状态计算。
然后还有优美的性质，能使计算 (otimes) 做到 (O( extrm{poly} (log)))：
对于一个费马数 (M = 2^{2^a})，对于一个 (y)，有以下两个性质：
- (M otimes y = M imes 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)。然后有：
[egin{align*}
& (P imes M) otimes (S imes 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 imes ((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 imes (d1 oplus d2)) oplus (frac{M}{2} otimes d1)
]
normalnimproduct 的正确性因为结合律显然。
然后这样写，就偷懒成功了（好记好写）。
实际上论文里另一个函数推法类似。反正如果考试遇到连预处理一个范围以内这种方法都跑不过的话，那就慢慢推常见做法吧。