取石子游戏
Solution
由于本人水平极低，所以觉得此题难死了。
通过看题解不难发现，对于一段区间
[L,R]，若
L+1 到
R每堆石子个数确定，那么使得这段区间上先手必败的
a[l]有且只有一个。
证明非常的容易。首先假设没有先手必败的
a[L]，那么所有的必胜态都会到一个必胜态，显然是不可能的。如果有
\geq 2个必败态，考虑其中任意两个
x,y,x>y，那么先手显然可以把
x取成
y，那么
x就是一个必胜态。矛盾。
于是，我们定义
left[i][j]表示在
[L,R]区间左边添多少个变成一个必败态，
right[i][j]表示在右边添多少个。那么答案就是
left[2][n]!=a[1]。现在考虑如何求
left[l][r]。设
L=left[l][r-1],R=right[l][r-1],X=a[r]我们可以分以下几种情况讨论。
- R=X\Rightarrow left[l][r]=0。
- X< L \land X< R\Rightarrow left[l][r]=X。对于这种情况，我们发现无论左右两边被怎么取，都不会达到[l,r-1]的必败态，所以在一个人取完之后，另外一个人就一定处于必胜态。因为两边都是X个，所以后手一定比先手后取完。故后手必胜。同时我们可以发现，如果左右两边两堆相同且都小于L,R，那么一定后手必胜。
- L>R\land R。
- 首先当R=X-1时，可以发现如果先手把右边那堆取成X-1，那么后手只需要把左边那堆取成0即可。否则先手一定会把其中一堆取成小于X-1，那么后手就可以把另外一堆取得和先手取的那一堆一样。于是就变成了上面那种情况了。
- 如果R，
- 先手如果把其中一堆取到小于R的话，后手只需要把另一堆变得和先手取的那堆一样又变成了两边相同的情况。
- 如果先手把其中一堆取到R，后手直接把另一堆取完。
- 否则，如果先手把其中一堆取到>R，后手只需要取到保持左边那堆=右边那堆-1，就又递归回到了同样的情况。操作多次后，先手会取到前面两种情况中的一种，于是后手必胜。
- L。方法与上面那种情况相同。
- L。
- 当L=R时，后手只需要在先手把其中一堆取到L的时候把另一堆取完，其他时候保持两堆相同即可。
- 当L\ne R时，不妨设L>R。后手会有以下几种操作。
- 先手把左边取到L或把右边取到R时，后手把另外一边拉满。
- 先手把左边取到R时，后手把右边取到R+1。
- 先手把右边取到L时，后手把左边取到L-1。这时倘若先手跟着后手一步一步走，总有一天会取到R+1，此时后手那堆取到了R。于是先手只好跳过R直接取R-1，就变成了最后一种操作情况了。否则先手必定有一次操作使得后手那一堆的个数大于自己操作的这一堆的个数，于是也变成了最后一种情况。
- 剩下的时候保持两堆个数相同。
至此，我们考虑了所有的情况，对于
right[l][r]的处理方式和
left[l][r]对称。于是可以通过
n^2Dp完美地解决了此题。