题解

思路

全部袋子被搬空后，盘子上的硬币构成一个普通 Nim 局面，异或和是否为零决定轮到谁时必胜。

做法

搬袋阶段恰有 $N$ 步，因此双方在这个阶段希望制造零异或还是非零异或，取决于 $N$ 的奇偶。若 $N$ 为奇数，后手总能在自己的搬袋回合把当前最大袋放到当前硬币最多的盘子，使某个盘子拥有超过总数一半的硬币，从而保证最终异或和非零，因此后手必胜。

若 $N$ 为偶数，当每种袋子大小都出现偶数次时，后手可以把等大的袋子两两配对，并对先手的落盘选择作对称回应，使搬袋结束后的异或和为零，因此后手获胜；只要有某个数值出现奇数次，先手可用同样的最大值策略破坏零异或并获胜。所以答案仅需判断 $N$ 是否为偶数以及所有频次是否均为偶数。

复杂度

将数组排序后扫描相等段即可，单组时间复杂度为 $O(N\log N)$，额外空间复杂度为 $O(N)$。