简单介绍几种常见的博弈类型，之前虽然看了sg函数相关的原理等等，做题的时候遇见的博弈题目也不少，然而我的感想却是：我怎么什么也不会啊
大多数时候博弈都和图论、动态规划之类的结合在了一起，就算看出来是博弈的题目，也无从下手，比如昨天做到的一道牛客上的完全图删边的博弈赞迪卡之声妮莎与奥札奇

反正现在不急于尽早出成果之类的，能学多少是多少吧同时也发现不会的还是很多，暂时先暂停比赛学一段时间

Nimk

母题：n堆石子，每次从不超过k堆中取任意多个石子，最后不能取的人失败。

结论：将n堆石子的数量进行k+1进制异或，如果最终的答案是0，那么为p-position，否则为n-position，k+1进制就是将所有数的二进制各位不进位相加后对k+1取模。

POJ-2315 Football Game
题意：一开始有n个到球门距离不同的足球，Alice和Bob轮流从n个足球当中最多选取k个踢球，最远都只能达到一定距离，最后谁没球踢谁就输了。

代码 
//#include<bits/stdc++.h>
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<string>
#include<string.h>
#include<map>
#include<math.h>

//#define int long long
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define all(a) begin(a),end(a)
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define sz(x) ((int)x.size())
#define ins insert
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define lowbit(x) ((x)&(-x))
using namespace std;

const int maxn=35;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
#define pi acos(-1.0)
int main(){
    fastio;
    int n,m,l,r;
    while(cin>>n>>m>>l>>r){
        int a[maxn];
        int sg[maxn]={};
        int xo[100]={};
        l/=(2*pi*r);
        int mx=0;
        for(int i=1;i<=n;++i){
            cin>>a[i];
            a[i]=a[i]/(2*pi*r)+1;
            sg[i]=a[i]%(l+1);
            int tmp=1;
            while(sg[i]){
                xo[tmp++]+=sg[i]&1;
                sg[i]>>=1;
            }
            mx=max(mx,tmp);
        }
        int f=1;
        for(int i=1;i<mx;++i){
            if(xo[i]%(m+1)){
                f=0;
                cout<<"Alice"<<endl;
                break;
            }
        }
        if(f)cout<<"Bob"<<endl;
    }

}

阶梯Nim

母题：在阶梯上进行，每层有若干个石子，每次可以选择任意层的任意个石子将其移动到该层的下一层。最后不能操作的人输。

结论：结果与奇数堆的Nim结果相同。可以先假设先手的情况，每次将石子从奇数堆移往偶数堆，后手若同样采取从奇数堆移往偶数堆，按奇数堆Nim的必胜策略走即可，如果对手选择从偶数堆移往奇数堆，从被移动到的奇数堆移动相同数目的石子到偶数堆即可，对奇数堆的情况并无影响。

POJ-1704 Georgia and Bob Game
题意：从左到右有一排石子，给出石子所在的位置。规定每个石子只能向左移动，且不能跨过前面的石子。最左边的石子最多只能移动到1位置。每次选择一个石子按规则向左移动，问先手是否能赢。

代码 
//#pragma GCC optimize(3,"Ofast","inline")
//#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

//#define int long long
#define pb push_back
#define st first
#define nd second
#define sz(x) ((int)x.size())
#define ins insert
#define fastio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define lowbit(x) ((x)&(-x))
#define pi acos(-1.0)
using namespace std;

const int maxn=1e5+10;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;

int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
int lcm(int a,int b){
    return a*b/gcd(a,b);
}
int a[1005]={};
int main(){
    fastio;
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;++i)cin>>a[i];
        sort(a+1,a+n+1);
        vector<int>b;
        for(int i=1;i<=n;++i)b.pb(a[i]-a[i-1]-1);
        int tot=sz(b);
        int ans=0;
        for(int i=tot-1;i>=0;i-=2){
            ans^=b[i];
        }
        if(ans)cout<<"Georgia";
        else cout<<"Bob";
        cout<<" will win"<<endl;
    }
}

反Nim

母题：正常的nim游戏是取走最后一颗的人获胜，而反nim游戏是取走最后一颗的人输。

结论：一个状态为必胜态，当且仅当：
1）所有堆的石子个数为1，且NIM_sum(xor和)=0
2）至少有一堆的石子个数大于1，且 NIM_sum(xor和) ≠ 0

Bash Game

母题：只有一堆石子共n个。每次从最少取1个，最多取m个，最后取光的人取胜。

结论：如果n%(m+1)那么先手一定必胜，最简单的博弈，用sg函数就可以看出只有当x是m+1的整数倍时sg[x]=0。

Lasker’s Nim

母题：Alice和Bob轮流取石子，每一次可以从任意一堆中拿走任意个石子，也可以将一堆石子分为两个小堆。先拿完者获胜。

结论：

if(x%4==0) sg[x]=x-1;
else if(x%4==1||x%4==2) sg[x]=x;
else if(x%4==3) sg[x] = x+1;

这种题一般要对sg值打表。(对于先拿完者获胜：sg值为零先手必败，否则后手必胜)

Wythoff's game

问题：两堆石子，每次可以取一堆或两堆，从两堆中取得时候个数必须相同，先取完的获胜。

结论： ak =[k *（1+√5）/2]，bk= ak + k （k=0，1，2，…,n 方括号表示取整函数)

这种博弈完全没搞懂，先只记住结论，树上和图上的博弈留给下一期吧。