博弈论之SG函数

alt

SG函数适用于解决博弈论中公平组合游戏（英文缩写ICG）问题的一种方法。

博弈论是二人（或多人）在平等的对局中各自利用对方的策略变换自己的对抗策略，达到取胜的目的。

公平组合游戏简介

公平组合游戏是一类双方轮流行动、无随机性、无隐藏信息、所有可行动作完全公开的数学博弈模型。

公平组合游戏一般满足以下几种条件：

$1.$ 一个对局中的两个玩家轮流行动，并且两个玩家遵守游戏规则。

$2.$ 对于游戏本身的规则，不包含运气成分

$3.$ 没有隐藏信息，局内的信息都可以被双方知道

$4.$ 游戏在若干轮后必然结束，无法行动者失败。

对于ICG问题，最经典的就是Nim游戏了

Nim游戏规则：地上有 n 堆石子，每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。

假设我们先选取一堆石子，这堆石子有m块，假设我们作为局中一人要操作这个石子，则我们有m种选法，也就是说这堆石子可能会变成 $m-1,m-2,m-3,...,1,0$ 块。我们定义一个函数 $sg(x)$ ,对于公平组合游戏来说 $sg(x)=mex({sg(y)|x\rightarrow y})$ ,这个公式意味着从 $x$ 的状态转移到 $y$ 状态，也就是找到 $x$ 可转移集合中没有出现的最小非负整数。其中 $\mathrm{mex}(S) = \min \{ x \in \mathbb{N} \mid x \notin S \}$ 。我们一般把 $sg(x)=0$ 称为必输态。

回到我们这一堆 $m$ 块石子中，故我们可以知道该堆石子的 $sg$ 值为m.这有点像动态规划中的DP状态转移，对于 $dp[m]$ 的这个状态，我们可以自由转移到 $dp[m-1],dp[m-2],...,dp[1],dp[0]$ 这种状态。

但是对于整局来说我们对单堆石子操作很难进行判断谁胜谁负。这就要用到我们的 $SG$ 定理了。

Sprague–Grundy 定理

定义若干个 $ICG$ 的组合构成的一个游戏：两个玩家轮流对这个游戏中的任意 $ICG$ 进行操作一次，当所有的子游戏无法操作时，游戏结束。计两个 $ICG$ 游戏的状态分别为 $x,y$ ，则这两个 $ICG$ 游戏和状态就是 $x+y$ 。对于 $sg$ 函数有：

$sg(x+y)=sg(x) \oplus sg(y)$

其中 $\oplus$ 代表异或操作。

这边不对Sprague–Grundy 定理做数学证明。

我们可以将 $SG$ 定理推广值多元有：

$sg(x_1+x_2+...+x_n)=sg(x_1)\oplus sg(x_2)\oplus ...\oplus sg(x_n)$

这样我们就可以将单一游戏的情况推广到全局游戏。若最终 $sg(x_1+x_2+...+x_n)=0$ 时，就可以判断谁必败，谁必胜。

例题

这样我们来看25校赛的这道题：

题目描述

P5R天下第一！

雨宫莲表面上是一名普普通通的高中生，其实是闻名东京的怪盗团团长Joker，通过进入心灵宫殿，怪盗团专门偷盗大人们扭曲的心灵，使他们“悔改”。

为了寻找并逮捕怪盗团成员，东京地方检察厅特别搜查部检察官新岛冴决定带领警察搜查秀尽学园，怪盗团陷入了绝境。危急关头，Joker决定潜入新岛冴的心灵宫殿，通过让她悔改的方式，使警察退出搜查，保证怪盗团的安全。

Joker一行人来到新岛冴心灵宫殿的最深处，发现新岛冴已经等候多时了。想要打败新岛冴，就必须在她设计的游戏中获胜，游戏的规则如下：

首先，给定一个数字F，然后场上出现N个牌堆，Joker和新岛冴轮流操作。每次操作时，操作者先选定一个不小于2的正整数M（M小于等于选中的牌堆的牌数），然后将任意一堆数量不小于F的牌堆分成M堆，并且满足这M堆牌堆中的扑克牌数最多的牌堆至多比扑克牌数最少的牌堆多1（即尽可能平均分配，可以想到分配方法是固定的）。也就是说，在完成一次操作后，场上增加M−1个牌堆，然后由下一个玩家操作。当一个玩家不能操作时，也就是每一个牌堆的数量均小于F时，该名玩家输掉游戏。

