博弈论

mex运算

定义mex运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。

如 、 、

可以用bitset来计算mex的值:

int mex(bitset<N> b)
{
    int i = 0;
    while(b[i++]);
    return i - 1;
}

SG函数

当先手 时，则先手在 状态时必败

例：取石子问题

有一堆n个的石子，两个人轮流取石子，每次只能取1、3、4个石子，先取完石子者胜利，两个人都足够聪明，求先手是否必赢。

当 为0-5时，sg函数的值如下：

即 为 时，先手必败； 为 时必胜。

石子数为1-5的后继关系如下图所示

SG定理

若一个游戏可以拆分成多个游戏，则该游戏的胜负取决于每个游戏的sg函数值的异或和。
即对于任意游戏
有

表示异或