给定一个有向无环图和一个起始顶点上的一枚棋子,Alice和Bob交替的将这枚棋子沿有向边进行移动,无法移动者判负。问是否有必胜策略。
首先定义 \(\text{mex}\) 运算,这是施加于一个集合的运算,表示最小的不属于这个集合的非负整数。例如 \(\text{mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0}\)。
对于一个给定的有向无环图,定义关于图的每个顶点的 \(\text{SG}\) 函数 \(\text{sg}\) 如下:\(\text{sg(x)=mex{ sg(y) | y是x的后继 }}\)。也就是说,一个点的 \(\text{SG}\) 函数为在它所有后继中都未出现的最小的值。
通过 \(\text{sg}\) 函数,我们可以把所有 \(\text{ICG}\) 游戏转换成 \(\text{Nim}\) 游戏,后手必胜当且仅当 \(\text{sg}\) 的异或和为 \(\text{0}\) 。
1. 把原游戏分解成多个独立的子游戏,则原游戏的SG函数值是它的所有子游戏的SG函数值的异或。
即:
\[sg(G)=sg(G_1)⊕sg(G_2)⊕…⊕sg(G_n) \]2. 分别考虑没一个子游戏,计算其 \(\text{SG}\) 值。
\(\text{SG}\) 值的计算方法:(重点)
可选步数为 \(1\)~\(\text{m}\) 的连续整数,直接取模即可,\(\text{SG(x)=x%(m+1)}\);
可选步数为任意步,\(\text{SG(x) = x}\);
可选步数为一系列不连续的数,用模板计算。