|
|
##[$AcWing$ $891$. $Nim$游戏](https://www.acwing.com/problem/content/description/893/)
|
|
|
|
|
|
### 一、题目描述
|
|
|
|
|
|
给定$n$堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。
|
|
|
|
|
|
问如果两人都采用最优策略，先手是否必胜。
|
|
|
|
|
|
**输入格式**
|
|
|
第一行包含整数 $n$。
|
|
|
|
|
|
第二行包含 $n$ 个数字，其中第 $i$ 个数字表示第 $i$ 堆石子的数量。
|
|
|
|
|
|
|
|
|
**输出格式**
|
|
|
如果先手方必胜，则输出 `Yes`。
|
|
|
|
|
|
否则，输出 `No`。
|
|
|
|
|
|
**数据范围**
|
|
|
$1≤n≤10^5,1≤每堆石子数≤10^9$
|
|
|
|
|
|
**输入样例**：
|
|
|
```cpp {.line-numbers}
|
|
|
2
|
|
|
2 3
|
|
|
```
|
|
|
**输出样例**：
|
|
|
```cpp {.line-numbers}
|
|
|
Yes
|
|
|
```
|
|
|
|
|
|
### 二、历史与传说
|
|
|
|
|
|
据说，它源自中国，经由被贩卖到美洲的奴工们外传。辛苦的工人们，在工作闲暇之余，用石头玩游戏以排遣寂寞。后来流传到高级人士，则用便士（$Pennies$），在酒吧柜台上玩。
|
|
|
|
|
|
最有名的玩法，是把十二枚便士放成$3、4、5$三列，拿光铜板的人赢。
|
|
|
|
|
|
后来，大家发现，先取的人只要在$3$那列里取走$2$枚，变成了$1、4、5$，就能稳操胜券了，游戏也就变得无趣了。
|
|
|
|
|
|
于是大家就增加列数，增加铜板的数量，这样就让人们有了毫无规律的感觉，不易于把握。
|
|
|
|
|
|
### 三、博弈论结论
|
|
|
在两名选手都足够聪明，每一步都是最优解的情况下：
|
|
|
|
|
|
$a_1$ ^ $a_2$ ^ ... ^$a_n=0$ 先手必败
|
|
|
$a_1$ ^ $a_2$ ^ ... ^$a_n\neq0$ 先手必胜
|
|
|
就是把所有堆的石子个数异或起来，结果是零，先手必败，不是零，先手必胜。
|
|
|
|
|
|
### 四、证明过程
|
|
|
|
|
|
#### 1、结论$1$
|
|
|
操作到最后时，每堆石子数都是$0$，有$0$ ^ $0$ ^ $…0=0$
|
|
|
|
|
|
|
|
|
#### 2、结论$2$
|
|
|
**在操作过程中，如果 $a_1 ∧ a_2 ∧ … ∧ a_n=x≠0$。那么玩家必然可以通过拿走某一堆若干个石子将异或结果变为$0$。**
|
|
|
|
|
|
**证明**：
|
|
|
* 不妨设结果$x$的二进制表示中最高一位$1$在第$k$位
|
|
|
* 那么在$a_1,a_2,…,a_n$中，必然有一个数$a_i$，它的第$k$位是$1$(**要不那个$1$从哪里来的？**)，且$a_i ∧ x<a_i$:
|
|
|
* 让第$i$堆石子保留$a_i ∧ x$个：即从第$i$堆石子中拿走$a_i−(a_i ∧ x)$个石子
|
|
|
* 此时新状态的异或和：
|
|
|
$$\large a_1 ∧ a_2 ∧ … ∧ a_{i^{'}} ∧ … a_n \\
|
|
|
=a_1 ∧ a_2 ∧ … ∧(a_i ∧ x) ∧ a_n \\
|
|
|
=a_1 ∧ a_2 ∧ … ∧a_i ∧... ∧ a_n ∧ x \\
|
|
|
=x ∧ x =0
|
|
|
$$
|
|
|
|
|
|
**证毕**
|
|
|
><font color='red' size=3><b>解释：也就是说，不管给我啥样的情况，我都能找出一种办法，使得一次拿取后满足异或和为$0$。</b></font>
|
|
|
|
|
|
其实，我们也并不非得要找到某个有明显特征（指$x$的最高位$1$在第$k$位，而$a_i$的第$k$位是$1$）的$a_i$,更通用的作法是
|
|
|
```c++
|
|
|
for (int i = 0; i < n; i++) {
|
|
|
if((a[i] ^ x) < a[i]){
|
|
|
1. 拿走 a[i]-(a[i] ^ x)个
|
|
|
2. 剩下 a[i] ^ x个
|
|
|
}
|
|
|
}
|
|
|
```
|
|
|
这样的话，我们也就可以求出有多少种拿法，并且知道每种拿法是拿走多少，剩下多少。
|
|
|
|
|
|
|
|
|
|
|
|
#### 3、结论$3$
|
|
|
**在操作过程中，如果 $a_1 ∧ a_2 ∧ …∧ a_n=0$，那么无论玩家怎么拿，必然会导致最终异或结果不为$0$**
|
|
|
|
|
|
**反证法**：假设玩家从第$i$堆石子拿走若干个，结果仍是$0$。不妨设还**剩下**$a_i^{′}$个，因为不能$1$个都不拿，所以$0≤a_i^{′}<a_i$，且$a_1 ∧ a_2∧…∧a_i^{′}∧…∧a_n=0$。
|
|
|
|
|
|
**进行构造**
|
|
|
$$(a_1 ∧ a_2∧…∧a_i∧…a_n)∧(a_1∧a_2∧…∧a_i^{′}∧…∧a_n)$$
|
|
|
|
|
|
整体构造完式子后，利用异或运算的 **结合律** 性质，让
|
|
|
$$a_1 ∧ a_1=0,a_2 ∧ a_2=0,a_3 ∧ a_3=0,...$$
|
|
|
|
|
|
$$\large \Rightarrow a_i∧a^{′}=0$$
|
|
|
|
|
|
则 $a_i=a′$，与假设$0≤a′<a_i$矛盾。
|
|
|
|
|
|
**证毕**
|
|
|
|
|
|
|
|
|
**基于上述三个结论**：
|
|
|
|
|
|
1. 如果先手面对的局面是$x=a_1∧a_2∧…∧a_n≠0$，那么先手总可以通过拿走某一堆若干个石子($a_i ∧ x$个)，将局面变成$a_1∧a_2∧…∧a_n=0$。如此重复，最后一定是后手面临最终没有石子可拿的状态。先手必胜。
|
|
|
<br>
|
|
|
2. 如果先手面对的局面是$a_1∧a_2∧…∧a_n=0$，那么无论先手怎么拿，都会将局面变成$a_1∧a_2∧…∧a_n≠0$，那么后手总可以通过拿走某一堆若干个石子，将局面变成$a_1∧a_2∧…∧a_n=0$。如此重复，最后一定是先手面临最终没有石子可拿的状态,先手必败。
|
|
|
|
|
|
### 五、实现代码
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
int main() {
|
|
|
int n;
|
|
|
cin >> n;
|
|
|
|
|
|
int res = 0; // 起始值是0,因为任何数与0进行异或都它本身
|
|
|
while (n--) {
|
|
|
int x;
|
|
|
cin >> x;
|
|
|
res ^= x;
|
|
|
}
|
|
|
if (res)
|
|
|
puts("Yes"); // 异或值非零，必胜
|
|
|
else
|
|
|
puts("No"); // 异或值是零，必败
|
|
|
return 0;
|
|
|
}
|
|
|
``` |
