抱歉cpy了一个，但我实在是懒得码了。

保证本文除实现部分外无信竞内容。

P2599 [ZJOI2009] 取石子游戏

题目描述

在研究过 Nim 游戏及各种变种之后，Orez 又发现了一种全新的取石子游戏，这个游戏是这样的：

有 $n$ 堆石子，将这 $n$ 堆石子摆成一排。游戏由两个人进行，两人轮流操作，每次操作者都可以从最左或最右的一堆中取出若干颗石子，可以将那一堆全部取掉，但不能不取，不能操作的人就输了。

Orez 问：对于任意给出一个初始一个局面，是否存在先手必胜策略。

输入格式

文件的第一行为一个整数 $T$，表示有 $T$ 组测试数据。对于每组测试数据：

第一行为一个整数 $n$，表示有 $n$ 堆石子。

第二行为 $n$ 个整数 $a_1, a_2, \ldots , a_n$，依次表示每堆石子的数目。

输出格式

对于每组测试数据仅输出一个整数 $0$ 或 $1$。其中 $1$ 表示有先手必胜策略，$0$ 表示没有。

输入输出样例 #1

输入 #1

1
4
3 1 9 4

输出 #1

0

说明/提示

对于 $30 \%$ 的数据，$n \le 5$，$a_i \le {10}^5$。
对于 $100 \%$ 的数据，$1 \le T \le 10$，$1 \le n \le 1000$，$1 \le a_i \le {10}^9$。

神仙题啊。会讲的比较详细，这部分讲解内容也会比较长，希望你能耐心看完哦。（如果你并不想了解其本质，只是想水黑的话，可以选择直接跳过推导部分看最后的转移结论和代码，虽然我并不建议这么做。）

首先有一个很厉害的状态定义，令 $\text{L}(i,j)$ 表示在区间 $[i,j]$ 的左侧加上一堆数量为 $\text{L}(i,j)$ 的石子后该局面为必败状态，即 $(\text{L}(i,j),a_i,a_{i+1},\dots,a_j)$ 为必败状态。$\text{R}(i,j)$ 的定义同理。

由于 $\text{L}$ 与 $\text{R}$ 在定义、推导、转移等各个方面都是类似的，为了避免文章过于冗长，这边仅以 $\text{L}$ 举例，$\text{R}$ 的内容同理，看懂了其中一个另外一个就很简单了。

对于 $\text{L}$，有两个重要的性质：存在性和唯一性。将给出这两个性质的证明。

1. $\text{L}(i,j)$ 的存在性证明：

   • 用反证法。
     假设不存在满足定义的 $\text{L}(i,j)$，则对于任意非负整数 $x$，$(x,a_i,a_{i+1},\dots,a_j)$ 都是必胜局面。
     由于该局面为必胜局面，则一定能一步转移到某个必败局面。
     若拿的是左边一堆，则不可能变为必败局面，因为其局面状态与当前局面是同一类，根据假设应均为必胜状态。
     于是只能拿右边一堆，设当前局面能一步到达的某个必败局面为 $(x,a_i,a_{i+1},\dots,a_{j-1},y)$，要求 $0 \le y < a_j$。
     由于 $x$ 有无限个，而 $y$ 只有 $a_j$ 个，由抽屉原理，一定存在 $x_1 > x_2$ 满足 $(x_1,a_i,a_{i+1},\dots,a_{j-1},y)$ 和 $(x_2,a_i,a_{i+1},\dots,a_{j-1},y)$ 都是必败状态，而这两个状态之间实际上一步可达，矛盾！故原命题成立。

2. $\text{L}(i,j)$ 的唯一性证明：

   • 还是用反证法。
     假设 $\text{L}(i,j)$ 不唯一，则必存在 $x_1 > x_2$ 使 $(x_1,a_i,a_{i+1},\dots,a_j)$ 和 $(x_2,a_i,a_{i+1},\dots,a_j)$ 都是必败状态，而这两个状态之间实际上一步可达，矛盾！故原命题成立。

这样，我们就证明了 $\text{L}(i,j)$ 的存在性和唯一性，也就能得到一个看似没啥用实则还是有用的结论：对于 $x \not= \text{L}(i,j)$，局面 $(x,a_i,a_{i+1},\dots,a_j)$ 都是必胜状态。

嗯，说了这么多，终于要开始状态转移了！

DP 一定要有边界情况，这里的边界情况就是 $L(i,i) = a_i$，因为后手永远可以模仿先手的操作以保证两个子游戏状态一模一样从而导致先手必败。

然后就是具体的转移了。$\text{L}(i,j)$ 的答案由 $\text{L}(i,j-1)$ 和 $\text{R}(i,j-1)$ 转移而来。

为了方便，我们令 $L = \text{L}(i,j-1) , R = \text{R}(i,j-1) , x = a_j$。

转移时需要分类讨论：

1. $x = R$ 时：$\text{L}(i,j) = 0$。

   • 这个是最简单的一种情况——由 $\text{R}(i,j-1)$ 的定义，$(a_i,a_{i+1},\dots,a_j)$ 自身就是必败状态，因此右侧不需要添加任何石子堆。

2. $x < L$ 且 $x < R$（即 $x < \min(L,R)$）时：$\text{L}(i,j) = x$。

   • 要做的就是证明 $(x,a_i,a_{i+1},\dots,a_{j-1},x)$ 为必败局面。
     由于最左边一堆和最右边一堆的石子数相同，后手可先与先手在相对堆上做相同操作，直到某个时刻后手得到形如 $(y,a_i,a_{i+1},\dots,a_{j-1})$ 或 $(a_i,a_{i+1},\dots,a_{j-1},y)$ 的局面，此时因 $0 < y \le x < \min(L,R)$，结合 $\text{L}(i,j-1)$ 及 $\text{R}(i,j-1)$ 的定义知此时是必胜局面，即先手必败，得证。

