博弈题先打表

不过建议先用一些基础的打表方法，就是简单的搜索打表，因为SG定理并非什么时候都适用->详见GDCPCL我们队的银牌差点消失 打表函数如下

bool dabiao(int x) {
    if (x==0) return false;
    if (memo[x]!=-1) {
        return memo[x]==1;
    }
    for (int i=1; i<=min(3ll,x); i++) {
        if (!dabiao(x-i)) {
            memo[x]=1;
            return true;
        }
    }
    memo[x]=0;
    return false;
}

公平组合游戏，如果一个节点后继有一个返回必败则这个节点本身必胜，打表规律如下 1 win 2 win 3 win 4 lose 5 win 6 win 7 win 8 lose 9 win 10 win 11 win 12 lose..... 可以看出规律了，只要是$n\bmod4=0$则必败 接下来可以使用数学归纳法给出证明

基础情况 当 $n=0$ 时：此时无法操作，定义为必败态。满足 $0 \pmod 4 = 0$。

当 $n=1, 2, 3$ 时：先手可以直接拿走全部石头，获胜。这三个状态是必胜态。满足 $1, 2, 3 \pmod 4 \neq 0$。

假设对于所有小于 $k$ 的石头数，结论成立：即 $n < k$ 时，凡是 $n \pmod 4 = 0$ 的均为必败，凡是 $n \pmod 4 \neq 0$ 的均为必胜。

情况 A：若 $k \pmod 4 \neq 0$（即 $k = 4m + r, r \in \{1, 2, 3\}$） 我们可以选择拿走 $r$ 个石头。剩下的石头数为 $k - r = 4m$，这是一个 $4$ 的倍数。根据假设，这剩下的状态是必败态。因为我们能走到一个必败态，所以 $k$ 是必胜态。

情况 B：若 $k \pmod 4 = 0$（即 $k = 4m$） 无论先手拿走 $x \in \{1, 2, 3\}$ 个石头，剩下的石头数 $k - x$ 分别为 $4m-1, 4m-2, 4m-3$。这些数显然都不是 $4$ 的倍数。根据假设，这些状态全都是必胜态（对先手而言）。因为无论先手怎么走，留给对方的都是必胜态（对对方而言），所以 $k$ 是必败态。 证毕 再提一嘴这个东西其实是巴什博弈