题解 CF768E 【Game of Stones】

2020-12-31 13:05:58


垃圾做法喜提 luogu 时间最劣解+空间最劣解+代码长度最劣解。

考虑状压,第 $i$ 位为 $1$ 表示之前某次已经取过了 $i$ 个石子,

设 $sg_{i,j}$ 表示当前剩 $i$ 个石子,状态为 $j$ 的 $sg$ 值,

虽然一共有 $2^{60}$ 种状态,但是其中真正有效的却不多,对于某个状态,所有为 $1$ 的位的下标的和显然不能超过 $60$,否则为无效状态,

可以写一个 dfs 搜出所有有效状态,发现只有 $101983$ 种,

于是可以对于所有有效的 $sg$ 暴力求 $mex$,时间复杂度为 $O(101983\times60^2)$,即可得到所有 $sg_{i,j}$,答案即为 $sg_{a_i,0}$ 的 $xor$,

实现时可以给每个有效状态分配一个下标,用 unordered_map 映射回去。

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define N 60
int read(){
    int w=0,f=1;
    char c=' ';
    while(c<'0'||c>'9')c=getchar(),f=c=='-'?-1:f;
    while(c>='0'&&c<='9')w=w*10+c-48,c=getchar();
    return w*f;
}
int n,sg[N+1][102000],sum[102000],cnt;
ull vis[102000],fl,ind[N+1],all=ULONG_LONG_MAX;
unordered_map<ull,int>mp;
bool ap[N+1];
void dfs(int now,int s){
    if(s>N)return;
    if(now==N)return vis[++cnt]=fl,sum[cnt]=s,mp[fl]=cnt,void();
    now++;
    fl&=ind[now];
    dfs(now,s);
    fl|=(1llu<<now);
    dfs(now,s+now);
}
void init(){
    for(int i=1;i<=N;i++)
        ind[i]=all^(1llu<<i);
    dfs(0,0);
    for(int i=1;i<=N;i++){
        for(int j=1;j<=cnt;j++){
            if(sum[j]+i>N)continue;
            memset(ap,0,sizeof(ap));
            for(int k=1;k<=N;k++)
                if(!(vis[j]>>k&1)&&i-k>=0)ap[sg[i-k][mp[vis[j]|1llu<<k]]]=1;
            for(int k=0;;k++)
                if(!ap[k]){
                    sg[i][j]=k;
                    break;
                }
        }
    }
}
signed main(){
    init();
    n=read();
    int ans=0;
    for(int i=1;i<=n;i++)
        ans^=sg[read()][1];//显然mp[0]=1
    puts(ans?"NO":"YES");
    return 0;
}