题解：P14586 [LNCPC 2025] 前后缀石子博弈

神秘拼好题/fd

首先，我们先考虑单局游戏如何判断胜负。一个感受是对于每个数我们只用考虑它的奇偶性，因为可以通过下模仿棋的方式来保持奇偶性。进一步地，我们发现每次操作中序列的两端必有一端是会被取的。结合以上两点，我们可以合理猜测，胜负状态只与两端的奇偶性有关。

经过打表验证，可以发现只有两端都是偶数的时候先手必败，否则先手必胜，证明如下：

至此，博弈论部分解决。现在，我们需要考虑如何处理这个前后缀和操作，注意操作是在模 $2$ 意义下进行的。

不妨只考虑 $1 \sim x$ 这段前缀的操作，后缀的同理。对于一个值非零的位置 $i$，做一次后缀和相当于跳一步跳到前面，做 $k$ 次后缀和就相当于跳 $k$ 步。考虑每次跳到哪里，那么贡献实际上就是从 $1 \sim i$ 中选 $k - 1$ 个可重位置的方案数。利用插板法，容易得到贡献的具体值为：

利用 Lucas 定理，贡献的具体值转化为：

进行简单的转化后发现它等价于：

可以直接高维前缀和解决，时间复杂度 $O(n \log n)$。

submission: https://qoj.ac/submission/1771672.