博弈论

一、
NIM博弈：有n堆石子，从任意一堆石子中可以取任意颗石子，不能不取，最后谁取的时候没有石子了，谁就输了
结论：当$a1\oplus$$a2\oplus$$a3\oplus$$\dots$$=0$ 时是先手必败态，其余先手必胜
证明：我们证明可以分以下三步（注意当移动的时候两者先后手发生了变化）
1：将全为0的状态判为先手必败
2：判为先手必胜的状态一定可以移动到一个先手必败的状态
3：判为先手必败的状态不能移动到先手必败的状态
第一个命题显然：0异或n个0是0
第二个命题 ：先手必胜是a1^ a2 ^ a3 ^ …… an>0的状态，我们假设a1 ^ a2 ^ ……an=k，那么我们可以从中发现的是在所有的数一定有至少有一个数在k的最高位上的数字是1，那么这时ai ^ k< ai是一定成立的，我们将ai=ai ^ k。那么原式=k ^ k=0。
第三个命题：假设先手必败，那么a1 ^ a2 ^ …… ^ an=0，我们可以发现无论我们怎么改，一定会对各位数字上奇偶的数量发生变化，所以改变数字后，结果一定是不为0的。

这个其实也不叫证明，知识对于公式的验证，验证他是正确的。

二、
巴什博弈：有一堆物品共n个，两个人轮流取物，一次最少取1个，最多取m个，取走最后一个的胜。
分情况讨论：
当n<=m时，显然是先手必胜
当n=m+1时，显然是后手必胜
当n%(m+1)!=0时，先手可以取出n%(m+1)，然后这时n%(m+1)=0，然后这时，无论后手如何操作，先手只需要将一份剩下的m+1取完，直到最后取完。这时，先手必胜
当n%(m+1)=0时，同上，此时后手必胜

三、
威佐夫博弈：两堆物品，两人轮流取，一次可以从一堆取至少一个，至多全部，或从两堆取相同数，取最后一个的人获胜。

思路：这个感觉不需要证明，只要记住结论即可：1.618(或是(sqrt(5.0)+1)/2)*(abs(b-a))=min(a,b)就是后手赢其余都是先手赢。用语言描述呢就是假设1.618乘以两个差值=较小的值，那么就是后手赢否则就是先手赢
奇偶性博弈：有$n$堆石子，第$i$堆石子有$a_i$个，保证初始时$a_i$$\le$$a_{i+1}$(1$\le$i$<$n)。现在他们轮流对这些石子进行操作，每次操作人可以选择满足$a_i$>$a_{i-1}$（$a_0$视$0$）的一堆石子，并从中取走一个。谁最后不能取了谁输。$Alice$先手，他们都使用最优策略，判断最后谁会取得胜利。

证明：
1：首先很明显的就是只要是有石子就可以取，因为第一堆石子总比第0堆石子多。所以肯定是最终一定取完才可以分出胜负
2：这样的话就是奇数的话就是先手胜，偶数的话就是后手胜

也可以把上面的情况扩展到二维平面中，题目描述如下：
在一个$n\ast n$的棋盘上有一个棋子，放置在$(1,1)$这个位置，要求移动过的位置不能再被移动，最终不能被移动的人输。
我们可以发现一定不会出现就是一人被一人围住这种情况，因为我们可以发现只要被围住的时候一定会有一个人输，那么输的这个人一定会在被围住之前移到别处。
所以，所有的$n^2-1$个都会被走完，所以若其为奇数则先手赢，反之后手赢

四、
SG函数：
我们将nim游戏变得难一些，假设每次能够取的石子不是任意个了，我们假设第一堆可以取1，2，3，第二堆可以取偶数个，第三堆可以取奇数个，剩下的可以随便取。这样就不能用简单的nim来解决了，我们在这里就可以用SG函数来解决这个问题。

我们可以将一个博弈问题抽象成在有向无环图上一个的问题，假设图上的某一个顶点有一枚棋子，两个人分别移动这个棋子，最终无法移动的一个人输。这样的话任何一种局面我们可以看做一个顶点，用一条线连接他的子局面。

首先定义一个mex{}函数，他表示集合中不存在的最小的非负整数，mex{}=0,mex{1,2,0}=3,.mex{1,2,3}=0;

sg[x]=mex{sg(y)|y是x的后继}

我们可以给出sg函数的几个结论和结论的简单说明。

1：sg[x]=0表示x处于先手必败态（当然这个x状态需要具体问题具体分析，可能是1也可能是0或者其他 ），这个是由sg函数的定义决定的。我们可以做一个简单的说明：我们假设当前处于最后一个状态，那么下一个一定是空状态，这时候，sg[x]=0，即表示无法到达下一个状态了，这样一定是必败的。所以将sg[x]=0的状态设为必败态。
2：假设初始的情况下由很多种状态的时候，我们将sg[1] ^ sg[2] ^ sg[3] ^ ……=0的处于先手必胜，否则就是先手必败。

我们可以简单证明以下：这是类似于nim博弈的，sg函数的定义就是：我们可以达到的状态，假设sg[x]=k，那么表示可以将这x状态变成0,1,2,3,……,k-1，但是不能不变，所以这就和nim博弈联系起 来了，谁最后能拿完谁就胜，因为sg[x]存的是下一层sg函数的集合，所以也可以做这样的操作，最中化作有n堆石子的nim博弈问题。

注意：我们求mex得时候从最底层求，因为不同的题有不同的状态，而且层数也不同，所以不同的状态有不同的sg值

详细sg函数讲解参考博客：博客链接

下面是一道例题：戳我
这道题的SG就是找规律的。

我们要注意一个点就是mex{}里面的是一个一个子局面。

我们首先就是判断SG(1)=0，然后依次往上找即可。

但是要记住的是假设我们将8分成4个2，所以我们应该将所有的状态sg值异或起来就是原来的答案，这里我感觉用mex的话太复杂了，所以用sg值异或的方法比较好。

其实想想也是，如果我们将某一个数分成了几个相等的数，那么这就不是单独的状态了，这几个数共同构成一个状态，所以我们应该将他们的值求出来，然后把所有的值异或起来，得到的异或结果，构成这个分状态的值，下面是AC代码：（参考网上的代码，具体的可以网上搜一下题解）

#include 
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int p[maxn], cnt;
int flag[maxn];

void prime()
{
    for(int i = 2; i < maxn; i++)
    {
        if(!flag[i]) p[cnt++] = i;
        for(int j = 0; p[j] < maxn / i; j++)
        {
            flag[p[j] * i] = 1;
            if(i % p[j] == 0) break;
        }
    }
}

int sg(int x)
{
    int res = 0;
    for(int i = 0; i < cnt && p[i] <= x / p[i]; i++)
    {
        if(x % p[i] == 0)
        {
            if(p[i] == 2)
            {
                res++;
                while(x % p[i] == 0)
                    x /= p[i];
            }
            else
            {
                while(x % p[i] == 0)
                    x /= p[i], res++;
            }
        }
    }
    if(x > 1) res++;
    return res;

}

int main()
{
    prime();
    int t; scanf("%d", &t);
    while(t--)
    {
        int n; scanf("%d", &n);
        int res = 0;
        for(int i = 1; i <= n; i++)
        {
            int x; scanf("%d", &x);
            res ^= sg(x);
        }
        printf("%s\n", res ? "W" : "L");
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68