题目简述：

$n$ 堆石子排成一排，每次可以从最左或最右的一堆中取若干，不能不取。两人轮流操作，不能操作的就输了。对于给定的一个初始局面，是否存在先手必胜策略？

思路：

比较容易想到的是，如果两端石子相同时，先手必败。这是因为无论先手做什么操作，后手只需要做与之对称的操作就可以了，最后拿光石子的一定是后手。那么对于先手自身来讲，使其必胜的状态就是能够使两端石子相同的状态，这样就可以先发制人，使后手面对刚才说过的局面。

与之前做过的其他题目有一个显著的不同在于，这道题只允许玩家从两端取石子，在两端的石子取完之前中间的石子状态并不会发生改变。两端的石子的确可以决定玩家的状态，但生活总不是风平浪静，两端的石子被取完后，曾经的优势者也可能面临着劣势局面 —— 如何力挽狂澜是他需要考虑的事情，而对于我们来讲，不仅需要考虑能操作范围内 (即两端) 石子的状态，更要考虑现在能操作的石子与未来要操作的石子之间的关系，考虑 DP。

不妨先做一些规定吧：$l_{i,j}$ 表示先手必败时中间石子形成的闭区间 $[i,j]$ 左端的石子数，$r_{i,j}$ 表示先手必败时闭区间 $[i,j]$ 右端的石子数，$a_i$ 表示 $i$ 位置的石子数。值得注意的是，前两个条件不仅限制了两端的石子数，还限制了游戏中剩余所有石子的范围 —— 换句话说，只有除去两端石子，剩下的石子正好是闭区间 $[i,j]$ 时，$l_{i,j}$ 和 $r_{i,j}$ 才会生效。

首先，如果 $l_{i,j}$ 和 $r_{i,j}$ 存在，那它们一定是唯一的。假设 $l_{i,j}$ 有两个值 $l_1$ 和 $l_2$ ( $l_1>l_2$ )，那么当最左端的石子数量为 $l_1$ 时，先手本应必败，但是他可以将最左端石子拿成 $l_2$，局面变为后手必败，与前边先手必败矛盾。其次，$l_{i,j}$ 和 $r_{i,j}$ 一定都存在。假设 $l_{i,j}$ 不存在，那么无论最左端有多少石子都是必胜态。拿左边的石子显然是徒劳的，因为不管剩下多少都一定是必胜态，所以先手拿右边的石子。现在先手拿了右边的石子使得后手必败，那么后手无论从左边拿多少都必败，与「无论最左端有多少石子都是必胜态」矛盾。综上，$l_{i,j}$ 和 $r_{i,j}$ 存在且唯一。

Case0：边界 $[i,i]$

$l_{i,j}=r_{i,j}=a_i$，最开始已经说过了，两端石子相同时先手必败。

Case1：$a_j=r_{i,j-1}$

最右边的石子已经满足了先手必败时的条件，先手必败。

Case2：$a_j<l_{i,j-1},\ a_j<r_{i,j-1}$

此时有 $l_{i,j}=a_j$，又构成了最开始说的情况：最右端的石子是 $a_j$，那么最左端的石子和最右端对称的时候先手必败。

Case3：$a_j≥l_{i,j-1},\ a_j<r_{i,j-1}$

此时有 $l_{i,j}=a_j+1$。如果先手取左侧：

• 若剩余石子大于 $l_{i,j-1}$，后手只需要在右侧取相同数量的石子就可以循环回到 Case3。
• 若剩余石子等于 $l_{i,j-1}$，后手只需要取完右端所有石子，触发 $a_{i-1}=l_{i,j-1}$ 的先手必败状态。
• 若剩余石子小于 $l_{i,j-1}$，后者只需要取右端石子直至与左端相等，则回到 Case2。由于有 $a_j≥l_{i,j-1}$，所以先手取完时一定有 $a_j≥l_{i,j-1}≥a_{i-1}$。

如果先手取右侧：

• 若剩余石子大于 $l_{i,j-1}$，后手只需要在左侧取石子直至比右端多一就可以回到 Case3。
• 若剩余石子等于 $l_{i,j-1}$，后手只需要在左侧取石子直至比右端多一就可以回到 Case3。
• 若剩余石子小于 $l_{i,j-1}$，后手只需要在左侧取石子直至与右端相等，则回到 Case2。

Case4：$a_j≤l_{i,j-1},\ a_j>r_{i,j-1}$

此时有 $l_{i,j}=a_j-1$。如果先手取左侧：

• 若剩余石子大于 $r_{i,j-1}$，后手只需要在右侧取石子直至比左端多一就可以回到 Case4。
• 若剩余石子等于 $r_{i,j-1}$，后手只需要在右侧取石子直至比左端多一就可以回到 Case4。
• 若剩余石子小于 $r_{i,j-1}$，后者只需要取右端石子直至与左端相等，则回到 Case2。

如果先手取右侧：

• 若剩余石子大于 $r_{i,j-1}$，后手只需要在左侧取相同数量的石子就可以循环回到 Case3。
• 若剩余石子等于 $r_{i,j-1}$，后手只需要取完左端所有石子，触发 $a_{j}=r_{i,j-1}$ 的先手必败状态。
• 若剩余石子小于 $r_{i,j-1}$，后者只需要取左端石子直至与右端相等，则回到 Case2。

Case5：$a_j≥l_{i,j-1},\ a_j>r_{i,j-1}$

此时有 $l_{i,j}=a_j$。无论先手取哪一侧：

• 若剩余石子小于 $l_{i,j-1}，r_{i,j-1}$，一定可以回到 Case2。
• 若剩余石子大于 $l_{i,j-1}，r_{i,j-1}$，一定可以回到 Case5。
• 若剩余石子等于 $l_{i,j-1}，r_{i,j-1}$，后手可以通过在另一堆取石子回到 Case4 或 Case3。

上面的五个 Case 对称过来就是其他的方案，方案类似不再赘述。最后只需要判断 $a_1$ 是否等于 $l_{2,n}$

Code：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<climits>
#include<algorithm>
#include<utility>
#define int long long
using namespace std;
const int MaxN=1003;
int lL[MaxN][MaxN], rR[MaxN][MaxN], a[MaxN];

inline int Read(){
	int num = 0, op = 1;
	char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') op = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		num = num * 10 + ch - '0';
		ch = getchar();
	}
	return num * op;
}

signed main(){
	int T = Read();
	while(T--){
		int n = Read();
		for(int i=1;i<=n;++i)
			a[i] = Read(), lL[i][i] = rR[i][i] = a[i];
		for(int len=1; len<n; len++){
			for(int l=1,r=l+len; r<=n; l++,r++){
				int x, L, R;
				x = a[r], L = lL[l][r-1], R = rR[l][r-1];
				if(x == R) lL[l][r] = 0;
				else if(x > R && x > L || x < R && x < L) lL[l][r] = x;
				else if(x >= L && x < R) lL[l][r] = x + 1;
				else if(x > R && x <= L) lL[l][r] = x - 1;
				x = a[l], L = lL[l+1][r], R = rR[l+1][r];
				if(x == L) rR[l][r] = 0;
				else if(x > R && x > L || x < R && x < L) rR[l][r] = x;
				else if(x > L && x <= R) rR[l][r] = x - 1;
				else if(x >= R && x < L) rR[l][r] = x + 1;
			}
		}
		if(a[1]==lL[2][n]) printf("0\n");
		else printf("1\n");
	}
	return 0;
}