SG函数
SG函数的坑弃了很久了……高一的大佬已经开始D我了…… 什么是SG函数 首先我们需要知道，有限状态博弈问题可以表示为一个DAG， 每个节点表示一个局面 ，而每个选择就相当于一条边。 例如取石子问题。一共 5 5 个石子，玩家可以取两个或者取一个，先取完者胜。那么这个图是长成这样的： 点上的数表示“在这个局面下，还有多少个点没有被取”。 这个图上有“P点”和“N点”。 P点 表示必败点， N点 表示必不败点（在这个图中，就是必胜点）。关于P点和N点，我们作如下约定： 无路可走的点称为“终点”(Terminal)。终点是P点。 如果一个点能走向P点，那么它是N点。因为 可以 让对手输。 如果一个点只能走向N点，那么它是P点。因为 只能 让对手赢。 那么根据这几个约定，上面的博弈图可以画成下面这样。橙色表示P点，绿色表示N点。 上图的意思是，遇到 3 3 或 0 0 局面的玩家必败，否则必胜。由于 5 5 是N点，所以这个游戏是先手必胜的。（先手取两个石子，使对手面临 3 3 的局面，即可获胜） 那么什么是SG函数呢？SG函数就是判断了上面的三个约定，并把结果用数值表示出来。 我们首先定义 mex mex 运算，它是作用于集合上的运算。设 S S 是一个整数集合，则 mex ( S ) mex ( S ) 表示没有在 S S 中出现的最小非负整数。 例如， { 0 , 1 , 2 , 4 } { 0 , 1 , 2 , 4 } 的 mex mex 值是 3 3 ， { 1 , 2 , 3 } { 1 , 2 , 3 } 的 mex mex 值是 0 0 ， { } { } 的 mex mex 值是 0 0 。 在之前的图上，每个点表示一个状态。 SG函数给了每个点一个值： s g ( x ) = mex { s g ( p ) | p 是 x 的 儿 子 节 点 } s g ( x ) = mex { s g ( p ) | p 是 x 的 儿 子 节 点 } 。终点的 s g s g 值是0。 如果 s g ( x ) s g ( x ) 为 0 0 ，那么 x x 是 P点 ；否则 x x 是 N点 。 SG函数有一个神奇的特性：如果一个游戏可以分成几个同时进行的子游戏，那么...