博弈论（巴什、nim、......SG打表）

【算法讲解095【必备】博弈类问题必备内容详解-上】https://www.bilibili.com/video/BV1T5411i7Gg?vd_source=67186f29c3efb728bcff34035cf5aba2

巴什博奕

1.

每个人可以拿1~m个石子。拿走最后一颗的人赢。

这个问题与 m+1，有关。不论先手拿多少，后手总有办法使他俩拿的总和为 m+1的倍数。所以只需要判断初始 n 是不是 m 的倍数，是 的话，后手赢，反之，先手赢。

---

2.

每次可以拿 $p^k$ , p 为素数 ，k 为自然数

判断初始 n 是不是 6 的倍数，是 的话，后手赢，反之，先手赢。

因为可以拿（1，2，3，4，5），而 6 的倍数 一定拿不了。首先 6 不是质数，而它的两个因数 2，3也不能组成 6 的倍数。

---

L.下棋（博弈）

【算法讲解095【必备】博弈类问题必备内容详解-上】https://www.bilibili.com/video/BV1T5411i7Gg?vd_source=67186f29c3efb728bcff34035cf5aba2

巴什博奕

1.

每个人可以拿1~m个石子。拿走最后一颗的人赢。

这个问题与 m+1，有关。不论先手拿多少，后手总有办法使他俩拿的总和为 m+1的倍数。所以只需要判断初始 n 是不是 m 的倍数，是 的话，后手赢，反之，先手赢。

---

2.

每次可以拿 $p^k$ , p 为素数 ，k 为自然数

判断初始 n 是不是 6 的倍数，是 的话，后手赢，反之，先手赢。

因为可以拿（1，2，3，4，5），而 6 的倍数 一定拿不了。首先 6 不是质数，而它的两个因数 2，3也不能组成 6 的倍数。

---

L.下棋（博弈）

20250507ICPC训练赛 - Virtual Judge

对于奇数，显而易见 答案是2.

因为每次拿的数字x，它的二进制不能包含0，所以x 一定是奇数。对于一个奇数，需要拿奇数次奇数，所以最终先手必赢。

想到这，就应该类比！！!

可以从二进制不能出现0，想到 每次拿的数字x的k进制末尾数字不能是0（因为0不是任何数的因子），只看末尾就可以了。

我们每次只拿k进制下的个位数，这样一定可以拿。（5进制下，可以拿1 ~ 4 。k进制下，可以拿1~K-1）

现在有 n 个棋子， n 的k 进制末尾数字是0。

下一个人不管拿多少，他拿的数字x在k进制下末尾数字肯定不是0。这样 n-x ，此时剩余的棋子数量在k 进制下末尾数字一定不为0。

而最终需要变成 0。

例如n= 6，在2进制下为110 ，x=1 或者 3

n-x =5 或者 3 ， 2进制下末尾数字一定不为0

下下一个人，只需要拿剩余的棋子数量 在k 进制下的末尾数字（一定可以拿），此时就可以保证它拿完之后，棋子数量在k 进制下末尾数字一定为 0。

---

所以，我们只需要保证 n 在k 进制下 末尾数字不为零，此时先手去拿，使其变成0，那么最终一定是先手赢。

而只有 k 不是 n 的因子，就可以满足。

Nim博弈

n堆石子，拿走任意数量，最后一个拿的获胜。

n堆全为0的时候 异或=0。当异或为0，另一个人不论拿走多少，异或绝对不等于0.当异或不等于 0 ，总有办法，拿走一个使异或等于0.

初始异或不为0，先手赢。为0.后手赢

反Nim博弈 ：谁最后拿，谁输。

特判全是1的情况

判断初始异或是否等于0，

求先手有几种选择

只需满足sum^a[i]<=a[i]

循环n次不断累加。

斐波那契博弈

1. 单堆石子版本
   • 初始石子数为 n ，两人轮流取石子。
   • 规则
     1. 先手第一次至少取1颗，但不能全部取完 。
     2. 后续每次取的石子数需满足：1≤当前取数≤ 2×对手上次取数。
   • 胜利条件：取走最后一颗石子者获胜。
2. 两堆石子版本（与威佐夫博弈的关联）
   • 若涉及两堆石子（如威佐夫博弈），当两堆石子数分别为斐波那契数列中的相邻项时,后手有必胜策略。

威佐夫博弈（Wythoff Game）

