P2197 【模板】nim游戏

发表于 | 更新于 | 评论数： | 阅读次数：
本文字数： 5.2k | 阅读时长 ≈ 5 分钟

P2197 【模板】nim游戏

传送门

洛谷

题目描述

甲，乙两个人玩$Nim$取石子游戏。

$nim$游戏的规则是这样的：地上有$n$堆石子（每堆石子数量小于$10000$），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这$n$堆石子的数量，他想知道是否存在先手必胜的策略。

输入输出格式

输入格式：

第一行一个整数$T \le 10$,表示有$T$组数据

接下来每两行是一组数据，第一行一个整数$n$，表示有$n$堆石子，$n \le 10000$;

第二行有$n$个数，表示每一堆石子的数量

输出格式：

共$T$行，如果对于这组数据存在先手必胜策略则输出”$Yes$”,否则输出”$No$”，不包含引号，每个单词一行。

输入输出样例

输入样例#1：

2
2
1 1
2
1 0

输出样例#1：

No
Yes

分析

本题可以就题论题，但本文对本题不做过多证明（我才不会告诉你是我证不来）。
介绍比较通用的解法——博弈$SG$。

博弈SG

简介

公平游戏是一种双人游戏，在游戏中双方都有完整的信息，没有牵涉，任何状态的合法操作对双方来说都是相同的。
而在公平游戏中，$SG$函数和$SG$定理是一个十分神奇的东西，有了它，绝大部分的博弈都可以被统一到这个上面，都可以使用$SG$函数解决。是一种解决博弈问题的十分方便的手段。

前置知识

首先，我们定义$mex$运算（排斥运算），其运算结果是传入参数中没有出现的第一个非负整数。举个例子：
$mex(1,2,3)=0$ $mex(0,1,2)=3$ $mex(0,2,3)=1$
很好理解，对吧？
我们可以抽象一下。
由于博弈是单人游戏，而且有“双方都做出最优决策”这一点限制了，所以最后的结果只取决于你面对的局面。
很简单，如果结果像象棋一样取决与你和对手的策略（不一定最优），那还叫你做什么，这又不是交互式题目。
开始即结束，大家一开始就知道结果了，是不是有点凄凉？
那么我们所谓的$SG$值其实是指这一局面的$SG$值。
既然我们的$SG$值只取决于局面，那我们将局面看作一个个点，如果我们有操作可以使得局面$A$变成局面$B$，那么我们在局面$A$所代表的点和局面$B$所代表的点连边，方向从局面$A$所代表的点和局面$B$所代表的点，同时我们称状态$B$是状态$A$的后继状态。
然后画画图，我们发现，这就是个$DAG$。


$\uparrow$ 图来自龙杉老师的Sprague-Grundy Function-SG函数—博弈论(3)。

然后我们定义的$P$状态和$N$状态。
$P$状态（$Positive$状态），指在这一局面下存在使操作者胜利的操作方法。
$N$状态（$Negative$状态），指在这一局面下不存在存在使操作者胜利的操作方法。
其中汇点是$P$状态。
那么我们考虑如何推导当前状态。
有一个很显然的定理（不知道算不算定理，姑且算定理）。
对于每一个$P$状态，它的后继状态一定全是$N$状态。
对于每一个$N$状态，它的后继状态有一部分是$P$状态。
逆定理也成立。
口胡证明一波，如果当前状态的后继状态有$P$状态，那么根据“双方都做出最优决策”限制，对手一定会做操作将当前状态变成后继状态中的$P$状态，那么你就挂了，所以是$N$状态，而如果当前状态的后继状态全是$N$状态，对手怎么操作都是$N$状态，那么它就挂了，所以是$P$状态。


$\uparrow$ 图来自龙杉老师的Sprague-Grundy Function-SG函数—博弈论(3)。

现在就介绍$Sprague-Grundy$定理（$SG$定理）：
如果$Game_1$和$Game_2$是公平游戏，那么他们的总游戏是另一个公平游戏（$Game_1$和$Game_2$是子游戏）。
总游戏规则：在每个回合，一个玩家玩其中一个游戏，不碰另一个游戏。当 $Game_1$ 和 $Game_2$ 都结束时总游戏结束。

如果 $Graph_1 = (V_1, E_1)$ 和 $Graph_2 = (V_2, E_2)$是$Game_1$和$Game_2$分别的$DAG$，那么我们将总游戏 $Graph = (V _ {sum}, E _ {sum}) $规定为：

如果我们有这两个游戏的$DAG$——$Graph_1$和$Graph_2$。并且我们知道单个游戏的P状态和N状态。那么我们能够知道总游戏的$DAG$吗？
显然不行。
不难看出两个P状态的和总是P状态，P状态和N状态的和总是N状态。
但是两个N状态的和既可能是P状态也可能是N状态。因此，只知道单个游戏的P状态和N状态是不够的。

