292. Nim Game

问题：

给n个石子，由你开始选取，和你的朋友轮流进行。

每次选取，可以选取1～3个石子，

最后一个取完石子的人获胜，返回你是否能赢得胜利。

Example 1:
Input: n = 4
Output: false
Explanation: These are the possible outcomes:
1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
3. You remove 3 stones. Your friend removes the last stone. Your friend wins.
In all outcomes, your friend wins.

Example 2:
Input: n = 1
Output: true

Example 3:
Input: n = 2
Output: true
 
Constraints:
1 <= n <= 2^31 - 1

　　

解法：math

我们进行反向推演：

• 若轮到我时：
  • 最后剩下1～3个石子，那么我一定赢。
  • 剩下4个石子，那我不管取1～3个石子，我一定会留下1～3个石子，使得对方赢。

即谁面临4个石子，谁输。

那么假使为了让我一定赢，那么一定得使得对方面临4个石子。

• 那么怎样才能让对方面临4个石子呢？
  • 那就是：
  • 轮到我时，让我能够面临：5～7个石子，那么我就一定能取到，使得对方面临4个石子。
• 继续：怎样才能让我面临5～7个石子呢？
  • 那么：
  • 轮到对方时，让对方面临：8个石子，不管对方怎么取，都一定会剩下5～7个石子。

……

总结：

为了让我赢：那就要对方面临：4，8，12... 4n 个石子。

如果一开始就是我面临4n个石子，对方也是聪明的，对方就不会留给我，能够使得对方自己面临4n个石子的机会。

所以，只要一开始我就面临4n个石子，最后就只能输了。

否则，我就一定不会让自己接下来面临4n个石子。

答案即是：若4%n==0，那我就一定输，否则一定赢。

代码参考：

class Solution {
public:
    bool canWinNim(int n) {
        return n%4!=0;
    }
};