题解

若后继状态存在偏序关系（即如果状态$S_1$可以转移到$S_2$，状态$S_2$可以转移到状态$S_3$时，那么$S_1$一定可以转移到$S_3$），假设$SG(S_2)=x$，那么所有$0x-1$的$SG$值都在$S_2$的后继状态中出现过，又因为存在偏序关系，$S_1$的后继状态包含$S_2$的所有后继状态。所以$0x-1$和$x$的$SG$值一定在$S_1$的后继状态出现过，所以$SG(S_1)>x$。又因为$SG$是未在后继状态中出现过的最小自然数，所以$SG(S_1)=max_{t为1的后继状态}(SG_t)+1$。至此我们就将复杂度取$mex$问题转化为了更为简单的取$max$问题。

（由排列区间取$mex$转化为区间外取$min$和后继状态存在偏序关系的$SG$函数计算转化为取$max$可知，$SG$函数复杂的$mex$运算可以通过问题的性质化为更简单的$min/max$操作）