LeetCode 292。尼姆游戏

很明显，如果n=m+1，那么无论第一个拿取者拿走多少物品，最后一个拿取者都可以一次性拿走剩余的物品，后者获胜。所以我们找到了如何取胜的规律:如果n=(m+1)r+s，(r是任意自然数，s≤m)，那么第一个取者取s项，如果第二个取者取k(≤m)，那么第一个取者取m+1-k项，结果就剩下了。简而言之，如果你想为你的对手保留(m+1)的倍数，最后你就能赢。

对于巴适游戏，那么我们规定，如果最后赢家输了，会怎么样？

(n-1)%(m+1)==0，成功的玩家获胜。

第一手会重新确定策略，所以不是简单的相反。

Wythoff的游戏:有两堆，每堆有几件物品，两个人轮流从任一堆中取至少一件物品或同时从两堆中取相同数量的物品，并规定每次至少取一件物品，多件物品不限。最后，胜者为王。

如果两个人使用正确的操作，那么在面对非奇异的情况下，第一个会赢；另一方面，后者获胜。

那么给定一个情况，(a，b)，如何判断是不是奇怪的情况呢？我们有以下公式:

指这样的游戏。目前有什么堆石头，每堆石头的数量也是任意的。双方轮流从他们身上取出石头。规则如下:

1)每一步至少要移走一块石头；每一步只能从一堆石头中取出部分或全部石头；

谁拿到最后一块石头，谁就赢了。

判断当前情况是否是双赢(双输)局面；

所有堆中石头的数量用二进制数表示。当所有这些数按位异或的结果为0时，当前情况为输的情况，否则为赢的情况。

有一堆数量为n的石头，游戏双方轮流拿石头，满足以下要求:

1)第一手第一次拿不到所有的石头；

2)之后每次可以取的石头数量在1和对手刚刚取的石头数量的两倍之间(包括1和对手刚刚取的石头数量的两倍)。

大家一致认为，拿到最后一块石头的人就是胜利者，他将被打败。

这个游戏叫斐波那契游戏，一定和斐波那契数列有密切关系。如果经过一些实验，我们可以猜测第一手牌赢且仅当n不是斐波那契数。换句话说，输的状态构成了斐波那契数列。