题意

n个石头，轮流取1-3三个，谁把最后取空谁获胜。问谁能获胜

限制：

初始个数不超过$10^{9}10^9$

方法

递归（TLE）

因为是轮流取1-3个，所以除了取的时候个数不同，其它是公平的

如果一个人要取时剩余不到3个，那么全部取走获胜。

对于其它情况考虑一个人取的时候剩下n个，那么他取后，他的对手可以是n-1,n-2,n-3个三种情况

如果其中每种情况，他的对手都必胜，那么他就必败。

否则选择他对手必败的情况即可。

所以有递归关系

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return bool布尔型
     */
    bool NimGame(int n) {
        if(n <= 3)return true;
        for(int i = 1;i<=3;i++){
            if(!NimGame(n-i)) // 只要有一个是失败，那么就选这个方案
                return true;
        }
        return false; // 如果全是成功 则必定失败
    }
};

复杂度分析

时间复杂度: 因为每个状态会衍生3个状态，所以时间复杂度为$O(3^n)O(3^n)$

空间复杂度: 空间主要和递归深度有关，所以空间复杂度为$O(n)O(n)$

不变量维持

如果不论对手怎么取，他取后你有方案维持某个不变量，那么不论最初有多少，从最初到最后，每轮这个不变量都一致。

就不再会需要具体取模拟而是考察不变量了。

以题目中的样例数据4为例

取值范围是[1,3]的整数，你会发现后取的人始终可以取(1+3)-对手的值来让你们的操作之和为$44$

也就是如果对手操作前 模4余k，你可以在你操作后依然模4余k

如何胜利呢，你需要模4余零。

所以你需要第一步完成模4余零，然后维持它。

所以问题变成了，能否在第一次让值模4余零。

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return bool布尔型
     */
    bool NimGame(int n) {
        return n%4; // 本身不余零，才能第一次取后让它模4余零
    }
};

复杂度分析

时间复杂度: 直接计算，时间复杂度为$O(1)O(1)$

空间复杂度: 直接计算，时间复杂度为$O(1)O(1)$