3. $L \le x < R$ 时：$\text{L}(i,j) = x + 1$。

   • 如果先手先拿左边一堆，设拿了以后还剩 $z$ 枚石子：
     若 $z > L$，则后手可以将最右边拿成 $z-1$ 枚石子，就能回到第三种情况本身，递归证明即可。
     若 $z = L$，则后手将最右边拿完，根据 $\text{L}(i,j-1)$ 的定义知此局面先手必败。
     若 $0 < z < L$，则后手将最右边拿成 $z$ 枚石子，由第二种情况知此时先手必败。
     若 $z=0$，此时最右边石子数 $k$ 满足 $L \le k < R$，结合 $\text{R}(i,j-1)$ 知此局面必胜，即对于先手来说必败。
     如果先手先拿右边一堆，设拿了以后还剩 $z$ 枚石子：
     若 $z \ge L$，则后手可以将最左边拿成 $z+1$ 枚石子，回到其本身，递归证明。
     若 $0 < z < L$，则后手将最左边拿成 $z$ 枚石子，由第二种情况知此时先手必败。
     若 $z = 0$，则后手将最左边拿成 $L$ 枚石子，由 $\text{L}(i,j-1)$ 的定义知此局面先手必败。

4. $R < x \le L$ 时：$\text{L}(i,j) = x - 1$。

   • 证明与上一种（第三种情况）是类似的，可以先尝试自己证一下。
     如果先手先拿左边一堆，设拿了以后还剩 $z$ 枚石子：
     若 $z \ge R$，则后手可以将最右边拿成 $z+1$ 枚石子，就能回到第四种情况本身，递归证明即可。
     若 $0 < z < R$，则后手将最右边拿成 $z$ 枚石子，由第二种情况知此时先手必败。
     若 $z=0$，则后手将最右边拿成 $R$ 枚石子，由 $\text{R}(i,j-1)$ 的定义知先手必败。
     如果先手先拿右边一堆，设拿了以后还剩 $z$ 枚石子：
     若 $z > R$，则后手可以将最左边拿成 $z-1$ 枚石子，回到其本身，递归证明。
     若 $z = R$，则后手把最左边拿完，根据 $\text{R}(i,j-1)$ 的定义知此局面先手必败。
     若 $0 < z < R$，则后手将最左边拿成 $z$ 枚石子，由第二种情况知此时先手必败。
     若 $z = 0$，此时最左边石子数 $k$ 满足 $0 < k < L$，结合 $\text{L}(i,j-1)$ 的定义知此局面必胜，即对于先手来说必败。

5. $x > L$ 且 $x > R$（即 $x > \max(L,R)$）时：$\text{L}(i,j) = x$。

   • 设先手将左右两堆中其中一堆拿成了 $z$ 枚石子。
     若 $z > \max(L,R)$，回到第五种情况本身，递归证明。
     若 $0 < z < \min(L,R)$，后手把另一堆也拿成 $z$ 回到第二种情况，先手必败。
     若 $z=0$ 将另一堆拿成 $L$ 或 $R$ 个即可。
     剩下的就是 $L \le z \le R$ 或 $R \le z \le L$，第三种情况可以解决最左边 $L < z \le R$ 及最右边 $L \le z < R$ 的状态，第四种情况可以解决最左边 $R \le z < L$ 及最右边 $R < z \le L$ 的状态，因此只剩最左边 $z = L$ 和最右边 $z = R$，而这两种情况下只需把另一堆拿完即可由 $\text{L}(i,j-1)$ 或 $\text{R}(i,j-1)$ 的定义证明。

综上，我们得到了整个 $\text{L}(i,j)$ 在所有情况下的转移式：

$$\text{L}(i,j) = \begin{cases} 0, & x=R \\ x+1, & L \le x < R \\ x-1, & R < x \le L \\ x , & \text{otherwise}. \end{cases}$$

同理能求 $\text{R}$，具体推导过程不放了（码字好累的 TAT，而且基本是一样的内容啊），这里放出最后的转移式（注意这里的 $L = \text{L}(i+1,j) , R = \text{R}(i+1,j) , x = a_i$）：

$$\text{R}(i,j) = \begin{cases} 0, & x=L \\ x+1, & R \le x < L \\ x-1, & L < x \le R \\ x , & \text{otherwise}. \end{cases}$$

回到本题最后要求输出的内容，只有当 $\text{L}(2,n) = a_1$ 时先手无必胜策略，否则都是先手必胜哦！

总时间复杂度是 $O(n^2)$ 的，求 $\text{L}$ 和 $\text{R}$ 的过程是区间 DP。

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 1005;
int T,n,a[N],L[N][N],R[N][N];
int read(){
    int su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}

int main(){
    T=read();
    while(T--){
        n=read();
        for(int i=1;i<=n;i++)
            a[i]=read(),L[i][i]=a[i],R[i][i]=a[i];
        for(int len=2;len<=n;len++)
            for(int i=1;i+len-1<=n;i++){
                int j=i+len-1,x=a[j];
                int l=L[i][j-1],r=R[i][j-1];
                if(x==r)L[i][j]=0;
                else if(l<=x&&x<r)L[i][j]=x+1;
                else if(r<x&&x<=l)L[i][j]=x-1;
                else L[i][j]=x;
                l=L[i+1][j],r=R[i+1][j],x=a[i];
                if(x==l)R[i][j]=0;
                else if(r<=x&&x<l)R[i][j]=x+1;
                else if(l<x&&x<=r)R[i][j]=x-1;
                else R[i][j]=x;
            }
        cout<<(L[2][n]!=a[1])<<"\n";
    }
    return 0;
}