Description
在研究过Nim游戏及各种变种之后，Orez又发现了一种全新的取石子游戏，这个游戏是这样的： 有n堆石子，将这n堆石子摆成一排。游戏由两个人进行，两人轮流操作，每次操作者都可以从最左或最右的一堆中取出若干颗石子，可以将那一堆全部取掉，但不能不取，不能操作的人就输了。 Orez问：对于任意给出一个初始一个局面，是否存在先手必胜策略。
Input
文件的第一行为一个整数T，表示有 T组测试数据。对于每组测试数据，第一行为一个整数n，表示有n堆石子；第二行为n个整数ai，依次表示每堆石子的数目。
Output
对于每组测试数据仅输出一个整数0或1。其中1表示有先手必胜策略，0表示没有。
Sample Input
1
4
3 1 9 4
Sample Output
0
数据范围
对于30%的数据 n≤5 ai≤105
对于100%的数据 T≤10 n≤1000 每堆的石子数目≤109
Solution
重要性质：
- 对于一段区间 ([L,R]) ，若 (L+1) 到 (R) 的石子固定，那么让当前先手在这段区间上必败的 (a_L) 有且只有一个。 pause
证明唯一：如果有两个必败态，那么由于其中一个必败态可以转移到另一个必败态，与定义矛盾，所以只会有一个必败态
证明存在：如果左边没有必败态，那么左边所有的必胜态都由右边的必败态转移过来。由于左边的石子可以有任意多个，但右边的石子是固定的，所以会有石子对应多个必败态，这与唯一性矛盾
根据这两条性质，得出一个做法
设 (L[i][j]) 代表区间 ([i,j]) 左边加上一堆数量为 (L[i][j]) 的石子后先手必败；(R[i][j]) 定义相似，代表右边
最后只要判断 (L[2][n]) 是否等于 (a[1]) 就知道先手是否有必胜策略
考虑计算这两个数组：发现 (L[i][j]) 只与 (L[i][j-1],R[i][j-1]) 和 (a[j]) 有关
令 (l=L[i][j-1],r=R[i][j-1],x=a[j])
分情况讨论
-
边界条件，(L[i][i]=R[i][i]=a[i])
-
(r=x) ，已经确定先手必败，(L[i][j]=0)
-
(x le l) 且 (x le r) ，(L[i][j]=x) 。后手要做的就是在另一边取与先手一样数量的石子，这样先手一定先取完一堆。假设先手取完的是右边一堆，那么根据我们的 (l=L[i][j-1]) ，含义是区间 ([i,j-1]) 左边加上数量为 (l) 的石子先手必败，可以把当前局面等价于先手已经把数量为 (l) 的这堆石子取了一些了，所以先手必败
-
(r le x leq l) ，(L[i][j]=x-1) 。假设先手拿的左边一堆，拿到 (y) 个。若 (y le r) ，那么后手在右边一堆也拿到 (y) 个，变成上面一种情况；若 (y > r) ，那么后手拿到 (y+1) ，变成当前情况递归。假设先手拿右边一堆，拿到 (y) 个。若 $ y le r$ 那么后手在左边一堆也拿到 (y) 个，变成上面一种情况；若 (y=r) ，后手直接取完左边一堆，由于 (R[i][j-1]=r) ，所以先手必败；若 (y > r) ，那么后手将左边一堆取到 (y-1) ，变成这种情况递归。无论何种走向，最后只能是先手必败
-
(l le x leq r) ，(L[i][j]=x+1) 。类似于上面一种情况
-
(x > l) 且 (x > r) ，(L[i][j]=x) 。假设先手取其中一堆到 (y) 个。若 (y > l,r) ，那么变成这种情况递归；若 (y le l,r) ，那么变成第二种情况；剩下的情况后手相应取到 (y+1) 或 (y-1) ，变成上面两种情况中的一种就好了
(L[i][j]) 的所有情况都讨论完了，(R[i][j]) 的求法类似。
复杂度 (O(Tn^2))
#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define ft first
#define sd second
#define pb(a) push_back(a)
#define PII std::pair<int,int>
#define PLL std::pair<ll,ll>
#define mp(a,b) std::make_pair(a,b)
#define ITR(a,b) for(auto a:b)
#define REP(a,b,c) for(register int a=(b),a##end=(c);a<=a##end;++a)
#define DEP(a,b,c) for(register int a=(b),a##end=(c);a>=a##end;--a)
const int MAXN=1000+10;
int n,a[MAXN],L[MAXN][MAXN],R[MAXN][MAXN];
template<typename T> inline void read(T &x)
{
T data=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
x=data*w;
}
template<typename T> inline void write(T x,char ch=' ')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
if(ch!=' ')putchar(ch);
}
template<typename T> inline bool chkmin(T &x,T y){return y<x?(x=y,true):false;}
template<typename T> inline bool chkmax(T &x,T y){return y>x?(x=y,true):false;}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
int main()
{
int T;read(T);
while(T--)
{
int n;read(n);
REP(i,1,n)read(a[i]),L[i][i]=R[i][i]=a[i];
REP(len,2,n)REP(i,1,n-len+1)
{
int j=i+len-1,l,r,x;
l=L[i][j-1],r=R[i][j-1],x=a[j];
if(r==x)L[i][j]=0;
else if(r<x&&x<=l)L[i][j]=x-1;
else if(l<x&&x<=r)L[i][j]=x+1;
else L[i][j]=x;
l=L[i+1][j],r=R[i+1][j],x=a[i];
if(l==x)R[i][j]=0;
else if(l<x&&x<=r)R[i][j]=x-1;
else if(r<x&&x<=l)R[i][j]=x+1;
else R[i][j]=x;
}
puts(L[2][n]==a[1]?"0":"1");
}
return 0;
}