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

· · 题解

神秘拼好题/fd

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

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

对于一个必胜状态，显然可以进行一次操作使得两端都是偶数，于是它一定可以变成一个必败状态。

对于一个必败状态，由于两端中必有一端要取，所以一定会有一端改变奇偶性，于是它一定会变成一个必胜状态。

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

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

{i + k - 2 \choose k - 1} \bmod 2

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

[(k - 1) \subseteq (i + k - 2)]

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

[(k - 1) \cap (i - 1) = \varnothing]

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

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