题解：P9003 [RC-07] Game Theory
VinstaG173
·
·
题解
突然看到这题，发现竟然没做过，然后发现之前的题解饱受诟病后全被撤了，于是来写一发以免次次都要去找官方题解。
首先看到题意，选择“满足区间 [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)，故
\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}]。
我们发现由异或运算的性质，
\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}
因此我们需要求
\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 时后手必胜。代码过于简单就不提供了。