新岛冴十分自信Joker看不出这个游戏的必胜策略，所以大方的让Joker选择先手还是后手。假设双方都采用最优策略，你的任务是帮助Joker找到这个游戏是先手必胜还是后手必胜。

打败新岛冴，偷走她的心吧！

输入格式

第一行给定两个正整数N（1≤N≤105)和F(1≤F≤103)，表示牌堆的数量和给定的数字。

第二行给定N个正整数ai(1≤ai≤103)，表示牌堆中扑克牌的数量。

输出格式

输出一行，如果先手必胜，输出”First”；否则，输出”Second”。

样例1

输入

1 3
5

Copy

输出

First

Copy

样例2

输入

5 3
3 3 2 2 1

Copy

输出

Second

题意浓缩：

场上有 $N$ 个牌堆，给你一个数字 $F$ , 牌堆中牌数 $a_i\ge max(2,F)$ 的都必须拆分成 $M-1$ 堆，其中 $2\le M \le a_i-1$ ，堆中的扑克牌数最多的牌堆至多比扑克牌数最少的牌堆多1。当一个玩家不能操作时，也就是每一个牌堆的数量均小于 $F$ 时，该名玩家输掉游戏。让我们求先手稳赢还是后手稳赢。

思考过程：

看着这个题目，显然满足公平组合游戏的几个条件，我们就要利用 $SG$ 函数对每一堆 $ICG$ 组合游戏然后求每一个 $ICG$ 的 $sg(a_i)$ 。然后判断 $!sg(sum(a))$ 即可。然后考虑如何求 $sg(a_i)$ ,由于我们要求的是 $mex({sg(y)|a_i\rightarrow y})$ 。我们可以枚举牌堆中牌的数量 $i$ 从 $1$ 到 $1000$ ,堆数 $j$ 从 $2$ 枚举到 $a_i-1$ 。我们设置一个 $pd$ 数组来检测 $mex$ 值。设置一个 $temp$ 值暂存 $sg(i)$ 可以到达的值。

譬如说牌数为5的牌堆可以分成1 1 1 1 1，2 1 1 1 ，2 2 1这三种情况。

此时，堆中最小值是 $i/j$ ,最大值的数量为 $i\% j$ ,如果 $i\% j\&1$ 则当前状态可以转移到 $i/j+1$ 的状态， $temp$ ^ $=sg(i/j+1)$ ,如果 $(j-i\%j)\&1$ ,则 $temp$ ^ $sg(i/j)$ ;

我们就可以预处理出从 $1-1000$ 的 $sg(a_i)$ 的值，最后再异或一下，判断 $!sg(sum(a))$

是否为True,是则输出Second，否则输出First。

AC code:

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
typedef long long ll;
#define yes do{cout<<"YES"<<endl;return;}while(0);
#define no do{cout<<"NO"<<endl;return;}while(0);
#define pb push_back
#define PII pair<int,int>
#define all(x) x.begin(),x.end()
//#define F first
//#define S second
#define int long long
#define ld long double
const int N=2e5+10;
const int M=2e3+10;
int mod=1e9+7;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
const ll inf=0x3f3f3f3f3f3f3f3fLL;
bool vis[N];
int n,m;
float f;
long long binpow(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}
void solve(){
    cin>>n>>m;
    vector<int> v(n+1);
    vector<int> sg(1005);
    for(int i=1;i<=n;i++){
        cin>>v[i];
    }
    for(int i=1;i<=1000;i++){
        if(i<m){
            sg[i]=0;//小于F不能分解
            continue;
        }
        vector<int> pd(2005);
        for(int j=2;j<=i;j++){
            int mn=i/j;//最小值
            int yu=i%j;//最大值个数
            int temp=0;
            if((j-yu)&1) temp^=sg[mn];
            if(yu&1) temp^=sg[mn+1];
            pd[x]=1;
        }
        int g=0;
        while(pd[g])++g;//寻找mex中
        sg[i]=g;
    }
    int x=0;
    for(int i=1;i<=n;i++){
        x^=sg[v[i]];
    }
    if(x!=0){
        cout<<"First"<<endl;
    }else{
        cout<<"Second"<<endl;
    }
}
signed main(){
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}