202503021815 博弈论 石子 无限拿

石子 无限拿

给定  n  堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

思路

若为 2, 3 堆, 先手在 3 堆里拿 1 个, 为 2 2。 之后只要跟后手拿的数量相同, 后手一定失败。

定理： $a_1\wedge a_2\wedge a_3...\wedge a_n=0先手必败$ 证明：

$$\begin{array}{rl}0\wedge 0\wedge 0\wedge \mathrm{0...}\wedge 0=0& \\ a_1\wedge a_2\wedge a_3...\wedge a_n\ne 0& \\ & \end{array}$$

不等于 0 时, 设结果为 $x$ $x$ 的二进制表示为 $10100100$ $a_i$的二进制表示 $1100100110$ 一定存在 $a_i$ 在 $x$ 最高位 $k$ 位上为 1。 则 $a_i\wedge x<a_i$ , 那么就拿走 少的那一部分。

此时 $a_i=a_i\wedge x$ 带入到原来式子后得到： $x\wedge x=0$ 故先手必赢。

等于 0 时, 设同样可以拿走一些, 剩下 $a_i^{\prime }$个

$$\begin{array}{r}{a}_1\wedge a_2\wedge a_3...a_i\wedge ..\wedge a_n=0\\ a_1\wedge a_2\wedge a_3...a_i^{\prime }\wedge ..\wedge a_n=0\\ 式子相异或得\\ a_i\wedge a_i^{\prime }=0\\ a_i=a_i^{\prime }\end{array}$$

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
int readInt()
{
    int t ;
    scanf("%d", &t);
    return t;
}
 
int n;
int main()
{
    int x;
    cin >> n;
    cin >> x;
    n -= 1;
    while(n--)
        x ^= readInt();
    if(x) cout << "Yes\n";
    else cout << "No\n";
 
}