博弈论

博弈论入门及其经典模型，以及关于 SG 函数的理解。

0.有向图游戏

给定一个有 $n$ 个点的有向无环图，图中有 $m$ 个的棋子放在图上其中 $m$ 个点上。两名玩家交替地把其中一枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。判断先手必胜。

我们先考虑 $m=1$ 的情况。

首先通过推理,我们有下面三条定理：

​ 定理 1：没有后继状态的状态是必败状态。

​ 定理 2：一个状态是必胜状态当且仅当存在至少一个必败状态为它的后继状态。

​ 定理 3：一个状态是必败状态当且仅当它的所有后继状态均为必胜状态。

那么我们很容易用 DP 简单求解。那么对于更一般的情况呢？我们容易发现每个棋子其实是相互独立的。

1.SG 函数

SG 函数是用于解决博弈论中公平组合游戏（Impartial Combinatorial Games，ICG）问题的一种方法。此处我们主要讨论公平组合游戏。

1.1 定义

设一个状态 $X$，设其后继状态的 SG 函数为 $A={SG(Y_1),SG(Y_2),\dots,SG(Y_n)}$，定义：

$$SG(A)=\left\{ \begin{align} &0 & {A = \emptyset}\\ &\text{mex}(A) & {A\ne \emptyset} \end{align} \right. \notag$$

其中 $\text{mex}(A)$ 表示未在 $A$ 中出现的最小非负整数。

1.2 性质

即 SG 定理。设两个互相独立的状态 $X,Y$，状态 $X+Y$ 表示两个状态的组合，有：

$$SG(X+Y)=SG(X)\oplus SG(Y)$$

进一步得到：

$$SG(X_1+X_2+\dots +X_n)=SG(X_1)\oplus SG(X_2)\oplus \dots \oplus SG(X_n)$$

这是我们用 SG 函数求解问题的关键（一定要分清楚后继状态和状态的组合）。

实际上 SG 函数是为了解决 有向图游戏 给出的一种方法。而绝大多数公平组合游戏都可以转化为 有向图游戏。

2.基本模型

关键在于如何设计 SG 函数，即如何转化为有向图游戏。

2.1 Nim 游戏

2.2 阶梯模型

有 $n$ 层阶梯，编号 $1,\cdots,n$，每层阶梯上有一些石子。

两个玩家轮流操作，每次操作可以将第 $i$ 层上至少一个石子放在第 $i-1$ 层阶梯上。无法操作者判负。

首先发现偶数层相当于“垃圾桶”，因为如果有一方尝试将偶数层上的石子移向奇数层，那么另一方可以相应的将这些石子移到偶数层，而过程中奇偶行没有发生变化。再考虑奇数层，容易发现可以将任意多的石子扔到“垃圾桶”，完全等价于 Nim 游戏。于是只需要计算奇数层石子个数的异或和即可。

2.2.1 例题

1.P5363 [SDOI2019] 移动金币

考虑转化模型，直接让金币代表阶梯，金币之间的格子代表石子，那么我们转化成与上述模型一样的情况。

于是给定 $n-m$ 个石子，要求分为 $m+1$ 堆，满足偶数堆的石子数异或起来为 $0$ 的方案数。

考虑朴素 DP，设计状态 $f(i,j,k)$ 表示考虑前 $i$ 堆共用了 $j$ 个石子，异或和为 $k$ 的方案数。这样直接做是 $\mathcal O(n^2m)$ 的。

我们显然可以对于异或和的每一位单独考虑。设计 $f(t,i)$ 表示考虑到第 $t$ 位的状态为 $0/1$（前 $t-1$ 位已经全部为 $0$），共用了 $i$ 个石子。于是直接钦定偶数个 $1$ 即可。这样时间复杂度为 $\mathcal O(nm\log n)$，能够通过此题。

Code

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1.5e5+10,M=50,K=18,mod=1e9+9;
template<class T>
inline void read(T &x)
{
    x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m,bit;
int fac[N],ifac[N];
int f[K+5][N];
int all;
inline int adj(int x){return x>=mod?x-mod:x;}
inline void upd(int &x,int y){x+=y,x=x>=mod?x-mod:x;}
inline int qpow(int x,int k=mod-2)
{
    int ans=1;
    while(k)
    {
        if(k&1)ans=1ll*ans*x%mod;
        x=1ll*x*x%mod;
        k>>=1;
    }
    return ans;
}
inline void init(int n)
{
    fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
    ifac[n]=qpow(fac[n]);
    for(int i=n;i;i--)ifac[i-1]=1ll*ifac[i]*i%mod;
}
inline int C(int n,int m)
{
    if(m>n)return 0;
    return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main()
{
    read(n,m);
    init(n);
    all=C(n,m);
    n-=m,m++;
    while(1<<bit<n)bit++;
    f[0][0]=1;
    for(int t=0;t<bit;t++)
    {
        for(int i=0;i<=(m>>1);i+=2)
        {
            int now=i<<t;
            for(int j=0;j<=n-now;j+=2)
                upd(f[t+1][j+now],1ll*f[t][j]*C(m>>1,i)%mod);
        }
    }
    int ans=0;
    for(int i=0;i<=n;i+=2)upd(ans,1ll*f[bit][i]*C(n-i+(m-1>>1),m-1>>1)%mod);
    printf("%d\n",adj(all+mod-ans));
    return 0;
}

考虑继续优化，我们发现答案只关心 $i=n$ 状态。注意对于第 $t$ 位，我们最多放 $m$ 个 $1$，总共是 $m\cdot 2^t$ 个。在依次考虑 $t$ 的过程中，用记录进位了 $i$ 个 $2^t$，$i$ 的范围是 $[1,m]$。用 $g(i)$ 表示将 $i$ 个石子分给 $m$ 堆，每堆之多被分到一个，满足偶数堆总共被分到偶数个，这个我们容易预处理。我们用 $g(i)$ 作为转移的系数。设 $bit$ 为 $n$ 二进制下第 $t$ 位的值。容易得到：

$$f(t,i)\times g(j)\to f(t+1,\frac{i+j-bit}{2})$$

其中需要满足： $i+j\equiv bit\pmod 2$。

这样就可以做到 $\mathcal O(m^2\log n)$。更进一步的，我们发现 $f(t,i),g(i)$ 的转移都具有卷积形式。于是我们可以用 多项式乘法 优化（不过模数是 $1e9+9$，需要用到任意模数多项式乘法）。这样可以做到 $\mathcal O(m\log m\log n)$。

下面是 $\mathcal O(m^2\log n)$ 的做法。

Code

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1.5e5+10,M=50+10,K=18,mod=1e9+9;
template<class T>
inline void read(T &x)
{
    x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m,bit;
int fac[M],ifac[M];
int f[K+5][M],g[M];
inline int adj(int x){return x>=mod?x-mod:x;}
inline void upd(int &x,int y){x+=y,x=x>=mod?x-mod:x;}
inline int qpow(int x,int k=mod-2)
{
    int ans=1;
    while(k)
    {
        if(k&1)ans=1ll*ans*x%mod;
        x=1ll*x*x%mod;
        k>>=1;
    }
    return ans;
}
inline int C(int n,int m)
{
    if(m>n)return 0;
    return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
inline void init(int n)
{
    fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
    ifac[n]=qpow(fac[n]);
    for(int i=n;i;i--)ifac[i-1]=1ll*ifac[i]*i%mod;
    int p=n>>1,q=n+1>>1;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=p;j+=2)
            upd(g[i],1ll*C(p,j)*C(q,i-j)%mod);
}

int main()
{
    read(n,m);
    n-=m,m++;
    init(m);
    while(1<<bit<n)bit++;
    f[0][0]=1;
    for(int t=0;t<=bit;t++)
    {
        int now=n>>t&1;
        for(int i=0;i<=m;i++)
            for(int j=0;j<=m;j++)
            {
                if((i+j&1)!=now)continue;
                int k=(i+j)>>1;
                upd(f[t+1][k],1ll*f[t][i]*g[j]%mod);
            }
    }
    m--,n+=m;
    int all=ifac[m];
    for(int i=0;i<m;i++)all=1ll*all*(n-i)%mod;
    printf("%d\n",adj(all+mod-f[bit+1][0]));
    return 0;
}

2.P2575 高手过招

还是转化模型，与上面非常相似。

2.3 翻硬币模型

$n$ 个硬币排成一行，每次可以翻连续的若干个，要求最右边的必须从反到正，无法操作的人判负。

结论：整个游戏的 SG 函数相当于所有反面硬币的 SG 函数的异或和，而位于 $x$ 位置的 SG 函数有规律：$SG(x)=\text{lowbit}(x)$。

CF494E Sharti

利用上面的模型，我们得到几点：1.每个格子可以作为一个子游戏；2.整个游戏的 SG 函数的值为所有白色棋子的 SG 函数值；3.对于位置 $(x,y)$ 的白色棋子，$SG(x,y)=\min(\text{lowbit}(x),\text{lowbit}(y),\text{greatbit}(k))$。

有了这三点我们相对好做了。因为 $SG(x,y)$ 一定为 $2$ 的次幂。我们对于每个 $c$，求 $SG(x,y)=2^c$ 位置的奇偶性即可。为了更方便一点，我们容斥以下，依次求出 $SG(x,y)\ge 2^c$ 的个数，用 $SG(x,y)\ge 2^{c-1}$ 减去即可得到 $SG(x,y)=2^c$ 的个数。于是我们变换坐标 $(x,y)\to (\lfloor \frac{x}{2^c}\rfloor,\lfloor \frac{y}{2^c}\rfloor)$，扫描线求解即可。总的时间复杂度为 $\mathcal O(n\log^2 n)$。

2.4 斐波那契NIM游戏

有 $n$ 枚石子。两位玩家定了如下规则进行游戏： 第一次取石子时可以取走任意多个； 接下来，每次至少要取走一个石子，最多取走上一次取的数量的 $2$ 倍。当然，玩家取走的数量必须不大于目前场上剩余的石子数量。 无法操作的人判负。

结论：先将 $n$ 写成齐肯多夫表示，即用斐波那契数表示且没有相邻两个都是 1 ，则先手每次取最低位的 1 即可获胜。

例题：P6791 [SNOI2020] 取石子。

2.5 其它经典博弈

2.5.1 树（图）上删边博弈

在一棵树/图上钦定一个根，每次可以删去一条边，若删边后某部分与根不连通则一并删去，无法操作的人判负。

考虑已知儿子节点的 $SG(y_i)$ 的值，求根节点的 $SG(x)$。显然割掉 $(x,y_i)$ 并不会对其它 $y_i$ 产生影响。我们显然可以将每棵子树 $y_i$ 再加上节点 $x$ 看成若干个独立的状态，设这样的状态为 $z_i$，下面直接用 $SG(x)$ 表示子树 $x$ 的 SG 函数值。

先考虑单个 $z_i$：我们可以选择割掉 $(x,y_i)$，后继状态 SG 函数值为 0，若割掉子树 $y_i$ 中若干边之后，再割掉 $(x,y_i)$，那么 SG 函数的集合为 ${1,2,\cdots,SG(y_i)-1,SG(y_i)}$。最终对上述集合中值取 $\text{mex}$，得到 $SG(z_i)=SG(y_i)+1$。所以 $SG(x)=\operatorname{mex}_{y_i} SG(y_i)+1$。最终判断 $SG(x)$ 是否为 $0$ 即可。

图的情况：把所有偶环缩成点，所有奇环缩成一个点和一条边（只连他自己那个点），然后当成树来做。

例题：[AGC017D] Game on Tree。

2.5.2 威佐夫博弈

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。

结论：当且仅当两堆石子的数量构成黄金比的时候后手获胜。

2.5.3 二分图博弈

在二分图上，两人轮流指定下一步去哪个点，不经过重复的点，无法指定的人输，问谁赢？

结论：当一个点在所有最大匹配的方案中（少了这个点无法最大匹配），那么先手必胜。

证明：后手不可能选到非匹配点，如果后手选到一个非匹配点，设路径为 $S_1\to S_n$，那么把现在的匹配换成 $S_2\to S_n$，匹配数不变但不包含 $S_1$，与最大匹配一定包含 $S_1$ 矛盾。

扩展到无向图的情况：不指定起点，则有完美匹配后手必胜；否则结论与上面一样。

P5363 [SDOI2019] 移动金币

P2575 高手过招

P4077 [SDOI2016] 硬币游戏

P4576 [CQOI2013] 棋盘游戏

P4363 [九省联考 2018] 一双木棋 chess

[ARC137C] Distinct Numbers

[AGC043C] Giant Graph