P13309 演剧

对于这样的不好做，不如先考虑二分答案，这样只需要考虑全为 \(0\) 或 \(1\) 的情况，之后只需要考虑是否有情况能留下 \(1\)。考虑朴素 \(f(l,r,p\in 0/1)\) 表示操作 \([l,r]\) 的人希望最后为 \(0\) 还是为 \(1\)能否成功。那么有转移：

\[f(l,r,p)=[\exists i,f(l,i,1-p)=f(i+1,r,1-p)=0] \]

看起来是非常不好做的。这里我们就将 \(1\) 定义为当前局面的先手，\(0\) 为后手。我们考虑一下人类玩家对局面的判断，如果自己的颜色越多，那么看起来至少是更有利的。对于全 \(1\) 和全\(0\) 结论显然，不考虑。那么我们统计一下个数 \(c_1,c_0\)。先来考虑 \(c_1>c_0\) 的情况。

我们必须要让\(c_1\geq c_0\) 到最后。于是我们在切的时候必须要满足一段的长度 \(c_1>c_0\)。那么如果 \(c_1>c_0\) 是必胜的，则另一段不可以为 \(c_1<c_0\)。故我们必须要满足另一段如果不是 \(c_1>c_0\) 的话最次找到一段 \(c_1=c_0\)，且一定可以找到。现在轮到后手切。后手如果能够成功切出一段 \(c_1<c_0\) 的话则另一段必有 \(c_1>c_0\)。那么如果后手切出两个 \(c_1=c_0\) 就不好办了。但我们发现我们一定可以找到一段使得它不能够分割成两个\(c_1=c_0\)。我们先随机找一个 \(c_1=c_0\)，然后如果可以的话我们就改找它的前缀 \(c_1=c_0\) 就一定最终找到一个不满足的了。

如果 \(c_1<c_0\)，那么无论怎么分后手都能够选择一段 \(c_1<c_0\) 来变成先手以进入上方讨论。

故我们有若 \(c_p>c_{1-p}\) 则 \(p\) 必胜。若 \(c_p<c_{1-p}\) 则 \(p\) 必败。

之后考虑初始 \(c_1=c_0\)。那么先手必须分成两段 \(c_1=c_0\)，否则一定为一段 \(c_1>c_0\)，另一段 \(c_1<c_0\)，则根据上述引理先手必败。也就是说如果无法分割则先手必败。

我们发现，如果分割成一段 \(c_1=c_0\)，则另一段也必然为 \(c_1=c_0\)。如果一段为基础必败，则后手必须选择另一段。那么这一段分成前缀和后缀。我们发现这个决策点到最开始序列的前/后缀仍为 \(c_1=c_0\)。故可能决策点即为所有前缀为 \(c_1=c_0\) 的点。那么我们每一次就是要将其分割成两部分，如果均为 \(1\) 则后手必败。那么我们发现奇数必败。由于奇数必定分割成偶数+奇数的形式，偶数可以分割成奇数+奇数的形式，而 \(1\) 为奇数为必败态，所以只要选了偶数一定可以让对方只拿到奇数。而拿到奇数则对方一定可以拿到偶数。于是就分类完毕了。