所以为了正确地玩游戏和我们需要推广$P$状态和$N$状态，它就是$Sprague-Grudy$函数（$SG$函数）。
我们定义$SG$函数的值$SG_x = mex ( SG_y ) | (x,y) \in E _ {sum}$。


$\uparrow$ 图来自龙杉老师的Sprague-Grundy Function-SG函数—博弈论(3)。

那么它有什么性质吗？
肯定有啊。

性质1：点$x$是$P$状态当且仅当$SG_x=0$
性质2：如果$Graph = Graph_1 + Graph_2$且 点$x = x_1+x_2$ 是$Graph$的一个点，那么$SG_x$ 为$SG _ {x_1}$ 和 $SG _ {x_2}$ 在二进制下的异或：
即

也称作$nim$和。

实现

对于一个游戏，我们先将其分为几个互不相干的子游戏，求出每个子游戏的$SG$值，再用$nim$和合并一下就知道了总游戏的状态，然后看看是$P$态还是$N$态就知道结果了。
嗯…似乎很有道理。
但子游戏的$SG$值怎么求呢？

1.可选步数为1~m的连续整数，直接取模即可，SG(x) = x % (m+1);
2.可选步数为任意步，SG(x) = x;
3.可选步数为一系列不连续的数，用模板计算。
方法一：打表 $f[]$可以取走的石子个数,注意$f[]$需要从小到大排序 $sg[]$$SG$函数值；$vis[]$标记数组，用于求$mex{}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int f[MAXN],sg[MAXN];
bool vis[MAXN];
void getSG(int n)
{
    sort(f+1,f+1+n);
    memset(sg,0,sizeof(sg));
    for (int i=1; i<=n; i++)
    {
        memset(vis,0,sizeof(vis));
        for (int j=1; f[j]<=i; j++)//f排序是为了让每一种取法都循环到
            vis[sg[i-f[j]]]=1;
        for (int j=0; j<=n; j++)
        {
            if (vis[j]==0)
            {
                sg[i]=j; break;
            }   
        }
    }
}

方法二：$dfs$ $s$数组是定义特殊取法规则的数组，注意要按照从小到大排序；$n$表示集合大小 $SG$函数要初始化为$-1$，每个集合只需初始化一遍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int s[MAXN],sg[MAXN],n;
bool vis[MAXN];
int SG_dfs(int x)
{
    if (sh[x]!=-1)
        return sg[x];
    memset(vis,0,sizeof(vis));
    for (int i=0; i<n; i++)
    {
        if (x>=s[i])
        {
            SG_dfs(x-s[i]);
            vis[sg[x-s[i]]]=1;
        }
    }
    int i=0;
    while (1)
    {
        if (!vis[i])
            return sg[x]=i;
        i++;
    }
}

$\uparrow$ 方法和代码来自秋日私语的洛谷题解。

本题

说了这么多，还是要回归本题。
首先分解本题的子问题，就是一堆$n$个石子，两人分别取石子知道没有办法再取游戏结束。
根据$SG$函数值求法第2条：
$SG_n=n$
于是用$nim$和搞出本题总$SG$函数值。
即

再用$SG$函数值的性质判状态。
这就是本题解法的来历。
博弈$SG$一波带走。
之前没学过博弈$SG$的时候一直不知道这个简单的异或做法是怎么来的，结果学了博弈$SG$就是道水题。

参考资料

博弈SG

龙杉老师的 Sprague-Grundy Function-SG函数—博弈论(3) 讲的非常详细。
秋日私语的 [学习笔记] （博弈论）Nim游戏和SG函数 有经典模型和题目总结。
Enstein_Jun的 组合游戏 - SG函数和SG定理
Must_so的 ACM博弈学习小结
Flying_Fatty的 博弈 SG函数

拓展资料

自为风月马前卒的 博弈论进阶之Multi-SG
自为风月马前卒的 博弈论进阶之Every-SG
myjs999的 博弈论 SG函数 SG定理
kuangbin的 【转】博弈-翻硬币游戏
celia01的 由poj 1067引发的——取石子游戏【各类取石子总结】 各类博弈问题的总结。

本题

秋日私语的洛谷题解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
	read(b...);
}
int T,n;
int main()
{
	T=read<int>();
	for(int tot=1;tot<=T;tot++)
	{
		n=read<int>();
		int tmp=0;
		for(int i=1;i<=n;i++)tmp^=read<int>();
		puts(tmp? "Yes":"No");
	}
    return 0;
}