一种奇怪的石子游戏

Alice 和 Bob 又开始玩石子游戏了。

初始有 n 个石子，Alice 先走，可以取 [1, n − 1] 个，接下来每个人取的石子数不能比上一个人取的多。

无法取的人输。

观测题目，发现 Alice 可以一开始直接取 1 个，然后结局就固定了。

所以当且仅当 n ≡ 0 (mod  2) 时，Bob 才可能赢。

那么剩下情况呢？

显然当 n = 2 时 Alice 是无法反击的。

但是比如当 n = 6 时，Alice 可以考虑取两个，剩下 4 个显然是 Alice 必胜的。

略加思考可以发现，若当前局面 n ≡ 0 (mod  2)，那么先手必然不会操作奇数个，否则后手操作一个即可胜利。

所以我们相当于只需要讨论 在模 2 意义下的余数，因为这又转化成了之前的子问题。

于是Bob能赢当且仅当： n = 2^k(k = 1, 2, …)