咕咕咕

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

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$。

神仙题。

首先有一个神仙的状态定义：定义 $L(i,j)$ 和 $R(i,j)$ 分别为在区间 $[i,j]$ 的左侧和右侧加一堆数量为其的石子后必败，由于这两者事实上完全对称，下文只讨论 $L(i,j)$。

先证明唯一性和存在性：

唯一性是简单的，考虑反证，若存在不止一个，其中必有两个状态可达且均必败，矛盾。

证明存在性，依然考虑反证，若不存在，则 $\forall x$，均有 $(x,a_i,...,a_j)$ 必胜，那么，其必可以一步转移到必败状态。

若取左边的石子，则仍属于同一类状态，据假设，矛盾。

故只能取右边的石子，即 $\exist y$ 令 $(x,a_i,...,a_{j-1},y)$，而合法的 $x$ 有无数个，$y$ 则只有 $a_j$ 个 $(0\le x<a_j)$，据抽屉原理，$\exist x1>x2$ 令这两个 $y$ 相同，而其一步可达且均必败，矛盾。

综上，有且只有一个 $L(i,j)$ 合法。

接下来，要进行正式的状态转移了。

让我咕咕咕