简单博弈论：公平组合游戏

组合游戏"/>

简单博弈论：公平组合游戏

若一个游戏满足：

1. 由两名玩家交替行动
2. 在游戏进行的任意时刻，可以执行的合法行动与轮到哪位玩家无关
3. 不能行动的玩家判负

则称该游戏为一个公平组合游戏。

尼姆游戏（NIM）属于公平组合游戏，但常见的棋类游戏，比如围棋就不是公平组合游戏，因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和3。

有向图游戏

将公平组合游戏看作一个有向无环图，图中有一个唯一的起点，在起点放有一枚棋子。两名玩家交替把这枚棋子沿着有向边进行移动，每次可以移动一步，无法移动判负。任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连接有向边。

Mex运算

设 S S S表示一个非负整数集合，定义 m e x ( S ) mex(S) mex(S)为求出不属于集合 S S S的最小非负整数的运算即： m e x ( S ) = m i n ( x ) mex(S) = min(x) mex(S)=min(x)， x x x属于自然数，且 x x x不属于集合 S S S。
例如：集合$S = {1, 2, 3} $，那么 m e x ( S ) = 0 mex(S) = 0 mex(S)=0， 0 0 0为不在集合 S S S中的最小自然数。

SG函数

在有向图游戏中，对于每个结点 x x x，设从 x x x出发共有 k k k条边，分别到达节点 y 1 , y 2 , . . . , y k y_1, y_2, ..., y_k y1​,y2​,...,yk​，定义 S G ( x ) SG(x) SG(x)为 x x x的后继节点 y 1 , y 2 , . . . , y k y_1, y_2, ..., y_k y1​,y2​,...,yk​的 S G SG SG函数值构成的集合S、再执行 m e s ( S ) mes(S) mes(S)运算的结果，即： S G ( x ) = m e x ( S G ( y 1 ) , S G ( y 2 ) , . . . , S G ( y k ) ) SG(x) = mex(SG(y_1), SG(y_2), ..., SG(y_k)) SG(x)=mex(SG(y1​),SG(y2​),...,SG(yk​))
特别地，整个有向图游戏 G G G的 S G SG SG函数值被定义为有向图游戏起点 S S S的 S G SG SG函数值， S G ( G ) = S G ( S ) SG(G) = SG(S) SG(G)=SG(S)

例如，有如下有向图游戏，黄色为起点，绿色为终点，首先定义 S G ( 终 点 ) = 0 SG(终点) = 0 SG(终点)=0，那么可以推导出其它各点的 S G ( ) SG() SG()函数值：

在有向图游戏中判断某个状态 x x x（图中一点），如果：

1. S G ( x ) = 0 SG(x) = 0 SG(x)=0，为必败态。首先终点状态是 0 0 0，任何一个 0 0 0状态，在有向图中都无法直接到达一个 0 0 0状态。先手如果为0，无法通过操作将状态变为0，即留给后手一个必胜态。
2. S G ( x ) ≠ 0 SG(x) ≠ 0 SG(x)​=0，为必胜态。任何一个非 0 0 0状态，在有向图中必然可以直接到达一个 0 0 0状态。先手如果非 0 0 0，可以通过操作将状态变为 0 0 0，即留给后手一个必败态。

有向图游戏的和

设 G 1 , G 2 , . . . , G m G_1, G_2, ... , G_m G1​,G2​,...,Gm​是 m m m个有向图游戏。定义有向图游戏 G G G，它的行动规则是任选某个有向图游戏 G i G_i Gi​，并在 G i G_i Gi​上行动一步。 G G G被称为有向图游戏 G 1 , G 2 , . . . , G m G_1, G_2, ... , G_m G1​,G2​,...,Gm​的和。
有向图游戏的和的 S G SG SG函数值等于它包含的各个字游戏 S G SG SG函数值的异或和，即：
S G ( G ) = S G ( G 1 ) ⊕ S G ( G 2 ) ⊕ . . . ⊕ S G ( G m ) SG(G) = SG(G1) \oplus SG(G2) \oplus ... \oplus SG(G_m) SG(G)=SG(G1)⊕SG(G2)⊕...⊕SG(Gm​)

证明：参考尼姆游戏的证明。

#include <bits/stdc++.h>using namespace std;const int N = 110, M = 10010;
int k, n;
//s[]表示每次拿取的石子数量的集合
//dp[]记忆化搜索，dp[i]记录sg[i]
int s[N], dp[M];int sg(int x){//记忆化搜索，如果已经计算过，直接返回if(dp[x] != -1) return dp[x];//S存放从x出发、所有能到的局面的sg函数值set<int> S; for(int i = 0; i < k; i++){int sum = s[i]; //取走个数if(x >= sum){ //能从x中能取走sumS.insert(sg(x - sum)); //将取走后的局面加入到集合S中}}//mex(S)，求集合S中不存在的最小的自然数for(int i = 0; ; i++){if(S.count(i) == 0) return dp[x] = i;}}int main(){memset(dp, -1, sizeof dp);cin>>k;for(int i = 0; i < k; i++) cin>>s[i];cin>>n;int res = 0;for(int i = 0; i < n; i++){int x;cin>>x;res ^= sg(x);}if(res) puts("Yes");else puts("No");return 0;
}