战斗

给定正整数 $n,p$ 和 $n$ 堆石子，第 $i$ 堆石子中有 $a_i$ 个石子。

两个玩家轮流操作，每次必须选定一个非空石子堆取走 $p^k \ (k \geq 0)$ 个石子，无法操作者失败。

判断是否先手必胜，$1 \leq n \leq 3 \times 10^5$，$1 \leq p,a_i \leq 10^{18}$。

题目链接

数学、博弈论

公平组合游戏考虑从 $\operatorname{SG}$ 函数方向入手解决，由于 $\operatorname{SG}$ 函数不是简单的胜负 $01$ 状态，并且研究的是最小规模子问题，容易发现规律。

考虑计算每个堆的 $\operatorname{SG}$ 值，然后通过异或合并。当 $p$ 为奇数时，容易发现 $\operatorname{SG}(x) = x \bmod 2$。对于较难的 $p$ 为偶数的情况，打个表观察一下 $\operatorname{SG}$ 函数的值。

#include<bits/stdc++.h>
using namespace std;
int n,p,sg[105];
bool on[105];
void dfs(int x){
    if(on[x]) return;
    on[x]=1;
    vector<int> v;
    int aim=1;
    while(aim<=x){
        dfs(x-aim);
        v.push_back(sg[x-aim]);
        aim*=p;
    }
    sort(v.begin(),v.end());
    for(int i:v) if(sg[x]==i) ++sg[x];
}
int main(){//计算 n 个石子在给定 p 情况下每个状态的 SG 值
    scanf("%d%d",&n,&p);
    on[0]=1,dfs(n);
    ofstream fout("CC.out");
    for(int i=0;i<=n;i++) fout<<i<<' '<<sg[i]<<'\n';
    return 0;
}

观察发现 $\operatorname{SG}$ 函数以 $0 \sim p$ 为第一个周期，$p+1 \sim 2p+1$ 为第二个周期，以此类推。

同时，第一个周期满足 $\operatorname{SG}(p)=2$，其余 $\operatorname{SG}(x) = x \bmod 2$。

对于每一堆求出其 $\operatorname{SG}$ 值。先手必胜当且仅当初始局面 $\operatorname{SG}$ 值不为 $0$，时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
long long p;
int n,ans;
int main(){
    scanf("%d%lld",&n,&p);
    for(int i=1;i<=n;i++){
        static long long x;
        scanf("%lld",&x);
        if(p&1) ans^=x&1;
        else{
            x%=p+1;
            if(x==p) ans^=2;
            else ans^=x&1;
        }
    }
    puts(ans ? "GOOD":"BAD");
    return 0;
}