取石子

题解

在笔者写这篇题解之前，你可以发现，网上大部分流行的解法都是 $O\left(n\sum a\right)$ 的，但我们可以发现在 LOJ 的较快代码都是清一色的线性时间复杂度。
这篇题解将主要对这种线性的做法进行讲解。

首先我们抬出我们的结论:
我们记 $x=\sum [a_i=1]$ 即 $1$ 堆的个数， $y=\sum [a_i>1](a_i+1)-1$ ，也就是非 $1$ 堆的和。
当 $y\leqslant 2$ 时，如果 $3 ∣ x$ ，后手必胜，否则先手必胜。
当 $y > 2$ 时，如果 $2|x\wedge2|y$ ，后手必胜，否则先手必胜。

显然，不是 $1$ 的堆是不会对我们的答案产生影响的，它一定会做到最终被减到 $0$ 并且完全合（即自身合并的次数一定被用光）。
事实上，它不可能被任何一个人减到 $0$ ，如果有人妄图将它减到 $0$ ，浪费它的合并次数，那么当他将它从 $2$ 变到 $1$ ，是另一个人就会处于干扰对手的意愿，将其合并到它大于 $1$ 的朋友上，这也可以说明我们 $y$ 中最后要减去一个没处合并的 $1$ 。

显然，如果 $y\leqslant 2$ ，那么我们的序列必然是数个连续的 $1$ ，最后可能跟一个 $2$ 。
如果我们的 $3 ∣ x$ ，也就是说我们的 $1$ 的个数是 $3$ 的倍数。
如果我们的先手将一个 $1$ 变为 $0$ ，在有 $2$ 的情况下，后手可以将 $2$ 变成 $1$ ，在没 $2$ 的情况下，后手可以将两个 $1$ 变成 $2$ 。
如果先手将一个 $2$ 变成 $1$ ，后手将这个 $1$ 变成 $0$ 即可。
如果先手合并了两个 $1$ ，得到一个 $2$ ，那么在没 $2$ 的情况下，我们可以将一个 $1$ 消去，保持在原状态。
在有 $2$ 的情况，我们考虑现在 $x$ 的奇偶性没变， $y$ 的奇偶性变了，显然现在 $2\not | y$ ，因为现在它们多了一个可合并项，在 $y > 2$ 的情况看来，我们的后手现在是胜态。
于是，我们的目的有转到了证明 $y > 2$ 部分的结论是否成立，不妨先假设 $y > 2$ 部分的结论时对的，在下面会进行证明，先将 $y\leqslant 2$ 的情况说明完。
如果我们的 $3\not | x$ ，那么显然我们的先手可以将现在的情况变为 $3 ∣ x$ ，此时他是后手，可以胜利。
如果 $x\%3=1$ ，直接将这个 $1$ 减掉即可。
如果 $x\%3=2$ ，在有 $2$ 的情况下，可以将 $2$ 变成 $1$ ，没 $2$ 的情况下，将这两个 $1$ 合成 $2$ 。
于是我们便达到了 $3 ∣ x$ 的情况，原来的先手现在成了后手，必将胜利。

对于 $y > 2$ 的情况，我们先说明 $2|x\wedge 2|y$ 的情况后手是必胜的。
如果先手消一个 $1$ ，后手跟着消 $1$ 即可。
如果先手使 $y$ 减 $1$ ，如果现在 $y > 3$ ，后手让 $y$ 减 $1$ 即可。否则，如果前面有 $1$ 的话，一定是偶数个，我们合并两个 $1$ ，可以使 $y$ 变成 $6$ 。不然的话，整个序列中就一个 $3$ ，此时将这个 $3$ 变成 $2$ ，一个 $2$ 明显是后手必胜。
如果先手将一个 $1$ 合并到 $2$ 上，后手跟着合并一个 $1$ 即可。
如果先手将两个 $1$ 合成 $2$ ，此时 $y$ 会增加 $3$ ，后手使 $y$ 减 $1$ 即可。
这样，无论如何，我们的后手都有能与先手匹敌的方案。
如果 $2\not |x\vee 2\not |y$ ，先手是一定有一种方案使其变成 $2|x\wedge 2|y$ 的，此时作为后手的原来的先手胜利。
如果 $2\not | x\wedge 2|y$ ，先手可以直接消去一个 $1$ 。
如果 $x\wedge 2\not |y$ ，当 $y > 3$ 时，先手可以将 $y$ 减去一个 $1$ ，当 $y = 3$ 时，先手如果前面有 $1$ 就合并连个 $1$ ，否则将 $y$ 减 $1$ 。
如果 $2\not |x\wedge 2\not | y$ ，先手可以将一个 $1$ 合并到 $2$ 上面去。
于是，无论如何先手都能赢了。
这样，我们就证罢了 $y > 2$ 的情况了，那么 $y\leqslant 2$ 的情况也就证明完毕了。

于是，我们直接记录 $1$ 的个数与非 $1$ 的数的总和就可以线性求出答案了。
时间复杂度 $O\left(n\right)$ 。

源码

~~这还要看吗。~~

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 50055
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
#define lson (rt<<1)
#define rson (rt<<1|1)
typedef long long LL;
typedef unsigned long long uLL; 
typedef long double ld;
const int INF=0x3f3f3f3f;    
const int mo=998244353;
const int inv2=499122177;
const int jzm=233333333;
const int zero=100;
const int lim=200;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
const double eps=1e-5;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
	_T f=1;x=0;char s=getchar();
	while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
	x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1)t=1ll*t*a%p;a=1ll*a*a%p;s>>=1;}return t;}
int T,n,a[MAXN],sum,num;
signed main(){
	read(T);
	while(T--){
		read(n);num=sum=0;
		for(int i=1;i<=n;i++){
			read(a[i]);
			if(a[i]>1)sum+=a[i]+1;
			else num++;
		}
		if(sum)sum--;
		puts(Dp(num,sum)?"YES":"NO");
	}
	return 0;
}