知识基础：Nim游戏与SG函数

参考：[学习笔记] （博弈论）Nim游戏和SG函数_A_Comme_Amour的博客-CSDN博客_nim博弈

首先定义P是先手必败，N是先手必胜

有以下性质：

那么终结位置是P

可以转移到P的是N

所有操作都到达N的是P

那么根据以上三点，可以暴力求某一个局面是N还是P。步骤是先使得终结位置是P，然后枚举状态，能到P的是N。然后所有都到达N的P。然后不断迭代。

我做过的一些博弈题就是这个思路。

但是Nim游戏这么做的话时间复杂度很高。

Nim游戏的结论是异或和为0的情况下先手必败。

异或和为0和异或和不为0都可以通过一步操作互相转化。

sg函数：定义mex()表示集合中最小的为出现的非负整数。sg[x] = mex(sg[y] | y是x的后继)

那么终结位置没有后继，sg为0,其他的值可以通过定义算出。

sg = 0是先手必败，否则先手必胜。

多个子游戏的sg值是它们的异或和。

sg的计算：一堆石子，若操作石子数为1~m，那么sg[x] = x % (m + 1)

若为非零任意数，那么sg[x] = x

其他，根据定义暴力计算即可。

例题

比较裸，看作多个子游戏，每个子游戏计算sg值，看异或和即可

阶梯博弈

首先偶数层的石子是没有用的，因为一个人移动了偶数层的石子，另一个人可以模仿把移到奇数层的又移到偶数层。奇数层的操作，石子到了偶数层，相当于扔掉了。所以可以只看奇数层，奇数层的石子组成了一个Nim游戏。对于有必胜策略的那个人，对面移动奇数堆，我就按照Nim游戏移，对面移偶数堆，我就模仿它。

Great Party(Nim拓展+莫队)

在nim游戏的基础上，加了一个可以把剩余石子合并到其他堆的操作

如果是1堆，先手直接拿完，先手必胜

如果是两堆，从简单的开始。1 1，那么每次操作没得选，后手赢。

1 x，x>1  先手可以转化到1 1，先手赢

x x 这时每次操作都不能合并，合并就输了，这时后手可以模仿先手的操作，最后后手拿完，后手赢。

x y ，x!= y 先手可以转化到x x，先手赢

总结，2堆的时候，相同后手赢，不相同先手赢

3堆，发现这时先手可以转化为x x的情况，先手赢

4堆，这时一定不能合并，一合并就变成三堆，对手面对这种情况必赢

所以最后一定是1 1 1 1。那么每个数减去1，就变成了标准的nim游戏了

此时若异或和为0，后手操作完，先手面对1 1 1 1，此时后手赢。反之，异或和不为0，先手1

因此4堆的情况，减去1后，异或和为 0，后手赢，异或和不为0，先手赢。我们可以发现这个结论是包含2堆的情况的。

因此我们可以猜结论，奇数堆是先手，偶数堆，减去1后，异或和不为0是先手，否则后手。

为了简便，我们计算后手赢的情况，也就是长度为偶数且异或和为0

因为异或和不为0不好判断，异或和为0的话转化成前缀也就是前缀异或和相同，这个可以用莫队。

#include 
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
typedef long long LL;
const int N = 1e5 + 10;
struct query
{
    int l, r, id, bl;
}q[N];
int s[N], n, m;
LL ans[N], cur;
unordered_map<int, int> cnt[2];
 
bool cmp(query x, query y)
{
    if(x.bl != y.bl) return x.bl < y.bl;
    if(x.bl % 2 == 1) return x.r < y.r;
    return x.r > y.r;
}
 
void add(int x)
{
    int id = x % 2;
    x = s[x];
    cur += cnt[id][x];
    cnt[id][x]++;
}
 
void erase(int x)
{
    int id = x % 2;
    x = s[x];
    cnt[id][x]--;
    cur -= cnt[id][x];
}
 
int main()
{ 
    scanf("%d%d", &n, &m);
    int block = sqrt(n);
 
    _for(i, 1, n)
    {
        int x; scanf("%d", &x);
        x--;
        s[i] = s[i - 1] ^ x;
    }
    _for(i, 1, m)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        l--;
        q[i] = {l, r, i, l / block};
    }
    sort(q + 1, q + m + 1, cmp);
 
    int l = 1, r = 0;
    _for(i, 1, m)
    {
        int ll = q[i].l, rr = q[i].r;
        while(l < ll) erase(l++);
        while(l > ll) add(--l);
        while(r > rr) erase(r--);
        while(r < rr) add(++r);
 
        LL len = rr - (ll + 1) + 1;
        ans[q[i].id] = len * (len + 1) / 2 - cur;
    }
    _for(i, 1, m) printf("%lld\n", ans[i]);
    
    return 0;
}

Z-Game on grid（dp）

这个不是标准的博弈，但是很像博弈。A可以控制自己的行为，B可以理解为随机走。

从结果逆推，当A操作时，只要有一个操作可以达到即可，B操作时，要全部都达到

有点像暴力算N状态和P状态

#include 
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
const int N = 500 + 10;
int dp[N][N][3], n, m;   //0 A 1 D 2 B
char s[N][N];
 
int main()
{ 
    int T; scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        _for(i, 1, n) scanf("%s", s[i]);
        _for(i, 1, n + 1)
            _for(j, 1, m + 1)
                rep(k, 0, 3)
                    dp[i][j][k] = 0;
        
        for(int i = n; i >= 1; i--)
            for(int j = m; j >= 1; j--)
            {
                if(s[i][j] == 'A') dp[i][j][0] = 1;
                else if(s[i][j] == 'B') dp[i][j][2] = 1;
                else if(i == n && j == m) dp[i][j][1] = 1;
                else
                {
                    rep(k, 0, 3)
                    {
                        if((i + j) % 2 == 0) dp[i][j][k] = (dp[i + 1][j][k] || dp[i][j + 1][k]);
                        else dp[i][j][k] = ((i + 1 > n || dp[i + 1][j][k]) && (j + 1 > m || dp[i][j + 1][k]));
                    }
                }
            }
        rep(k, 0, 3) printf(dp[1][1][k] ? "yes " : "no ");
        puts("");
    }
   
    return 0;
}

Split Game（暴力计算SG函数）

这题就是暴力计算SG函数

先把边界条件，sg=0先手必败初始化后

然后遍历每一个状态，对于每一个状态枚举它的所有后继，计算后继的sg值

这道题的操作是分解成两个子游戏，这时的sg值是它们的异或。

#include 
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
const int N = 160;
int sg[N][N], a[N << 1];
 
int check(int i, int j)
{
    return i == 1 && j == 1;
}
 
int main()
{   
    memset(sg, -1, sizeof sg);
    sg[1][2] = sg[2][1] = 0;
    sg[1][3] = sg[3][1] = 0;
    _for(i, 1, 150)
        _for(j, 1, 150)
        {
            if(i == 1 && j == 1 || !sg[i][j]) continue;
            memset(a, 0, sizeof a);
            _for(k, 1, i - 1)
            {
                if(check(k, j) || check(i - k, j)) continue;
                a[sg[k][j] ^ sg[i - k][j]] = 1;
            }
            _for(k, 1, j - 1)
            {
                if(check(i, k) || check(i, j - k)) continue;
                a[sg[i][k] ^ sg[i][j - k]] = 1;
            }
 
            rep(k, 0, N << 1)
                if(!a[k])
                {
                    sg[i][j] = k;
                    break;
                }
        }
    
    int n, m;
    while(~scanf("%d%d", &n, &m))
        puts(sg[n][m] ? "Alice" : "Bob");
 
	return 0;
}