- 巴什博弈
- 尼姆博弈
- SG函数
- 公平组合游戏
- 有向图游戏
- Mex运算
- 遇到的一些不错的博弈题：
问题：
只有一堆 n n n个物品，两个人轮流从这堆物品中取物， 规定每次至少取一个，最多取 m m m个。最后取光者得胜。
- 若只有 0 0 0 ~ m m m个物品，先手必胜。
- 若有 m + 1 m+1 m+1个物品，先手必败。因为先手最多取m个，不管先手取多少个，后手都可以一次取完
- 若有
(
m
+
1
)
+
r
,
(
1
<
=
r
<
=
m
)
(m+1)+r,_{(1<=r<=m)}
(m+1)+r,(1<=r<=m)个，先手必胜。这种情况下，先手可以拿
r
r
r个，轮到后手拿的时
候，就是第二种情况，此时，后手就是必败的，先手必胜。 - 类似的，若有 k ( m + 1 ) + r k(m+1)+r k(m+1)+r个物品，那么先手可以先拿 r r r个，然后假设后手拿了 x ( x < = m ) x_{(x<=m)} x(x<=m)个，先手可以拿 ( m + 1 ) − x (m+1)-x (m+1)−x个，这样以此进行，每次后手和先手那的总和都是 m + 1 m+1 m+1个，并且总是先手拿到最后一部分。当只剩下 m + 1 m+1 m+1个时，一定是后手先拿一部分，然后先手就可以全部拿走了。
总结就是：
当
(
m
+
1
)
∣
n
(m+1)|n
(m+1)∣n的时候，后手必胜，否则，先手必胜。
扩展：
上面是先拿光这
n
n
n个物品的赢，如果改成先拿光这
n
n
n个物品的输该怎么办呢？
这个问题可以转化成先拿光
n
−
1
n-1
n−1个物品的赢（此时就只剩下
1
1
1个给对方拿了）。
所以就是
(
m
+
1
)
∣
(
n
−
1
)
(m+1)|(n-1)
(m+1)∣(n−1)的时候，后手必胜，否则，先手必胜。
尼姆博弈
问题：
有 n n n堆石子，每堆石子的数量是有限的，两个人依次从这些石子堆中拿取任意的石子，至少一个（不能不取），最后一个拿光石子的人胜利。
先抛出结论： 如果 a 1 a_1 a1 ^ a 2 a_2 a2 ^ … ^ a n = 0 a_n=0 an=0，那么先手必败，否则，先手必胜。
证明:
当所有物品都被取光的时候，显然有 a 1 a_1 a1 ^ a 2 a_2 a2 ^ … ^ a n = 0 a_n=0 an=0。
而对于任意一个
a
1
a_1
a1 ^
a
2
a_2
a2 ^ … ^
a
n
≠
0
=
x
a_nneq0=x
an=0=x的 局面，设x的二进制表示中最高位的是
1
1
1第
k
k
k位，那么在至少有一堆石子
a
i
a_i
ai，它的二进制表示的第
k
k
k位一定也是
1
1
1。那么一定有
a
i
a_i
ai ^
x
<
a
i
xx
a
1
a_1
a1 ^
a
2
a_2
a2 ^
.
.
.
...
...^
a
i
′
a_i^{'}
ai′^
.
.
.
...
... ^
a
n
a_n
an
=
a
1
=a_1
=a1 ^
a
2
a_2
a2 ^
.
.
.
...
...^
a
i
a_i
ai^
.
.
.
...
... ^
a
n
a_n
an ^
x
x
x
=
x
=x
=x ^
x
x
x
=
0
=0
=0
-
所以，对于异或值不等于 0 0 0的情况，我们一定可以将其变成异或值等于 0 0 0的情况。
-
而对于异或值等于 0 0 0的情况，取过石子后，就一定会变成异或值不等于 0 0 0的情况（证明可以用反证法）。
所以，如果先手一开始就处于异或值等于 0 0 0的情况，那么，以后的每一步，当轮到先手时，他得到的总是异或值等于 0 0 0的情况，最终，先手一定会输。
扩展：
台阶-尼姆游戏：
现在，有一个
n
n
n级台阶的楼梯，每级台阶上都有若干个石子，其中第
i
i
i级台阶上有
a
i
a_i
ai个石子(
i
>
=
1
i>=1
i>=1)。两位玩家轮流操作，每次操作可以从任意一级台阶上那若干个石子放到下一级台阶中（不能不拿）。已经拿到地面上的石子不能在拿，最后无法进行操作的人视为失败。
该题的神奇做法是只考虑奇数级台阶的异或和（本废物表示根本想不到 QAQ）。
如果所有的奇数级台阶的异或和
a
1
a_1
a1 ^
a
3
a_3
a3 ^ …^
a
k
≠
0
a_kneq0
ak=0。那么先手必胜。否则，先手必败。
这是为什么呢？
简单证明：
假设一开始有所有的奇数级台阶的异或和
a
1
a_1
a1 ^
a
3
a_3
a3 ^ …^
a
k
≠
0
a_kneq0
ak=0。
那么，根据前面的证明，先手一定可以在某一个奇数级台阶上拿若干个放到下面的偶数级台阶上，从而使得
a
1
a_1
a1 ^
a
3
a_3
a3 ^ …^
a
k
=
0
a_k=0
ak=0。接下来轮到了后手拿，分为两种情况：
- 后手在奇数级台阶上拿。这势必会使得所有奇数级台阶的异或和 a 1 a_1 a1 ^ a 3 a_3 a3 ^ …^ a k ≠ 0 a_kneq0 ak=0。此时，先手就可以继续之前的操作，使的奇数级台阶上的异或和再次为 0 0 0。
- 后手在偶数级台阶上拿。后手在偶数级台阶上拿过后一定放在了奇数级台阶上，那么此时先手可以把后手刚刚拿过的石子在次拿到下一级台阶上(偶数级)，那么所有奇数级台阶上的石子数相当于没有变，异或和仍然是 0 0 0。
所以，无论如何，轮到先手时，所有奇数级台阶的异或和总是不为 0 0 0的；而轮到后手时，所有的奇数级台阶的异或和总是为 0 0 0的。
那么，经过有限次操作后，轮到后手时，所有的奇数级台阶上的石子一定都为 0 0 0。后手只能去拿偶数级台阶上的石子，然后放到下面的台阶上。然后轮到先手，先手就可以重复后手的操作，把后手刚刚拿过的石子再次放到下面的台阶上。可以证明，此时先手一定是必胜的。（因为后手只能在偶数级台阶上拿）
还有斐波那契博弈和威佐夫博奕，由于还不会证明，先鸽了orz。
SG函数 公平组合游戏
如果一个游戏满足。
1、由两名玩家交替进行。 2、在游戏的任意时刻，可以执行的合法行动与轮到哪名玩家无关。 3、不能行动的玩家判输。
那么这种游戏就属于公平组合游戏。尼姆游戏就是一种公平组合游戏。
有向图游戏给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判输。这种游戏被称为有向图游戏。
任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每一个局面看作图中的一个点，并且从每一个局面向它可以合法转移到的局面连一条有向边。
Mex运算设 S S S表示一个非负整数集合。定义 m e x ( S ) mex(S) mex(S)为集合 S S S中没有出现过的最小非负整数。
s
g
sg
sg函数就是对于一个有向图游戏中的每一个点
x
x
x都有一个
s
g
(
x
)
sg(x)
sg(x)。
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的sg函数所构成的集合的
m
e
x
mex
mex运算的结果，即：
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)})
根据这个，一定有有向图中出度为
0
0
0的点的
s
g
=
0
sg = 0
sg=0。
- 对于只有一个有向图游戏 G G G的游戏来说。
设起点为 s s s。
如果 s g ( s ) = 0 sg(s)=0 sg(s)=0（这样的点叫做必败点），先手必败，否则（必胜点），先手必胜。
简单证明：
首先，有有向图中游戏结束的时候一定是走到了一个出度为 0 0 0的点，同时，它的 s g sg sg一定是 0 0 0。
如果
s
g
sg
sg不等于
0
0
0，那么一定可以从该点走到个
s
g
sg
sg为
0
0
0的点。
如果
s
g
=
0
sg=0
sg=0，那么从该点一定走不到一个
s
g
=
0
sg=0
sg=0的点。
所以，如果起点 s s s的 s g ( s ) = 0 sg(s)=0 sg(s)=0，那么它只能留给后手到一个 s g sg sg不等于 0 0 0的点，然后后手一定可以留给先手一个 s g = 0 sg=0 sg=0的点，这样以来，先手永远只能在 s g = 0 sg=0 sg=0的点上操作，最终，先手一定是走到了一个出度为 0 0 0的点，然后就gg了。
- 对于 m m m个有向图游戏 G 1 , G 2 , . . . , G m G_1,G_2,...,G_m G1,G2,...,Gm来说，它的行动是在 m m m个有向图中任选一个进行操作，如果 m m m个都无法进行操作了，那么就输了。
设起点分别是 s 1 , s 2 , . . . , s m s_1,s_2,...,s_m s1,s2,...,sm。
如果 s g ( s 1 ) sg(s_1) sg(s1) ^ s g ( s 2 ) sg(s_2) sg(s2) ^ . . . ... ... ^ s g ( s m ) = 0 sg(s_m)=0 sg(sm)=0，那么先手必败，否则，先手必胜。
该结论的证明与上面尼姆游戏的证明类似。
简单来说就是：
首先，当每一个有向图游戏的起点都是无法继续操作的点，有 s g ( s 1 ) sg(s_1) sg(s1) ^ s g ( s 2 ) sg(s_2) sg(s2) ^ . . . ... ... ^ s g ( s m ) = 0 sg(s_m)=0 sg(sm)=0
类似的，如果
s
g
(
s
1
)
sg(s_1)
sg(s1) ^
s
g
(
s
2
)
sg(s_2)
sg(s2) ^
.
.
.
...
... ^
s
g
(
s
m
)
≠
0
=
x
sg(s_m)neq0=x
sg(sm)=0=x。
那么，我们一定可以移动某一个
s
g
(
s
i
)
sg(s_i)
sg(si)使得
s
g
(
s
i
)
sg(s_i)
sg(si)变成
s
g
(
s
i
)
′
=
s
g
(
s
i
)
sg(s_i)^{'}=sg(s_i)
sg(si)′=sg(si) ^
x
x
x。
这样以来就有
s
g
(
s
1
)
sg(s_1)
sg(s1) ^
s
g
(
s
2
)
sg(s_2)
sg(s2) ^
.
.
.
...
... ^
s
g
(
s
i
)
′
sg(s_i)^{'}
sg(si)′ ^
.
.
.
...
... ^
s
g
(
s
m
)
=
0
sg(s_m)=0
sg(sm)=0
也就是说，我们一定可以从一个异或值不为 0 0 0的状态，通过一步操作变成异或值为 0 0 0的状态。
同时有，一个异或值为 0 0 0的状态只能走到异或值不为 0 0 0的状态（证明可以利用反证法，此处不在做证明）。
所以，如果先手一开始处于所有 s g sg sg的异或值为 0 0 0的情局面，那么后手可以使得他永远只能处于异或值为 0 0 0的局面，这样以来，先手必败。
遇到的一些不错的博弈题：
update 2021.10.22
题目大意:
给出
n
n
n个数，有
A
l
i
c
e
Alice
Alice和
B
o
b
Bob
Bob交替操作这
n
n
n个数，
A
l
i
c
e
Alice
Alice只能操作奇数，有两种操作方式：一是将一个奇数分裂成两个正整数（如
5
5
5–>
2
+
3
2 + 3
2+3），二是将一个等于
1
1
1的数删除（如果数列中没有等于
1
1
1的数就不能删）。
B
o
b
Bob
Bob只能操作偶数，只有一种操作方式，就是每次将一个偶数分裂两个正整数。当一个人无法操作时，他就输了。问最后谁会赢。
只要到最后轮到A时，A还剩至少一个1，并且B只剩下了若干个2。这个时候A就一定赢了，因为B只能把2-->1 + 1。 并且B一定是不能操作2的，否则就是白给行为，2只能变成1 + 1。 而B每次操作只会使一个偶数变小，最终变成2，所以，对A来说她只要能撑到最后就能赢。 接下来就变成了A能不能撑到最后。 对于一个奇数x，A最多能执行的次数是x / 2 + 1。 即每次将x-->2 + (x-2)，执行x/2（整除）次后，x一定变成了若干个2和一个1，最后将1删除也可以撑一个回合 对于一个偶数，B最大能执行的次数是x / 2 - 1。 同样也是每次将x变成x-->2 + (x-2)，执行x/2-1次后，x一定变成了若干个2，这时就不能继续操作了。 设A总共能执行a次，B能执行b次 如果a > b，则A赢，否则B赢。
#include#include #include #include #include #include
