标签：dots prime 石子 xor space int 博弈论 简单
简单博弈论
Nim游戏
Nim游戏满足以下三个条件:
(1)两名玩家交替行动
(2)游戏过程中，可以执行的的行动和轮到哪位玩家没有关系
(3)不能行动的玩家判负
比如围棋就不是一种Nim游戏，因为围棋有黑白两子不满足(2)，围棋判断输赢规则较为复杂不符合(3)。下面的取石子游戏就是一个Nim游戏：给定n堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
例如：有两堆石子，第一堆有2个，第二堆有3个，先手必胜。
操作步骤：
- 先手从第二堆拿走1个，此时第一堆和第二堆数目相同
- 无论后手怎么拿，先手都在另外一堆石子中取走相同数量的石子即可。
- 两个概念
必胜状态：即经过某一个操作后留给另一个玩家的是一个必败状态，则对于先手玩家来说就是一个必胜状态，即先手可以走到一个必败状态。
必败状态:即无论怎么操作都必定会走到一个必胜状态，则对于先手玩家来说是一个必败状态，即先手必定走到一个必胜状态。
- 解决方法和数学证明
假设这n堆石子分别为\(a_1,a_2,a_3\dots a_n\)个,那么当\(a_1\space xor\space a_2\space xor\space a_3\dots xor\space a_n=0\)时为先手必败，\(a_1,a_2,a_3\dots a_n\)个,那么当\(a_1\space xor\space a_2\space xor\space a_3\dots xor\space a_n\ne0\)时为先手必胜。(xor是异或运算）
证明:首先当每堆石子数量都为0时有：\(a_1\space xor\space
a_2\space xor\space a_3\dots xor\space a_n=0\)此时为终止状态，先手必败。当\(a_1\space xor\space a_2\space xor\space a_3\dots xor\space a_n=x\ne0\)时，我们设x的二进制数为1的最高位是第k位，显然有\(a_1\)~\(a_n\)中至少有一个数的二进制数的第k位为1，不妨设这个数为\(a_i\)，则\(a_i\space xor\space x<a_i\)[^异或计算],那么就可以保证从第i堆石子中取\(a_i-(a_i\space xor\space x)\)有意义，设取了以后第i堆剩下的石子个数为\(a^{\prime}=a_i-(a_i-(a_i\space xor\space x))=a_i\space xor\space x\),则取后各堆石子异或为:\(a_1\space xor\space
a_2\space xor\space a_3\dots xor\space a^{\prime}\dots\space xor\space a_n=a_1\space xor\space
a_2\space xor\space a_3\dots xor\space a_i\space xor\space x\dots\space xor\space a_n=x\space xor\space x=0\)所以对于任一个各石堆个数异或值不为0的状态，我们都可以取特定的石子让它变为异或值为0的状态，即此时状态为先手必胜。再证：首先当\(a_1\space xor\space a_2\space xor\space a_3\dots xor\space a_n=0\)此时为先手必败状态。这里我们可以用反证法，假设我们可以通过取一定的石子让它的异或值继续为0，即:
不知道为什么，这下面的发不出来。
\[\begin{cases}
a_1\space xor\space a_2\space xor\space a_3\dots xor\space a_n=0&(1)\\
a_1\space xor\space
a_2\space xor\space a_3\dots xor\space a^{\prime}\dots\space xor\space a_n=0&(2)
\end{cases}
$$(1),(2)两边同时异或得$a_1\space xor\space a_2\space xor\space a_3\dots xor\space a_n\space xor\space a_1\space xor\space
a_2\space xor\space a_3\dots xor\space a^{\prime}\dots\space xor\space a_n=0$这里除了$a_i$和$a^{\prime}$外其余都是成对得所以$a_1\space xor\space a_2\space xor\space a_3\dots xor\space a_n\space xor\space a_1\space xor\space
a_2\space xor\space a_3\dots xor\space a^{\prime}\dots\space xor\space a_n=0\Longleftrightarrow a_i\space xor\space a^{\prime}=0\Longrightarrow a_i=a^{\prime}$，Nim游戏中每一次都必须进行操作所以$a_i\ne a^{\prime}$，与规则矛盾，所以当$a_1\space xor\space a_2\space xor\space a_3\dots xor\space a_n=0$此时为先手必败状态，证毕。
[^异或计算]:异或计算是不进位加法，例如$1\space xor\space3=001\space xor\space 011=010=2$,这里$a_i=00\underbrace{1\dots}_{k}$ 而$x=00\underbrace{1\dots}_{k}$二者异或第k位必定变为0则必定小于$a_i$
- 代码实现
```c++
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
int res=0;
for(int i=0;i<n;i++)
{
int x;
scanf("%d",&x);
res^=x;
}
if(res==0)
{
printf("No");
}
else
{
printf("Yes");
}
return 0;
}
```
## sg函数
- mex操作
mex操作是指求一个集合中未出现的最小自然数，例如mex(1,2,3)=0,mex(0,1,2,4,5)=3。
- sg函数定义
在一个有向图中，对于每个节点x，从x出发有k条边，分别能到$y_1,y_2,y_3\dots y_k$则$sg(x)=mex(sg(y_1),sg(y_2),sg(y_3)\dots sg(y_k))$,特别地，终点的sg值为0。一个图的sg值定义为起点的sg值
容易看出sg函数有性质:
(1):若sg(x)=k$\ne 0$,则x点能到达的点的sg值最大为k-1.
(2):sg值为0的点走不到sg值为0的点
(3):sg值不为0的点一定能走到sg值为0的点
- 定理
在一个图中，若sg(s)=0,则先手必败，若sg(s)$\ne 0$，则先手必胜。
在n个图中，若$sg(s_1)\space xor\space sg(s_2)\space xor\space sg(s_3)\dots\space xor\space sg(s_n)=0$为先手必败，反之必胜，从sg函数的性质很容易能够理解。
- 代码实现
给定 n 堆石子以及一个由 k 个不同正整数构成的数字集合 S。
现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合 S，最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
```c++
#include<iostream>
#include<unordered_set>
#include<cstring>
using namespace std;
const int N=1e5+10,M=110;
int f[N],g[M],h[M];
int k,n;
int sg(int x)
{
if(f[x]!=-1)
{
return f[x];//让每个值的sg值只算一遍
}
unordered_set<int> s;//用哈希表来存储x点取后会变为哪些状态
for(int i=0;i<k;i++)
{
int sum=g[i];
if(x>=sum)
{
s.insert(sg(x-sum));
}
}
for(int i=0;;i++)
{
if(!s.count(i))//注意哈希表如果什么也没有插入，查询0也会返回不存在，for循环从0开始所以这里可以保证终点的sg值一定为0
{
f[x]=i;
return f[x];
}
}
}
int main()
{
cin>>k;
memset(f,-1,sizeof(f));
for(int i=0;i<k;i++)
{
scanf("%d",&g[i]);
}
cin>>n;
for(int i=0;i<n;i++)
{
scanf("%d",&h[i]);
}
int res=0;
for(int i=0;i<n;i++)
{
res^=sg(h[i]);
}
if(res==0)
{
printf("No");
}
else
{
printf("Yes");
return 0;
}
}
```\]
标签：dots,
prime,
石子,
xor,
space,
int,
博弈论,
简单
From： https://www.cnblogs.com/Taco-gu/p/17556971.html