P2148 [SDOI2009] E&D

$$$$

题目描述

小 E 与小 W 进行一项名为 E&D 游戏。

游戏的规则如下：桌子上有 $2n$ 堆石子，编号为 $1\sim 2n$。其中，为了方便起见，我们将第 $2k-1$ 堆与第 $2k$ 堆（$1\le k\le n$）视为同一组。第 $i$ 堆的石子个数用一个正整数 $S_i$ 表示。

一次分割操作指的是，从桌子上任取一堆石子，将其移走。然后分割它同一组的另一堆石子，从中取出若干个石子放在被移走的位置，组成新的一堆。操作完成后，所有堆的石子数必须保证大于 $0$。显然，被分割的一堆的石子数至少要为 $2$。两个人轮流进行分割操作。如果轮到某人进行操作时，所有堆的石子数均为 $1$，则此时没有石子可以操作，判此人输掉比赛。

小 E 进行第一次分割。他想知道，是否存在某种策略使得他一定能战胜小 W。因此，他求助于小 F，也就是你，请你告诉他是否存在必胜策略。例如，假设初始时桌子上有 $4$ 堆石子，数量分别为 $1,2,3,1$。小 E 可以选择移走第 $1$ 堆，然后将第 $2$ 堆分割（只能分出 $1$ 个石子）。接下来，小 W 只能选择移走第 $4$ 堆，然后将第 $3$ 堆分割为 $1$ 和 $2$。最后轮到小 E，他只能移走后两堆中数量为 $1$ 的一堆，将另一堆分割为 $1$ 和 $1$。这样，轮到小 W 时，所有堆的数量均为 $1$，则他输掉了比赛。故小 E 存在必胜策略。

输入格式

本题有多组数据。

第一行一个整数 $T$，表示数据组数。

对于每组数据：

第一行一个整数 $N$，表示桌子上共有 $N$ 堆石子，这里的 $N$ 即为题目描述中的 $2n$。

第二行 $N$ 个整数 $S_{1\dots N}$。

输出格式

对于每组数据，如果小 E 必胜，则一行一个字符串 YES，否则一行一个字符串 NO。

输入输出样例 #1

输入 #1

2
4
1 2 3 1
6
1 1 1 1 1 1

输出 #1

YES
NO

说明/提示

对于 $20\mathrm{\%}$ 的数据，$N=2$。

对于另外 $20\mathrm{\%}$ 的数据，$N\le 4$，$S_i\le 50$。

对于 $100\mathrm{\%}$ 的数据，$1\le T\le 20$，$1\le N\le 2\times {10}^4$ 且 $N$ 为偶数，$1\le S_i\le 2\times {10}^9$。

题解

容易发现每组两堆石子都是一个独立的 ICG，因此我们可以单独考虑每个 ICG。

对于每组两堆石子 $(a,b)$，不妨设 $a<b$。容易打表得到下面的 $\mathrm{SG}(a,b)$ 函数：

  0  1  2  3  4  5  6  7  8  9 10
---------------------------------
 1:  0  1  0  2  0  1  0  3  0  1
 2:  1  1  2  2  1  1  3  3  1
 3:  0  2  0  2  0  3  0  3
 4:  2  2  2  2  3  3  3
 5:  0  1  0  3  0  1
 6:  1  1  3  3  1
 7:  0  3  0  3
 8:  3  3  3
 9:  0  1
10:  1

令 $S_i=\{\mathrm{SG}(a,b)|a+b=i\}$，用 bitset 表示 $S_i$，打表得到：

 i    109876543210
------------------
 1:SG0 00000000000
 2:SG1 00000000001
 3:SG0 00000000010
 4:SG2 00000000011
 5:SG0 00000000100
 6:SG1 00000000101
 7:SG0 00000000110
 8:SG3 00000000111
 9:SG0 00000001000
10:SG1 00000001001

容易发现，$S_i$ 其实就是 $i-1$ 的二进制表示。

于是，我们有：

$$\mathrm{SG}(a,b)=\mathrm{mex}\{\mathrm{SG}(i,j)|i=j=a\vee i+j=b\}=\mathrm{mex}\{S_a\cup S_b\}$$

我们得到了 $O(\log b)$ 快速计算 $\mathrm{SG}(a,b)$ 的算法。