有两堆石子，数量任意，可以不同，游戏开始由两个人轮流取石子
游戏规定，每次有两种不同的取法
1）在任意的一堆中取走任意多的石子
2）可以在两堆中同时取走相同数量的石子
最后把石子全部取完者为胜者
现在给出初始的两堆石子的数目，返回先手能不能获胜
测试链接：https://www.luoqu.com.cn/problem/P2252

小 != (int)（大 - 小）* 黄金分割比例，先手赢
小 == (int)（大 - 小）* 黄金分割比例，后手赢

• 黄金分割比例φ的整数部分，其中φ = (1 + √5)/2 ≈ 1.618

SG打表

SG函数的基本定义

SG函数（Sprague-Grundy Function）是博弈论中解决公平组合游戏（Impartial Combinatorial Games，简称ICG）的重要工具。

• 定义：
  SG函数的参数是游戏的状态，返回值是一个非负整数。
  公式：

  $sg(x)=mex({sg(y)∣y是x的后继状态}) $

  其中，mex（Minimum EXcludant）表示从集合中排除的最小非负整数。例如，mex{0, 1, 2} = 3。

• 后继状态：
  后继状态是指从当前状态通过合法操作能够到达的所有状态。

• 性质1：如果 sg(x)=0，则当前状态 x 是必败状态。

• 性质2：如果 sg(x)≠0，则当前状态 x 是必胜状态。

---

在多个独立游戏的组合（即组合游戏）中，整体游戏的胜负性可以通过各子游戏的SG函数值的异或和来判断：

• 定理

  若游戏由多个独立子游戏组成，则整体游戏的SG函数值为各子游戏SG函数值的异或和：

  sg(x1,x2,…,xn)=sg(x1)⊕sg(x2)⊕⋯⊕sg(xn)

• 胜负判断

  • 如果异或和为0，当前玩家处于必败状态（对手有必胜策略）。
  • 如果异或和不为0，当前玩家处于必胜状态（可通过操作使异或和变为0）。

例题：C. Battle

Problem - C - Codeforces

易知，当p=3：

sg(1) = 1 , sg(2) = 0 , sg(3)= 1

sg打表

int f[300],p=3;
int sg(int x) {if(f[x]!=-1) {return f[x];}set<int>s;for(int i=0; i<10; i++) {if(x>=pow(p,i)) {s.insert(sg(x-pow(p,i)));}}for(int i=0;; i++) {if(!s.count(i)) {return f[x]=i;}}}
void solve()
{fir(i,1,200)f[i]=-1;fir(i,1,100)cout<<sg(i)<<" ";
}

可以发现规律，奇数为：10101010

偶数也有规律

标程

int a[N];
void solve()
{int n,p,ans=0;cin>>n>>p;fir(i,1,n)cin>>a[i];fir(i,1,n){if(p&1)ans^=(a[i]%2);else{if(a[i]%(p+1)==0)ans^=0;else if(a[i]%(p+1)==p)ans^=2;elseans^=(a[i]%(p+1)%2);}}if(ans!=0)cout<<"GOOD"<<'\n';else cout<<"BAD"<<'\n';
}

20250507ICPC训练赛 - Virtual Judge

对于奇数，显而易见 答案是2.

因为每次拿的数字x，它的二进制不能包含0，所以x 一定是奇数。对于一个奇数，需要拿奇数次奇数，所以最终先手必赢。

想到这，就应该类比！！!

可以从二进制不能出现0，想到 每次拿的数字x的k进制末尾数字不能是0（因为0不是任何数的因子），只看末尾就可以了。

我们每次只拿k进制下的个位数，这样一定可以拿。（5进制下，可以拿1 ~ 4 。k进制下，可以拿1~K-1）

现在有 n 个棋子， n 的k 进制末尾数字是0。

下一个人不管拿多少，他拿的数字x在k进制下末尾数字肯定不是0。这样 n-x ，此时剩余的棋子数量在k 进制下末尾数字一定不为0。

而最终需要变成 0。

例如n= 6，在2进制下为110 ，x=1 或者 3

n-x =5 或者 3 ， 2进制下末尾数字一定不为0

下下一个人，只需要拿剩余的棋子数量 在k 进制下的末尾数字（一定可以拿），此时就可以保证它拿完之后，棋子数量在k 进制下末尾数字一定为 0。

---

