luogu#P2148. [SDOI2009] E&D

    ID: 6196 远端评测题 1000ms 125MiB 尝试: 1 已通过: 0 难度: 5 上传者: 标签>博弈论枚举暴力树状数组状态压缩状压各省省选2009山东

[SDOI2009] E&D

题目描述

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

游戏的规则如下:桌子上有 2n2n 堆石子,编号为 12n1 \sim 2n。其中,为了方便起见,我们将第 2k12k-1 堆与第 2k2k 堆(1kn1 \le k \le n)视为同一组。第 ii 堆的石子个数用一个正整数 SiS_i 表示。

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

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

输入格式

本题有多组数据。

第一行一个整数 TT,表示数据组数。

对于每组数据:

第一行一个整数 NN,表示桌子上共有 NN 堆石子,这里的 NN 即为题目描述中的 2n2n

第二行 NN 个整数 S1NS_{1 \dots N}

输出格式

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

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

YES
NO

提示

对于 20%20\% 的数据,N=2N=2

对于另外 20%20\% 的数据,N4N \le 4Si50S_i \le 50

对于 100%100\% 的数据,1T201 \le T \le 201N2×1041 \le N \le 2 \times 10^4NN 为偶数,1Si2×1091 \le S_i \le 2 \times 10^9