SCUT - 290 - PARCO的因数游戏 - 博弈论

https://scut.online/p/290

一个 N 个数的取数游戏，Kaildls 和 Parco 轮流操作，每次操作从 N 个数中取一个数 y 并把他变成 y-x(满足 x | y 且x < y)，无法操作的人输。

假设 Kaildls 先手且两人都是用最优策略，请问最后谁会赢？

第一次学SG函数，要找的是每次能从石子堆中取走的数目，记录下来。

最后的Nim和为0是后手赢？

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define MAXN 1000005

#define N 1000005

//f[N]:可改变当前状态的方式，N为方式的种类，f[N]要在getSG之前先预处理

//SG[]:0~n的SG函数值

//S[]:为x后继状态的集合

vector<int> nextofSG[MAXN];

int f[N],SG[MAXN],S[MAXN];

void  getSG(int n){

    for(int i = ; i <= n; i++){

        int l=nextofSG[i].size();

        //后继状态 最多有l 种

        for(int j=;j<=l;j++){

            S[j]=;

        }

        for(auto vi:nextofSG[i]){

            //vi：从i状态能取走的石子数

            S[SG[i-vi]]=;

        }

        for(int j=;j<=l;j++){

            if(!S[j]){

                SG[i] = j;

                break;

            }

        }

        //cout<<"SG["<<i<<"]="<<SG[i]<<endl;

    }

}

int a[];

unsigned generateai(unsigned &n,unsigned &x,unsigned &y, unsigned &z){

    x=x^(x<<);

    x=x^(x>>);

    x=x^(x<<);

    x=x^(x>>);

    unsigned w=x^(y^z);

    x=y;

    y=z;

    z=w;

    return z;

}

int main(){

    unsigned n,x,y,z;

    for(int i=;i<=;i++){

        for(int j=i+i;j<=;j+=i){

            nextofSG[j].push_back(i);

        }

    }

    getSG();

    for(int t=;t<;t++){

        cin>>n>>x>>y>>z;

        int sumSG=;

        for(int i=;i<n;i++){

            a[i]=generateai(n,x,y,z)%n+;

            //cout<<a[i]<<endl;

            sumSG^=SG[a[i]];

        }

        //cout<<"!"<<sumSG<<endl;

        if(sumSG==)

            cout<<"Parco"<<endl;

        else{

            cout<<"Kaildls"<<endl;

        }

    }

}