题解 CF768E 【Game of Stones】
Forever_Pursuit
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` 映射回去。
```cpp
#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;
}
```