数论

博弈论：sg函数

定义

NIM博弈：

给定n堆物品，第$i$堆物品有$A_i$ 个，两名玩家轮流行动，每次任选一堆，取出任意多个物品，取走最后一件物品者胜利。

当且仅当 $A_1 xorA_2xor…xorA_n$时，NIM博弈先手必胜。

公平组合游戏ICG：（NIM就是经典的公平组合游戏）

1.由两名玩家交替行动
2.在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关
3.不能行动的玩家判负

有向图游戏：

给定一个有向无环图，途中有唯一的起点，在起点放一枚棋子。两名玩家交替把这个棋子沿边移动，无法移动者判负。

公平组合游戏都可以转化为有向图游戏。

SG函数：

在有向图游戏中，对于节点x，设从节点x出发分别到达了$y_1,y_2,…,y_k$ ，定义$sg(x)$:

$sg(x) = mex({ sg(y_1),sg(y_2),…,sg(y_k)})$ 。（mex(s)表示不属于集合s的最小非负整数）

对于整个有向图G，$sg(G) = sg(s)$

对于多个有向图游戏$G_1,G_2,…,G_m$的和G
$SG(G) = SG(G_1)xorSG(G_2)xor…xorSG(G_m)$

$sg(x)>0$ 表示这个局面必胜，$sg(x)=0$表示这个局面必败

代码模板

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
#include<iostream>
#include<cstring>
#include<unordered_set>
using namespace std;
const int N = 1e5+5;//N表示一个堆最多多少物品
int f[N];//f[i] = sg(i).记忆化搜索
int num[50];//num储存总的有向图的数量（也就是NIM中的有几堆物品）
int sg(int x){
    if(f[x] != -1) return f[x];
    unordered_set<int> s;
    //出边，分别代表取一个，取两个，全取出来
    if(x >= 1) s.insert(sg(x-1));
    if(x >= 2) s.insert(sg(x-2));
    s.insert(sg(0));
    //mex
    for(int i = 0;;i++){
        if(!s.count(i)) return f[x] = i;
    }
}
int main(){
    memset(f,-1,sizeof(f));
    f[0] = 0;//初始值，可以不设?,也可以视情况设其他的(例如脑算出sg(1),sg(2)等，然后直接给出值)
    int res = 0;//总的sg
    for(int x : num){
        // res ^= sg(x);
    }
    return 0;
}

例题

Men’s showdown

https://codeforces.com/gym/102780/problem/H

给出一堆物品n，双方分别拿走1，5，13个，拿走最后一个者失败。问谁会获胜

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
#include<iostream>
#include<cstring>
#include<unordered_set>
using namespace std;
int f[10005];//f[i] = sg(i).记忆化搜索
int num[50];//num储存总的有向图的数量（也就是NIM中的有几堆物品）
int sg(int x){
    if(f[x] != -1) return f[x];
    unordered_set<int> s;
    if(x >= 1) s.insert(sg(x-1));
    if(x >= 5) s.insert(sg(x-5));
    if(x >= 13) s.insert(sg(x-13));
    //mex
    for(int i = 0;;i++){
        if(!s.count(i)) return f[x] = i;
    }
}
int main(){
    memset(f,-1,sizeof(f));
    int x;
    cin>>x;
    if(sg(x)) cout<<2;
    else cout<<1;
    return 0;
}

A word game

https://codeforces.com/gym/102780/problem/F

有一个只有大写字母的字符串，双方轮流进行如下操作之一，最终拿走最后一个字符者获胜
1.拿走一个字符
2.拿走两个相同的字符
3.拿走某种字符的全部

将每种字符看作一个NIM博弈，那么答案就是所有NIM博弈的“和”。最终的sg函数也就是各自的sg函数的异或和。

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
#include<iostream>
#include<cstring>
#include<unordered_set>
using namespace std;
int num[30];
int f[100];
int sg(int x){
    if(f[x] != -1) return f[x];
    unordered_set<int> s;
    if(x >= 1) s.insert(sg(x-1));
    if(x >= 2) s.insert(sg(x-2));
    if(x >= 3) s.insert(sg(0));
    for(int i = 0;;i++){
        if(!s.count(i)) return f[x] = i;
    }
}
int main(){
    string str;
    cin>>str;
    for(auto p : str){num[p-'A'+1]++;}
    memset(f,-1,sizeof(f));
    f[0] = 0;
    int res = 0;
    for(int i = 1;i<=26;i++){
        res ^= sg(num[i]);
    }
    if(res) cout<<"Alice";
    else cout<<"Bob";
    return 0;
}