题解 P3179 【[HAOI2015]数组游戏】

~~折腾一晚上终于搞出来了~~ ### Step1 首先是翻棋子问题的套路，每个棋子可以作为单个游戏，整个游戏就是所有白棋子的SG异或和，可以想到一个暴力算SG的方法，有50分 ### Step2 进一步优化就是可以打表发现$\frac{n}{i}$下取整的值相同的棋子SG值相同（i表示位置），于是有一个分块想法 先处理$q[i]=k$表示从左到右第i块的右端点为k，然后我们枚举x=q[i]，同时记录res为异或和，cnt表示有多少不同的SG值，于是我们对于区间[L,R]（[L,R]的$\frac{n}{i}$值相等），我们需要由下面的状态取mex转移 $$\{0,SG([2L,2R]),SG([2L,2R]\ xor\ SG[3L,3R]....)\}$$ 于是我们接下来对[l,r]分块（[l,r]表示[L,R]的[l,r]倍在同一个大块里面），用这个的奇偶性来维护SG异或的前缀和 最后一个优化是存储x的值，块x表示右端点x，$\frac{n}{i}$，那么如果x在1到根号n只之内直接存，否则存$\frac{n}{i}$，这样子就能优化空间到根号n了 ```cpp #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> using namespace std; const int N=500000; int T,n,W,c[N],a[N],b[N]; int q[N],nn,tag[N],tot; void Pre() { nn=sqrt(n);tot=0; for(int l=1,r;l<=n;l=r+1) r=n/(n/l),q[++tot]=r; for(int u=tot;u;u--) { int x=q[u],res=0,cnt=0; for(int l=2*x,r;l<=n;l=r+x) { r=n/(n/l)/x*x; int z=r>nn?b[n/r]:a[r]; c[++cnt]=res^z;tag[c[cnt]]=1; if(((r-l)/x+1)&1) res^=z; } res=1;while(tag[res]) res++; x>nn?b[n/x]=res:a[x]=res; for(int i=1;i<=cnt;i++) tag[c[i]]=0; } } void work() { cin>>W;int res=0; for(int i=1;i<=W;i++) { int x;cin>>x; res^=x>nn?b[n/x]:a[x]; } res?puts("Yes"):puts("No"); } int main() { cin>>n>>T;Pre(); while(T--) work(); } ``` 打个小广告：[博弈总结](https://www.cnblogs.com/xzyxzy/p/9397756.html) 管理员请重新审核之前有个地方有误`o=o`