EagleBear2002 的博客

这里必须根绝一切犹豫,这里任何怯懦都无济于事

P2148 [SDOI2009] E&D

$$ \def\xor{\text{ xor }} \def\mex{\mathrm{mex}} \def\SG{\mathrm{SG}} $$

题目描述

小 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

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

输出 #1

1
2
YES
NO

说明/提示

对于 $20%$ 的数据,$N=2$。

对于另外 $20%$ 的数据,$N \le 4$,$S_i \le 50$。

对于 $100%$ 的数据,$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$。容易打表得到下面的 $\SG(a,b)$ 函数:

1
2
3
4
5
6
7
8
9
10
11
12
  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 = \set{\SG(a,b) | a + b = i}$,用 bitset 表示 $S_i$,打表得到:

1
2
3
4
5
6
7
8
9
10
11
12
 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$ 的二进制表示。

于是,我们有: $$ \SG(a,b) = \mex\set{\SG(i,j)|i + j = a \lor i + j = b} = \mex\set{S_a \cup S_b} $$ 我们得到了 $O(\log b)$ 快速计算 $\SG(a,b)$ 的算法。