题目描述

你和一个朋友玩Nim游戏：桌上有一堆石子，每次你们可以拿走1-3枚石子，交替进行。拿走最后一枚石子的玩家获胜。你是先手。

你们两名玩家都非常聪明，每次都会选择最优玩法。请编写一个函数，判断给定 $n$ 枚石子时，你能否获胜。

样例

输入：4
输出：false 
解释：一共有4枚石子，你必败。不管第一次你取多少石子，
      第二次你的对手都可以取走剩下的所有石子。

算法

(博弈论) $O(1)$

如果 $n$ 能被 $4$ 整除，则不论每次你取多少石子，不妨设是 $x$，你的对手可以取 $4 - x$ 枚石子。那么最后一枚石子一定被对手取走，你必败；

如果 $n$ 不能被 $4$ 整除，则你第一次取走 $n\%4$ 枚石子，然后剩下的石子数就是 $4$ 的倍数，按上一种情况的讨论，你的对手必败，你必胜。

在C++中，n%4 可以用位运算计算，时间效率高一些，n%4 = n&3。

时间复杂度分析：只有一次位运算，时间复杂度是 $O(1)$。

C++ 代码

class Solution {
public:
    bool canWinNim(int n) {
        return n&3;
    }
};