c++ - 涉及按位异或的博弈论问题

所以首先，让我们了解真正赢得比赛的因素。

由于最后是在比较分数，分数高的获胜，所以唯一重要的是每个分数的最高位。

由于获得分数的方法是从给定数组中获取数字，因此唯一重要的是数组中每个数字的最高有效位。只有两个玩家会从最高位获得相同的分数，您需要测试下一位。

令 x 为 1 的个数， y 为数字的最高有效位中的 0 的个数：

如果 x 是偶数，无论玩家做出什么决定，都将以相同的分数结束该位，因此转到下一位（如果不存在，则游戏以平局结束）。事实上，两个玩家的结果的奇偶性将是相同的，因为 x 是偶数。

为简单起见，我假设数组中包含的所有数字都是 1 或 0。假设数组中有 4 个数字 [1, 1, 1, 1]。如果两个玩家都必须 xor 1 两次。所以他们都得到（0 xor 1）xor 1 = 0。

事实上，只要 1 的个数是偶数，它们总是会打成平手，因为它们都会异或相同数量的 1。另一方面，异或 0 不会改变它们的分数。

所以我们可以得到：x mod 2 = 0 给出平局

现在让我们考虑一下玩家 1 将如何赢或输。最简单的情况，如果有 [1, (0)...]，或者只有一个 1，并且任何数字 0，玩家 1 获胜。

这里我们可以得到如果 x = 1, p1 获胜

那你怎么能让玩家1输呢？只要数组中有一个 1，玩家 1 就可以拿走它。所以要让他输，玩家 1 必须再拿一个 1，而玩家 2 也需要拿一个 1。也就是说，你至少需要三个 1 才能让玩家 1 输。

这里我们可以得到如果 x = 3，p1 可能会输

但是你如何确保玩家 1 会拿走额外的 1 呢？我们必须确保玩家 1 是最后一个选择的玩家，所以他别无选择，只能选择它。为此，我们将得到偶数个 0。通过这样做，p2 总是可以复制 p1 所做的事情，除了取额外的 1。

假设我们有 [1, 1, 1, 0, 0]。然后他们会做：
P1: 1, 0, 1
P2: 1, 0,
or:
P1: 0, 1, 1
P2: 0, 1,

现在我们可以得到if x = 3, y mod 2 = 0, p1 loss

现在让我们看看我们是否可以概括这部分，假设我们有 x = 5。现在，无论 p2 做什么，p1 总是可以确保奇数为 1，所以他总是会赢。

类似地，如果我们有 x = 7，我们将有一个与 x = 3 相同的情况。如果我们有偶数 0，p2 总是可以使 p1 得到偶数 1。

现在我们得到：

如果 x mod 2 = 0，他们平手

如果 x mod 4 = 1，则 p1 获胜并且

如果 x mod 4 = 3, y mod 2 = 1, p1 获胜并且

if x mod 4 = 3, y mod 2 = 0, p1 lost，这基本上就是他们的解决方案。