题目分析

本题是一个双人回合制组合游戏，核心规则为：

• 桌子上有 $2n$ 堆石子，分为 $n$ 组（第 $2k-1$ 堆与第 $2k$ 堆为一组，其中 $1 \le k \le n$）。
• 每次操作需从一组中移走一堆石子，再将同组另一堆分割为两堆非零石子（被分割的堆石子数至少为 $2$）。
• 无法操作（所有堆均为 $1$）时判当前玩家输，小E先手，需判断其是否存在必胜策略。

算法思路

本题可通过组合游戏中的Grundy数（尼姆数） 分析胜负，核心逻辑如下：

1. 游戏的独立性：每组石子的操作互不影响，整个游戏可视为 $n$ 个独立子游戏的“异或组合”。根据组合游戏理论，整体游戏的胜负由所有子游戏的Grundy数的异或结果决定：若异或结果非零，先手（小E）必胜；否则后手（小W）必胜。

2. 子游戏的Grundy数计算：
   对于每组石子 $(a, b)$（两堆石子数），其对应的Grundy数需通过二进制分析推导：

   • 令 $x = a-1$，$y = b-1$，计算 $s = x | y$（二进制或运算）。
   • 定义函数 $f(s)$ 为 $s$ 的二进制表示中“末尾连续 $1$ 的个数”（例如 $s=6$ 即二进制 110，末尾连续 $1$ 的个数为 $1$）。
   • 该组的Grundy数即为 $f(s)$。

3. 整体胜负判断：将所有组的Grundy数进行异或运算，若结果非零，则小E存在必胜策略（输出“YES”）；否则不存在（输出“NO”）。

关键原理

• Grundy数的意义：每个子游戏的Grundy数表征了该状态的“胜负势”，其值等于该状态所有可能后续状态的Grundy数的最小非负整数（mex）。
• 二进制特性：本题中 $f(s)$ 的定义对应了分割操作的本质——每次分割会改变二进制末尾连续 $1$ 的结构，而异或运算恰好能综合所有子游戏的胜负势，最终判断整体游戏的胜负。

算法标签

• 组合游戏
• Grundy数（尼姆数）
• 异或运算
• 二进制分析