思路与算法

各堆不能独立取，只有两端能够操作。定义f(A)：在序列A左侧额外放一堆x（x=0视为省略），使整个局面成为必败态的唯一非负整数x。空序列的f为0。f(A)=0恰表示A本身必败。

若A本身必败，则x=0是唯一解。否则，x=0是必胜态；当x>0时，合法操作只有减小x，或从A最右堆取石得到序列B。后者能一步变成必败态，当且仅当x=f(B)。因此f(A)是这些f(B)中最小缺失的正整数。这个阈值用于识别败态，并非各堆独立的SG值。

为避免枚举至10^9，固定前缀P，令r=f(P)、q=f(reverse(P))，并考察把大小z的堆接在P末端后的f值。z=0时值为r；z=q时整个序列必败，值为0；其他z>0的值依次是尚未出现的最小正整数。r与q同时为0或同时非0，因为局面胜负不随左右翻转改变。若q=0，结果为z。若z=q，结果为0。否则令j=z-1（z>q时）或j=z（z<q时），返回第j个排除r的正整数：j<r时为j，否则为j+1。

建立F[i][j]=f(a_i..a_j)、G[i][j]=f(reverse(a_i..a_j))。单点均为a_i。按区间长度递增：F[i][j]=step(F[i][j-1],G[i][j-1],a_j)，G[i][j]=step(G[i+1][j],F[i+1][j],a_i)。最终F[0][n-1]为0则输出0，否则输出1。

正确性说明

先证明阈值定义成立。x=0若必败，所有x>0都能取空额外左堆回到该败态，所以无第二个解。若x=0必胜，右端操作所得B有限，记其阈值集合为S。取最小不在S内的正数x。所有更小正整数y都属于S，因而能经右端操作到某个阈值等于y的败态；y=0也已知必胜。因此从当前x减小左堆只能到必胜态，右端操作也因x不属于S而只能到必胜态，故该x必败。所有更大的额外左堆可降到x而必胜。这既给出存在性，也给出唯一性。归纳可按总石子数进行，因为每步总数严格减少。

再证明压缩公式。序列P+[z]的胜负，翻转后等于[z]+reverse(P)，所以它恰在z=q时必败，f值恰在该位置为0。z=0时相当于删去最右堆，f值是r。每个其他正z的右端后继恰为P+[b]，其中0<=b<z，因此其f值是此前值中最小缺失正数。于是从正z起，除唯一的q位置强制为0外，其他位置按正整数升序使用且跳过已被r占据的值。当q=0时r也为0，故直接得到z；否则z之前是否越过q决定正值序号j，跳过r又决定j或j+1。step公式因此正确。

F、G的递推只引用更短区间，单点f([a])=a（两堆相等时败，亦可由上述公式从空前缀推出）。按长度归纳，每个双方向阈值均正确。最后f(A)=0与原局面必败等价，故输出正确。

复杂度

单组分配和清零两张N乘N的int表O(N²)，读取与对角线初始化O(N)。每个区间两个常数时间转移，总时间O(N²)，额外空间O(N²)。多组总时间为各组N²之和。阈值公式的结果最多为对应端点石子数加1，使用较宽松的max(a)+N界也小于32位有符号上限；不把10^9展开成状态。

易错点

1. 只可从最左或最右堆取石，取数为任意正数；不能把中间堆直接当作Nim子游戏。
2. q=0、z=q、z小于q及z大于q都要分别处理；正mex排除的是已出现r，不能用普通含0的mex替代。
3. F、G含义不同，G转移来自右侧子区间并用左端a_i，不能把两方向数组混用。
4. 输入正石子数；0堆只用于阈值定义中省略额外堆，不扩展原输入为任意中间空堆。
5. 代码输出是0或1。覆盖单堆、左右翻转、重复端点、1与10^9、T=10且每组N=1000，完整小状态胜负与阈值均经独立穷举。

参考代码（C++11）

#include <iostream>
#include <vector>
using namespace std;
int step(int r, int q, int z) {
    if (q == 0)
        return z;
    if (z == q)
        return 0;
    int j = z - (z > q);
    return j + (j >= r);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int &x : a)
            cin >> x;
        vector<vector<int>> F(n, vector<int>(n)), G(n, vector<int>(n));
        for (int i = 0; i < n; ++i)
            F[i][i] = G[i][i] = a[i];
        for (int len = 2; len <= n; ++len)
            for (int i = 0; i + len <= n; ++i) {
                int j = i + len - 1;
                F[i][j] = step(F[i][j - 1], G[i][j - 1], a[j]);
                G[i][j] = step(G[i + 1][j], F[i + 1][j], a[i]);
            }
        cout << (F[0][n - 1] != 0) << '\n';
    }
}