Problem - C - Codeforces

题目大意：有n堆石子，给出一个数p，A先B后，每个人每次只能取p的幂个石子（包括1）问A能不能赢

1<=n<=3e5;1<=p<=1e18

思路：先递归算出sg函数看看，sg(0)=0，sg(x)能转移的位置也就是sg(x-)

打出表发现如果p是奇数，那么当x为奇数时sg(x)=1，x为偶数时sg(x)=0，如果p是偶数，sg(x)会出现长度为p+1的循环节，x对p+1取模后，如果新的x是奇数，sg(x)=1，如果x=p，sg(x)=2，否则sg(x)=0

因为每堆石子都是相互独立的游戏，根据打表发现的规律求出每一堆石子的sg值然后求异或和即可

//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
map<ll,ll>sg;
ll po[100];
const int N=3e5+5;
int it=1;
ll dfs(ll x)
{//递归计算sg值
	if (sg.find(x)!=sg.end())
	{//记忆化搜索
		return sg[x];
	}
	set<ll>s;
	for (int i = 1; i <= it-1; i++)
	{//能转移到的地方
		ll j = x-po[i];
		if (j < 0)
			continue;
        ll temp=dfs(j);
        sg[j]=temp;
		s.insert(sg[j]);
	}
	int now = 0;
	while (s.count(now))
	{//找MEX
		now++;
	}
	return now;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	sg[0] = 0;
    sg[1]=1;
    ll n,p;
    ll ans=0;
    cin>>n>>p;
    ll now=1;
    //while(now<=INF)
    //{//预处理p的幂
        //po[it++]=now;
        //now*=p;
    //}
    // for(int i=1;i<=1000;i++)
    // {//打表找规律
    //     ll temp=dfs(i);
    //     sg[i]=temp;
    //     cout<<sg[i]<<endl;
    // }
    if(p&1)
    {
        for(int i=1;i<=n;i++)
        {
            ll x;
            cin>>x;
            ll temp=x%2;
            if(temp&1)
            {
                ans^=1;
            }
            //cout<<ans<<endl;
        }
    }
    else
    {
        for(int i=1;i<=n;i++)
        {
            ll x;
            cin>>x;
            ll temp=x%(p+1);
            if(temp&1)
            {
                ans^=1;
            }
            else if(temp==p)
            {
                ans^=2;
            }
            //cout<<ans<<endl;
        }
        
    }
    cout<<(!ans?"BAD":"GOOD")<<endl;
//    for(int i=1;i<=n;i++)
//         {
//             ll x;
//             cin>>x;
//             ll temp=dfs(x);
//             sg[x]=temp;
//             ans^=sg[x];
//             //cout<<ans<<endl;
//         }
	return 0;
}