SG函数总结(入门向+简单数学证明)

超、凢脫俗 2021-09-15 19:00 446阅读 0赞

在谈SG函数之前，我们先看一个关于有向图游戏的定义。  
**有向图游戏**

> 给定一个有向无环图和一个起始顶点上的一枚棋子，两名选手交替的将这枚棋子沿有向边进行移动，无法移动者判负。

事实上我们可以发现**任何一个ICG(公平组合游戏)都可以转化成有向图游戏**。具体方法为，把每个局面看成图的一个节点，并且从每个局面向能到达的局面连有向边。

然后我们再来了解一个Mex运算。  
**Mex(minimal excludant)运算**

> [Mex wiki][]  
> In mathematics, the mex of a subset of a well-ordered set is the smallest value from the whole set that does not belong to the subset. That is, it is the minimum value of the complement set. The name “mex” is shorthand for “minimum excluded” value.

我们这里可以简单点理解，给一个非负整数集合S，mex(S)为求出**不属于集合S**的**最小**非负整数的运算。例如mex(0,1,2,4,5)=3  m e x ( 0 , 1 , 2 , 4 , 5 ) = 3 、 mex(2,3,5)=0  m e x ( 2 , 3 , 5 ) = 0 、mex()=0  m e x ( ) = 0

接着就到了本文的核心，SG函数

# **SG函数** #

> 对于一个给定的有向无环图，定义关于图的每个顶点的SG函数SG如下，**SG(x)  S G ( x ) = mex  m e x (\{ SG(y1)  S G ( y 1 )  ,SG(y2)  S G ( y 2 ) ,…,SG(yk)  S G ( y k ) \}) (y  y 是x x的后继)** 。

我们怎么理解这个函数呢？在有向图游戏中，对于每个节点x  x ，设从x x出发共有k  k 条有向边，分别到达节点y1 y 1,y2  y 2 ,…,yk  y k ，SG(x)  S G ( x ) 为x  x 的后继节点的SG S G函数值构成的集合再执行mex  m e x 运算的结果为该节点x  x 的SG S G函数值  
**整个有向图游戏G  G 的SG S G函数值被定义为有向图游戏起点的SG  S G 函数值**

## 有向图游戏的和 ##

> **有向图游戏的和的SG  S G 函数值等于它包含的各个子游戏SG  S G 函数值的异或值**

#### 定理 ####

> 有向图游戏的某个局面**必胜**，***当且仅当***该局面对应节点的SG  S G 函数值大于0  
> 有向图游戏的某个局面**必败**，***当且仅当***该局面对应节点的SG  S G 函数值等于0

### 证明 ###

> [Sprague–Grundy\_theorem Wiki][Sprague_Grundy_theorem Wiki]

这里给出一点简单的个人理解：  
*1*.在一个**没有出边**的节点s  s 上，棋子不能移动，SG(s) S G ( s ) =  =  0 0 ,对应P局面

*2*.一个节点k  k 的SG S G函数值**大于0  0** ，则其后继节点必有一个节点s s的SG  S G 函数值等于0  0 ，由1得节点s对应P局面，则当前节点k对应的局面为N局面

*3*.一个节点的后继节点SG S G函数值均不为0  0 ，则该节点的SG S G函数值为0  0 。可推出**若一个局面的后继局面全部为N局面，则当前局面为P局面**。

以下为SimonS大佬的SG S G函数模板

define MAX 1005
    /* 计算从1-n范围内的SG值。 Array(存储可以走的步数，Array[0]表示可以有多少种走法) Array[]需要从小到大排序 */
    /*HDU1847博弈SG函数 1.可选步数为1-m的连续整数，直接取模即可，SG(x) = x % (m+1); 2.可选步数为任意步，SG(x) = x; 3.可选步数为一系列不连续的数，用GetSG(计算) */
    int SG[MAX], hash[MAX];
    void GetSG(int Array[],int n = MAX-1)
    {
        memset(SG, 0, sizeof(SG));
        for(int i = 0; i <= n; ++i)
        {
            memset(hash, 0, sizeof(hash));
            for(int j = 1; j <= Array[0]; ++j)
            {
                if(i < Array[j])
                    break;
                hash[SG[i - Array[j]]] = 1;
            }
            for(int j = 0; j <= n; ++j)
                if(!hash[j])
                {
                    SG[i] = j;
                    break;
                }
        }
    }

*\*基于lyd的<<算法竞赛进阶指南>>和部分集训队论文写成*

[Mex wiki]: https://en.wikipedia.org/wiki/Mex_%28mathematics%29
[Sprague_Grundy_theorem Wiki]: https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem