博弈论之SG函数

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

定义：
luogu P2197 【模板】nim 游戏
Nim游戏是经典的公平组合游戏(ICG)，对于ICG游戏我们有如下定义：

• 两名选手
• 两名选手轮流行动，每一次行动可以在有限合法操作集合中选择一个
• 游戏的任何一种可能的局面(position)，合法操作集合只取决于这个局面本身，不取决于轮到哪名选手操作、以前的任何操作、骰子的点数或者其它因素；局面的改变称为“移动”(move)
• 如果轮到某名选手移动，且这个局面的合法的移动集合为空（也就是说此时无法进行移动），则这名选手输掉比赛

对于第三条，我们有更进一步的定义Position，我们将Position分为两类：

P-position：在当前的局面下，先手必败
N-position：在当前的局面下，先手必胜

它们有如下性质：

合法操作集合为空的局面是P-position
可以移动到P-position的局面是N-position
所有移动都只能到N-position的局面是P-position

我们对于此题，明显不可以用dfs,bfs等暴力模拟，So，引出我们的主题————

SG函数：

事实上，任何一个ICG游戏都可以通过把每个局面看成一个顶点，对每个局面和它的子局面连一条有向边来抽象成这个“有向图游戏”。下面我们就在有向无环图的顶点上定义SG(Sprague-Garundy)函数。

先介绍 mex 运算，这是施加于一个集合的运算，表示最小的不属于(没出现过)这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

定义关于图的每个顶点的SG函数sg如下：sg(x)=mex{ sg(y1),sg(y2),sg(y3)… }(所有x出边所连的y)。也就是说，一个点的SG函数为在它所有后继中都未出现的最小的值。

ps:此处后继不为Splay中的后继，为所有x出边所连的y

对于一个sg(x)=0的顶点x，它的所有后继y都满足 sg(y)≠0。
对于一个sg(x)≠0的顶点，必定存在一个后继y满足sg(y)=0。

可以发现，顶点x所代表的postion是P-position当且仅当sg(x)=0，x点必先手败（跟P-positioin/N-position的定义是完全对应的）

如果如nim游戏，有 n 堆石子，我们只需将其拆成 n 个子游戏
So, sg(总体)=sg(子游戏1) ^ (子游戏2) ^ (子游戏3) ^ … ^ (子游戏n)

SG值的计算方法（重点）
可选步数为1~m的连续整数，直接取模即可，sg(x) = x % (m+1);
可选步数为任意步，sg(x) = x;
可选步数为一系列不连续的数，用"模板"计算。

又到了 喜闻乐见 的抄代码环节！
code:

int f[12],sg[1021];//f[]记录一次可取石子数
bool mex[1021];
void getSG(int n){//注意f[]要从小到大sort排序
	for (int i=1;i<=n;i++){
		for(int j=0;j<=n;j++)mex[j]=false;
		for (int j=1;f[j]<=i&&j<=m;j++)mex[sg[i-f[j]]]=1;//查后继的sg值
		for (int j=0;j<=n;j++)if(!mex[j]){sg[i]=j;break;}//查i的sg值
	}
}

ps:其实还有一种dfs的方法求sg,但博主是jrlqw(大蒟蒻)，不会打…其实是觉得dfs不好,太复杂了

拓展：

51nod 3431 取石子游戏
题意：
A君和B君正在玩一个取石子游戏。 取石子游戏的规则是这样的，每个人每次可以从N堆中从一堆石子中取出若干个石子，每次取石子的个数有限制(会给出每次可取的个数，不同无规律)，谁不能取石子时就会输掉游戏。 A君先进行操作，他想问你他是否有必胜策略，如果有，第一步如何取石子,在哪堆取几个？

输入文件的第一行为石子的堆数N，接下来N行，每行一个数Ai，表示每堆石子的个数。接下来一行为每次取石子个数的种类数M，接下来M行，每行一个数Bi，表示每次可以取的石子个数，输入保证这M个数按照递增顺序排列。

输出文件第一行为“YES”或者“NO”，表示小H是否有必胜策略。 若结果为“YES”,则第二行包含两个数，第一个数表示从哪堆石子取，第二个数表示取多少个石子，若有多种答案，取第一个数最小的答案，若仍有多种答案，取第二个数最小的答案。

数据规模和约定
数据编号 N范围 Ai范围 数据编号 N范围 Ai范围
1 N=2 Ai≤10 6 N≤10 Ai≤10
2 N=2 Ai≤1000 7 N≤10 Ai≤100
3 N=3 Ai≤100 8 N≤10 Ai≤1000
4 N≤10 Ai≤4 9 N≤10 Ai≤1000
5 N≤10 Ai≤7 10 N≤10 Ai≤1000
对于全部数据，M≤10，Bi≤10

样例
input：
4
7 6 9 3
2
1 2
output:
YES
1 1

tips:用sg值解，如果可行，先手必胜，第一步如何取石子,在哪堆取几个？如何判断呢？设在第 i 堆取第 j 中的个数个，N堆的sg值的xor和为all ，如果 all ^ sg[a[i]] ^ sg[a[i]-f[j]] == 0 则 可于 第 i 堆取 f[j] 个！(可用sg的意义&N、P局面来理解，从胜败角度判断)

最后，希望大家都可以从中学习到有用的知识，希望这篇文章对你有帮助

(反正博主觉得很有收获)