大家好,欢迎来到IT知识分享网。
1.前言
以前一直觉得, s g sg sg 函数只需要用到零和一两个值,表示先手是否必胜。
后来,我发现我错了:那根本不叫 s g sg sg 函数。 s g sg sg 函数,比你想象中要强悍一些!
2.知识储备
2.0.我的书写
我会将 S S S 在 U U U 中的补集写成 U − S U-S U−S,而非 U ∩ S ˉ U\cap\bar S U∩Sˉ 或 ∁ U S \complement_{U}S ∁US 一类的标记。因为 LaTeX \LaTeX LATEX 中的补集符号我一直背不下来。
2.1. m e x mex mex 函数
或者,也可以把它写成:记 x = m e x ( S ) ( x ∈ Z ) x=mex(S)\;(x\in\Z) x=mex(S)(x∈Z),不妨设 S ⫅ Z S\subsete\Z S⫅Z,则
S ∩ [ 0 , x ] = [ 0 , x ) S\cap[0,x]=[0,x) S∩[0,x]=[0,x)
即, m e x mex mex 是没有出现过的最小自然数。
2.2.博弈
后文中将不会讨论 “游戏永远不会结束” 的情况。
如果将游戏看做一张图,点是状态、边是转移,多数情况下,其为 DAG \text{DAG} DAG 。
博弈是有一些性质的。在下方罗列了几点,可能并不严谨,但可以理解。
- 没有后继的状态,胜负情况是明晰的。对于其他的状态:
- 称该状态是必胜状态,当且仅当其存在一个后继是必败状态。
- 称该状态为必败状态,当且仅当其所有后继都是必胜状态。
3. s g \rm sg sg 函数
3.1.定义
对于一个状态 x x x ,其后继状态为 S S S 集合,那么 s g ( x ) = m e x [ s g ( r ) ] ( r ∈ S ) sg(x)=mex[sg(r)]\quad(r\in S) sg(x)=mex[sg(r)](r∈S)
也就是说,一个状态的 s g sg sg 函数值,是其后继的所有 s g sg sg 值取 m e x mex mex 。
如果没有后继呢?没有后继,根据 m e x mex mex 的定义,自然应该是零。
3.2.性质
如果没有后继,毫无疑问,应当是一个已经失败的局面——如果是已经胜利,那么强加给他一个后继,并且该后继是没有后继的。
规定已经失败的局面没有后继。因为它的后继是没有意义的——你根本就不会转移。
那么,我们就有了这样一条:一个状态是必败的,当且仅当其 s g sg sg 函数值为零。
这可以在 DAG \text{DAG} DAG 上利用归纳法证明。用到了博弈的基本性质。
4. s g \rm sg sg 定理
4.1.独立子游戏
将当前游戏划分为 n n n 个子游戏,状态分别为 x 1 , x 2 , x 3 , … , x n x_1,x_2,x_3,\dots,x_n x1,x2,x3,…,xn 。不妨记其 s g sg sg 函数分别为 f 1 , f 2 , f 3 , … , f n f_1,f_2,f_3,\dots,f_n f1,f2,f3,…,fn 。与之相对的,原游戏的 s g sg sg 函数是 f f f、状态是 x x x 。
我们称其为独立子游戏,当且仅当其满足下方的几点性质。
- 原游戏中的失败,对应着所有子游戏的失败。即: f ( x ) = 0 ⇔ ∀ i ∈ [ 1 , n ] , f i ( x i ) = 0 f(x)=0\Leftrightarrow\forall i\in[1,n],\;f_i(x_i)=0 f(x)=0⇔∀i∈[1,n],fi(xi)=0 。
- 每次操作只影响一个子游戏。即:后继状态 x ′ = ⟨ x 1 , x 2 , … , x i − 1 , x i ′ , x i + 1 , … , x n ⟩ x’=\langle x_1,x_2,\dots,x_{i-1},x’_i,x_{i+1},\dots,x_{n}\rangle x′=⟨x1,x2,…,xi−1,xi′,xi+1,…,xn⟩ 。
4.2.定理
如果一个游戏由很多个独立子游戏构成,那么 s g sg sg 值为所有子游戏的 s g sg sg 值的异或。
利用归纳法。如果终止态满足此条件,而转移也满足此条件,则成立。
对于终止态,有 ∀ i ∈ [ 1 , n ] , f i ( x i ) = 0 \forall i\in[1,n],\;f_i(x_i)=0 ∀i∈[1,n],fi(xi)=0,此时是必败,即 f ( x ) = 0 f(x)=0 f(x)=0,显然成立。
对于一个非终止态,设 b = ⨁ i = 1 n f i ( x i ) b=\bigoplus_{i=1}^{n}f_i(x_i) b=⨁i=1nfi(xi),不妨假设 x j x_j xj 存在后继 x j ′ x_j’ xj′ 。
那么 x ′ = ⟨ x 1 , x 2 , … , x j − 1 , x j ′ , x j + 1 , … , x n ⟩ x’=\langle x_1,x_2,\dots,x_{j-1},x’_j,x_{j+1},\dots,x_n\rangle x′=⟨x1,x2,…,xj−1,xj′,xj+1,…,xn⟩ 这个后继的 s g sg sg 值就会成为 b ⊕ f j ( x j ) ⊕ f j ( x j ′ ) b\oplus f_j(x_j)\oplus f_j(x_j’) b⊕fj(xj)⊕fj(xj′) 。
由 m e x mex mex 的定义,只需要证明两点:
- ∀ a ∈ [ 0 , b ) , ∃ x j ′ , b ⊕ f j ( x j ) ⊕ f j ( x j ′ ) = a \forall a\in[0,b),\;\exist x_j’,\;b\oplus f_j(x_j)\oplus f_j(x_j’)=a ∀a∈[0,b),∃xj′,b⊕fj(xj)⊕fj(xj′)=a
- ∀ x j ′ , b ⊕ f j ( x j ) ⊕ f j ( x j ′ ) ≠ b \forall x’_j,\;b\oplus f_j(x_j)\oplus f_j(x_j’)\ne b ∀xj′,b⊕fj(xj)⊕fj(xj′)=b
对于第一点,是极好证明的:发现 f j ( x j ′ ) f_j(x_j’) fj(xj′) 可以取遍 [ 0 , f j ( x j ) − 1 ] [0,f_j(x_j)-1] [0,fj(xj)−1],取最大的 f j ( x j ) f_j(x_j) fj(xj) 即可。
对于第二点,也不难证明:当且仅当 f j ( x j ) = f j ( x j ′ ) f_j(x_j)=f_j(x’_j) fj(xj)=fj(xj′) 时成立,但这违反了 m e x mex mex 的定义。
4.3.例子
我将会在下方给出一些例子,以期更清晰的阐述该定理。
- 石头剪刀布游戏:有一颗石头,拿走者胜利。
毫无疑问, s g ( x ) = x ( x = 0 ∨ x = 1 ) sg(x)=x\;(x=0\vee x=1) sg(x)=x(x=0∨x=1) 。它可以看成特殊版的一堆石子游戏
。 - 一堆石子游戏:有一堆石头,每次拿任意个,拿光者胜利。
这个游戏可以转化成 n n n 个石头剪刀布游戏
吗?——不能,因为不满足 “只影响一个子游戏”。
当然,它的 s g sg sg 函数很好求,是 s g ( x ) = x sg(x)=x sg(x)=x 。 - n i m nim nim 游戏:有 n n n 堆石头,每次在某一堆里拿任意个,拿光者胜利。
这个游戏可以转化成 n n n 个一堆石子游戏
吗?——可以。
所以 n i m nim nim 游戏的 s g sg sg 函数是每一堆石子的数量取异或和。 - 奇怪的 n i m nim nim 游戏:在 n i m nim nim 游戏的基础上,增加船新操作:将一堆石子分成两堆。
对于某一堆来说,将它的分裂视作两个新的奇怪的nim游戏
可以吗?——可以。
注意到,这里的子问题和原问题是一样的。递归型子问题。
5.例题
5.1. Northcott Game \text{Northcott Game} Northcott Game
这道题其实是有 “山无棱,天地连,乃敢与君绝” 的可能性的(说人话:无限进行)。
但是,仍然存在必胜策略。而且,这是一种转化的思想。
点此跳转,看看什么叫做神奇的博弈。
5.2. Turning Turtles \text{Turning Turtles} Turning Turtles
另一种形式的转化。从某种角度上来说,他们只是计算方式相同,本质是不同的。
点此跳转,看看计算方式相同是从何处得出的结论。
5.3. Sprague-Grundy \text{Sprague-Grundy} Sprague-Grundy
传送门 to VJ(也可以直接看下面那句话,是简化后的题意)
在基本 n i m nim nim 游戏的基础上,增加了一种新的操作:将一堆石子分成两堆。
这个可以直接运用 s g sg sg 定理(子游戏与原游戏相同),得到
s g ( x ) = m e x ( S ) ( S = { s g ( 0 ) } ∪ { s g ( i ) , s g ( x − i ) ⊕ s g ( i ) ∣ i ∈ [ 1 , x ) } ) sg(x)=mex(S)\quad(S=\{sg(0)\}\cup\{sg(i),sg(x-i)\oplus sg(i)\;|\;i\in[1,x)\}) sg(x)=mex(S)(S={
sg(0)}∪{
sg(i),sg(x−i)⊕sg(i)∣i∈[1,x)})
那么你可以一开始 O ( A 2 ) \mathcal O(A^2) O(A2) 的递推一下,其中 A A A 是石子数量的最大值。
如果你更狠一点,将 s g sg sg 表打出来,是可以发现规律的!我在代码中直接运用了该规律。
最终,将每一堆石子的 s g sg sg 值异或起来即可。
#include <cstdio> #include <iostream> #include <vector> #include <algorithm> #include <cstring> using namespace std; inline int readint(){
int a = 0; char c = getchar(), f = 1; for(; c<'0' or c>'9'; c=getchar()) if(c == '-') f = -f; for(; '0'<=c and c<='9'; c=getchar()) a = (a<<3)+(a<<1)+(c^48); return a*f; } inline void writeint(long long x){
if(x < 0) putchar('-'), x = -x; if(x > 9) writeint(x/10); putchar((x%10)^48); } # define MB template < class T > MB void getMax(T &a,const T &b){
if(a < b) a = b; } MB void getMin(T &a,const T &b){
if(b < a) a = b; } int main(){
int res = 0; for(int i=1,n=readint(); i<=n; ++i){
int a = readint(); if((a-1)%4 >= 2) a = ((a-1)^1)+1; res ^= a; } puts(res == 0 ? "Bob" : "Alice"); return 0; }
5.4. kiki’s game \text{kiki’s game} kiki’s game
传送门 to VJ:一张 n × m n\times m n×m 的棋盘,有一个在左上角的棋子,每次可以 向右/向下/向右下 移动一步。轮流移动,先移动到右下角的人赢。
甚至不需要 s g sg sg 函数,直接用零和一表示是否先手必胜即可。打表找规律。
当然,你也可以说出其本质:保持坐标为两个奇数即可。你在 x x x 坐标上移动,我也在 x x x 坐标上移动。最终一定是我得到两个奇数的 ( 1 , 1 ) (1,1) (1,1) 咯!
#include <cstdio> #include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; inline int readint(){
int a = 0; char c = getchar(), f = 1; for(; c<'0' or c>'9'; c=getchar()) if(c == '-') f = -f; for(; '0'<=c and c<='9'; c=getchar()) a = (a<<3)+(a<<1)+(c^48); return a*f; } inline void writeint(long long x){
if(x < 0) putchar('-'), x = -x; if(x > 9) writeint(x/10); putchar((x%10)^48); } # define MB template < class T > MB void getMax(T &a,const T &b){
if(a < b) a = b; } MB void getMin(T &a,const T &b){
if(b < a) a = b; } int main(){
int n, m; while(scanf("%d %d",&n,&m) != -1) if(n == 0 and m == 0) break; else if((m&n&1) == 1) // 两个奇数 puts("What a pity!"); else puts("Wonderful!"); return 0; }
5.5. Cutting Game \text{Cutting Game} Cutting Game
一眼望去,是 s g sg sg 函数板题。
再看一次,发现并不简单。因为样例都过不了。
仔细端详,发现确实是 s g sg sg 函数,不过有一点微调。
点此跳转,可以看看怎么处理原问题,使之满足 s g sg sg 定理 “子游戏” 的定义。
5.6. nim-k \text{nim-k} nim-k
还是 n i m \rm nim nim 游戏,但是一次可以操作 k k k 堆石子,怎么做?
事实上已经不靠 s g sg sg 函数了。但是可以讲一讲。答案是,只需要数每堆石子在二进制下,每一位 1 1 1 的个数取模 ( k + 1 ) (k+1) (k+1) 的结果。原因跟这个东西比较像:
一堆石子,每次至少拿 1 1 1 个石子,最多拿 k k k 个石子。
当每一位 1 1 1 的个数都是 ( m + 1 ) (m+1) (m+1) 的倍数时,更改 m m m 个值不能使其仍然保持这一性质。而我们总能将其还原:从高位到低位考虑,设有 k k k 个数已被操作,除去这 k k k 个数以外,这一位上 1 1 1 的个数取模 ( m + 1 ) (m+1) (m+1) 得到 s s s 。显然原本 1 1 1 的个数至少为 s s s 。如果 s ⩽ m − k s\leqslant m-k s⩽m−k,则可以选出 s s s 个 1 1 1 变为 0 0 0 。如果 s ⩾ m − k + 1 s\geqslant m-k+1 s⩾m−k+1 即 k ⩾ m − s + 1 k\geqslant m-s+1 k⩾m−s+1,那么只需要选出 k k k 个数中的 m − s + 1 m-s+1 m−s+1 个取 1 1 1,这样就会让总个数是 ( m + 1 ) (m+1) (m+1) 的倍数。
值得注意的是,它并不是 s g sg sg 函数值。因为它只能从非零变为零,而不能变为比它更小的所有值。一个简单的例子是 { 2 , 1 , 0 , 0 , … , 0 } \{2,1,0,0,\dots,0\} {
2,1,0,0,…,0},有若干个零。 m m m 较大。想要获得一个更小的 s g sg sg 值:第一位有 m m m 个 1 1 1,第二位没有 1 1 1 。这是做不到的……
即使要求子游戏的 s g sg sg 值非零也不行,改成 { 5 , 3 , 1 , 1 , … , 1 } \{5,3,1,1,\dots,1\} {
5,3,1,1,…,1} 本质相同。
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://haidsoft.com/130413.html