[SG函数] 2021牛客寒假集训营6 H.寒冬信使2

传送门：H-寒冬信使2_2022牛客寒假算法基础集训营6 (nowcoder.com)

思路

首先回顾公平组合博弈的P点和N点：

• 所有终结点是必败点(P-Position)
• 从任何必胜点(N-Position)操作，至少存在一种方法进入必败点(P-Position)
• 无论如何操作，从必败点只能进入必胜点(N-Position)

那么我们开始分析本题目：

1. 采用二进制枚举的方式，用 0 0 0代表 b b b， 1 1 1代表 w w w，这样可以枚举一定长度内所有的组合。
2. 对于每一个状态，枚举能否进入必败态(初始必败态为 0 0 0)，如果能则标记为必胜态。
3. 对于两种操作而言：
   • 第一个格子为白色，可以直接反转第一个格子时：如果翻转第一个格子后是必败态，那么标记当前状态为必胜态
   • 对于其余格子而言，如果它完成第一类翻转后能够进入之前的任何一个必败态，那么标记当前状态为必败态

那么根据以上两个操作的性质，我们可以写出 S G SG SG打表函数：

int sg[N];
inline void getsg(){
    for(int i = 1; i