题解

思路

若 $N$ 为奇数，先手总能获胜：如果当前不能一步取胜，那么对手也不可能保证在下一步取胜；把不能配对的局面不断缩小，最终会轮到先手面对仅剩一块饼干的局面。

做法

若 $N$ 为偶数，先手只有在第一步就结束游戏时才能获胜，否则取走一块后会把一个奇数规模的必胜局面交给对手。设所有数的异或和为 $s$，取走 $A_i$ 后剩余数的异或和为 $s\mathbin{\mathrm{xor}}A_i$，它等于 $0$ 当且仅当 $A_i=s$。因此偶数情形只需检查序列中是否存在等于总异或和的元素。

复杂度

扫描一次序列即可得到总异或和并完成检查，时间复杂度为 $O(N)$，空间复杂度为 $O(N)$；若边读边保存并在之后检查，也可视实现方式降为常数额外空间。