又学会了新姿势。。。
把游戏变成黑棋也可以翻转
发现假如黑棋也可以翻转也没有人会翻，因为假如这个是一个好的决策人家可以翻回来
但假如你翻了白的人家也可以翻回来怎么办？面对这个局面你会去走最优决策，让别人翻回来显然不优。。。。感性理解。。。
那么就是新姿势，这种翻转棋子问题可以把每个棋子当成一个子游戏再算异或和
考虑sgi=mex(0,sg2*i,sg2*i^sg3*i,……)暴力搞会T
对于这个题流弊的性质，就是sg(i)==sg(j)当n/i==n/j，不会证跑了跑了（强行找规律？）
然后就可以按除n的值分块，还有计算的时候每次一个一个块异或
估计GDOI出了我就凉了
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; const int _=1e2; const int maxs=4*1e4+_; int n,sn; int sga[maxs],sgb[maxs]; int SG(int x){ x=n/x; if(x<=sn)return sga[x]; else return sgb[n/x]; } void upd(int x,int d){ x=n/x; if(x<=sn)sga[x]=d; else sgb[n/x]=d; } int plen,p[maxs]; int tim,v[maxs]; void init() { for(int i=1;i<=n;i=n/(n/i)+1)p[++plen]=n/(n/i); tim=0; for(int i=plen;i>=1;i--) { tim++;v[0]=tim; if(2*p[i]>n){upd(p[i],1);continue;} int u=0,R,num; for(int j=2*p[i];j<=n;j+=num*p[i]) { v[u^SG(j)]=tim; R=n/(n/j); num=(R-j)/p[i]+1;//这个块里有多少p[i]的倍数 if(num%2==1)u^=SG(j); } for(int j=0;;j++) if(v[j]!=tim){upd(p[i],j);break;} } } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); scanf("%d",&n); sn=int(sqrt(double(n+1))); init(); int T,m,x,ans; scanf("%d",&T); while(T--) { scanf("%d",&m); ans=0; for(int i=1;i<=m;i++) scanf("%d",&x),ans^=SG(x); if(ans==0)puts("No"); else puts("Yes"); } return 0; }