自动搬运

查看原文

来自洛谷，原作者为

	VinstaG173 Si Dieu n'existait pas, il faudrait l'inventer.

搬运于2025-08-24 22:44:29，当前版本为作者最后更新于2024-11-13 18:31:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

突然看到这题，发现竟然没做过，然后发现之前的题解饱受诟病后全被撤了，于是来写一发以免次次都要去找官方题解。

首先看到题意，选择“满足区间 $[1,i]$ 中有奇数个 $1$”的 $i$，并且序列中只有 $0$ 和 $1$，操作也是 $0,1$ 互换，看上去很像翻棋子游戏。考虑 $A_i=\text{xor}_{l=1}^i a_l$，那么操作实际上就是选择 $A_i=1$ 的 $i$ 及一个 $j\in(i,n]$，翻动 $A_i,\dots,A _{j-1}$，同样是 $A_i$ 全部为 $0$ 时失败。那么由翻棋子游戏的结论，我们只需求所有 $A_i=1$ 的 $i$ 处的 $sg(i)$ 的异或和，SG 函数方程如下：

$$sg(i)=\text{mex}_{i<j\le n}\{\text{xor} _{l=i+1}^{j-1}sg(l)\}. $$

我们不妨换个方向看，重新定义 $sg(i)$ 表示 $A_{n-i}$ 处的 SG 值。重写一遍方程：

$$sg(i)=\text{mex}_{0\le j<i}\{\text{xor} _{l=j+1}^{i-1}sg(l)\}. $$

打个小表，我们容易发现结论：

定理 $1$. $sg(i)=\text{lowbit}(i)$，其中对正整数 $i$ 定义 $\text{lowbit}(i)$ 表示使得 $2^k\mid i$ 的最大的 $2^k$。特别地，在此定义 $\text{lowbit}(0)=0$。下面我们证明这个定理。

定理证明. 用归纳法。首先显然 $sg(0)=0$，因为不能对位置 $n$ 操作（事实上由题设条件 $A_n$ 始终为 $0$）。假设对 $i\in[0,2^k]$ 结论成立，接下来我们借助两个引理来完成证明：

引理 $1$. 对于 $i\in(2^k,2^{k+1})$，有 $sg(i)=sg(i-2^k)$。

引理 $1$ 证明. 同样用归纳法。首先看归纳奠基 $2^k+1$，由于 $\forall j\in[0,2^k]$ 有 $sg(j)=\text{lowbit}(j)$，故 $\forall j\in[0,2^k)$ 有 $sg(j)<2^k$ 且 $sg(2^k)=2^k$，由异或运算的性质知 $\forall j\in[0,2^k),\text{xor}_{l=j+1}^{2^k}sg(l)\ge2^k$。又 $j=2^k$ 时有 $\text{xor}_{l=j+1}^{i-1}sg_l=0$（$0$ 个数的异或和定义为异或运算的单位元 $0$，下同），从而 $sg(2^k+1)=1=sg(1)$。

对 $i\in(2^k+1,2^{k+1})$，假设对 $j\in(2^k,i)$ 引理结论已证明，则 $\forall j\in[2^k,i),\text{xor}_{l=j+1}^{i-1}sg(l)=\text{xor} _{l=j-2^k+1}^{i-2^k-1}sg(l)$，故

$$\begin{aligned} \text{mex} _{2^k\le j<i}\{\text{xor} _{l=j+1}^{i-1}sg(l)\}&=\text{mex} _{0\le j<i-2^k}\{\text{xor} _{l=j+1}^{i-2^k-1}sg(l)\}\\ &=sg(i-2^k)<2^k, \end{aligned}$$

而同上可知 $\forall j\in[0,2^k),\text{xor}_{l=j+1}^{i-1}sg(l)\ge2^k$，从而 $sg(i)=sg(i-2^k)$，证毕。

引理 $2$. $\forall i\ge0$，$\text{xor}_{l=0}^i\text{lowbit}(l)$ 的二进制表示为格雷码的第 $i$ 位。记这个前缀异或和为 $g(i)$。

引理 $2$ 证明. 简单计算即可，在介绍格雷码的许多文章中也有提及，在此不做赘述。由引理 $2$ 我们可自然得到推论：

推论 $2$. $sg(2^{k+1})=2^{k+1}$。

由于 $\forall i\in(0,2^{k+1})$，有 $\text{lowbit}(i)=\text{lowbit}(2^{k+1}-i)$，又由于格雷码的 $0\sim2^{k+1}-1$ 位可取遍 $0\sim2^{k+1}-1$ 中的整数，故由引理 $2$ 及 SG 函数递推方程即得证。

通过引理 $1$ 及推论 $2$ 我们即对 $i\in[0,2^{k+1}]$ 完成了结论的证明，从而定理证毕。

回到原问题，我们即求所有 $A_{n-i}=1$ 的 $i$ 的 $\text{lowbit}(i)$ 的异或和。由题设 $a_i=1$ 的位置为偶数，设 $m=2t$，$a_i=1$ 的 $i$ 从小到大排列为 $i_1,\dots,i_{2t}$，那么我们发现所有 $A_{n-i}=1$ 的位置 $i$ 为集合 $\bigcup_{s=1}^t(n-i_{2s}+1,n-i_{2s-1}]$。

我们发现由异或运算的性质，

$$\begin{aligned} \text{xor}_{l=a+1}^b\text{lowbit}(l)&=(\text{xor} _{l=0}^a\text{lowbit}(l))\operatorname{xor}(\text{xor}_{l=0}^b\text{lowbit}(l))\\ &=g(a)\operatorname{xor}g(b). \end{aligned}$$

因此我们需要求

$$\begin{aligned} \text{xor} _{s=1}^{t}(\text{xor} _{l=n-i _{2s}+1}^{n-i _{2s-1}}\text{lowbit}(l))&=\text{xor} _{s=1}^t(g(n-i _{2s})\operatorname{xor}g(n-i _{2s-1}))\\ &=\text{xor} _{s=1}^mg(n-i_s). \end{aligned}$$

由于格雷码的另一条性质：$g(i)=i\operatorname{xor}\left\lfloor\dfrac i2\right\rfloor$，容易 $O(m)$ 计算。

进一步地，通过如上性质容易发现 $\text{xor} _{s=1}^mg(n-i_s)=0$ 当且仅当 $\text{xor} _{s=1}^m(n-i_s)=0$。这就是官方题解中的最终结论。

综上所述，当且仅当 $\text{xor} _{s=1}^m(n-i_s)=0$ 时后手必胜。代码过于简单就不提供了。