所以，我们只需要保证 n 在k 进制下 末尾数字不为零，此时先手去拿，使其变成0，那么最终一定是先手赢。

而只有 k 不是 n 的因子，就可以满足。

Nim博弈

n堆石子，拿走任意数量，最后一个拿的获胜。

n堆全为0的时候 异或=0。当异或为0，另一个人不论拿走多少，异或绝对不等于0.当异或不等于 0 ，总有办法，拿走一个使异或等于0.

初始异或不为0，先手赢。为0.后手赢

反Nim博弈 ：谁最后拿，谁输。

特判全是1的情况

判断初始异或是否等于0，

求先手有几种选择

只需满足sum^a[i]<=a[i]

循环n次不断累加。

斐波那契博弈

1. 单堆石子版本
   • 初始石子数为 n ，两人轮流取石子。
   • 规则
     1. 先手第一次至少取1颗，但不能全部取完 。
     2. 后续每次取的石子数需满足：1≤当前取数≤ 2×对手上次取数。
   • 胜利条件：取走最后一颗石子者获胜。
2. 两堆石子版本（与威佐夫博弈的关联）
   • 若涉及两堆石子（如威佐夫博弈），当两堆石子数分别为斐波那契数列中的相邻项时,后手有必胜策略。

威佐夫博弈（Wythoff Game）

有两堆石子，数量任意，可以不同，游戏开始由两个人轮流取石子
游戏规定，每次有两种不同的取法
1）在任意的一堆中取走任意多的石子
2）可以在两堆中同时取走相同数量的石子
最后把石子全部取完者为胜者
现在给出初始的两堆石子的数目，返回先手能不能获胜
测试链接：https://www.luoqu.com.cn/problem/P2252

小 != (int)（大 - 小）* 黄金分割比例，先手赢
小 == (int)（大 - 小）* 黄金分割比例，后手赢

• 黄金分割比例φ的整数部分，其中φ = (1 + √5)/2 ≈ 1.618

SG打表

SG函数的基本定义

SG函数（Sprague-Grundy Function）是博弈论中解决公平组合游戏（Impartial Combinatorial Games，简称ICG）的重要工具。

• 定义：
  SG函数的参数是游戏的状态，返回值是一个非负整数。
  公式：

  $sg(x)=mex({sg(y)∣y是x的后继状态}) $

  其中，mex（Minimum EXcludant）表示从集合中排除的最小非负整数。例如，mex{0, 1, 2} = 3。

• 后继状态：
  后继状态是指从当前状态通过合法操作能够到达的所有状态。

• 性质1：如果 sg(x)=0，则当前状态 x 是必败状态。

• 性质2：如果 sg(x)≠0，则当前状态 x 是必胜状态。

---

在多个独立游戏的组合（即组合游戏）中，整体游戏的胜负性可以通过各子游戏的SG函数值的异或和来判断：

• 定理

  若游戏由多个独立子游戏组成，则整体游戏的SG函数值为各子游戏SG函数值的异或和：

  sg(x1,x2,…,xn)=sg(x1)⊕sg(x2)⊕⋯⊕sg(xn)

• 胜负判断

  • 如果异或和为0，当前玩家处于必败状态（对手有必胜策略）。
  • 如果异或和不为0，当前玩家处于必胜状态（可通过操作使异或和变为0）。

例题：C. Battle

Problem - C - Codeforces

易知，当p=3：

sg(1) = 1 , sg(2) = 0 , sg(3)= 1

sg打表

int f[300],p=3;
int sg(int x) {if(f[x]!=-1) {return f[x];}set<int>s;for(int i=0; i<10; i++) {if(x>=pow(p,i)) {s.insert(sg(x-pow(p,i)));}}for(int i=0;; i++) {if(!s.count(i)) {return f[x]=i;}}}
void solve()
{fir(i,1,200)f[i]=-1;fir(i,1,100)cout<<sg(i)<<" ";
}

可以发现规律，奇数为：10101010

偶数也有规律

标程

int a[N];
void solve()
{int n,p,ans=0;cin>>n>>p;fir(i,1,n)cin>>a[i];fir(i,1,n){if(p&1)ans^=(a[i]%2);else{if(a[i]%(p+1)==0)ans^=0;else if(a[i]%(p+1)==p)ans^=2;elseans^=(a[i]%(p+1)%2);}}if(ans!=0)cout<<"GOOD"<<'\n';else cout<<"BAD"<<'\n';
}