Nim积的一种???的写法

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*}
\]

记 \(d1 = P \otimes S, d2 = P \otimes T\)，就有

\[x \otimes y = (M \times (d1 \oplus d2)) \oplus (\frac{M}{2} \otimes d1)
\]

normalnimproduct 的正确性因为结合律显然。

然后这样写，就偷懒成功了（好记好写）。

实际上论文里另一个函数推法类似。反正如果考试遇到连预处理一个范围以内这种方法都跑不过的话，那就慢慢推常见做法吧。

巴特西

Nim积的一种???的写法

最新文章

热门文章