题目描述
有一个长度为N的数组，甲乙两人在上面进行这样一个游戏：首先，数组上有一些格子是白的，有一些是黑的。然
后两人轮流进行操作。每次操作选择一个白色的格子，假设它的下标为x。接着，选择一个大小在1~n/x之间的整数
k，然后将下标为x、2x、...、kx的格子都进行颜色翻转。不能操作的人输。现在甲（先手）有一些询问。每次他
会给你一个数组的初始状态，你要求出对于这种初始状态他是否有必胜策略。
输入格式
接下来2*K行，每两行表示一次询问。在这两行中，第一行一个正整数W，表示数组中有多少个格子是白色的，第二
行则有W个1~N之间的正整数，表示白色格子的对应下标。
输出格式
对于每个询问，若先手必胜输出"Yes"，否则输出"No"。答案之间用换行隔开
数据范围
N<=1000000000 ， K,W<=100 ， 不会有格子在同一次询问中多次出现。
-
题解
- 可以发现变颜色这类问题是符合分解理论的，求出所有位置的sg值异或得到游戏的sg值；
- 考虑所有位置的sg值如何求；
- 可以写出一个$O(n^2)$的暴力(注意终止状态的$sg$为0);
- 考虑改进暴力，打表发现对于一个$n$的所有$i$，$\frac{n}{i}$相同的位置sg值也相同；
- 将$n$下底分块，就只需要求出$\sqrt{n}$个块的sg函数；
- 由于是异或，只需要判断在某个块里的奇偶性就可以知道经过这个块的异或值；
- 同时sg值由于是$mex$所以没有很大，$i<=sqrt(n)$的直接存，$i>sqrt{n}$的存在$\frac{n}{i}$里面：
- 时间复杂度：$O(n)$ ?， 空间复杂度：$O(\sqrt{n})$;
1 #include2 using namespace std; 3 const int N=1e5; 4 int n,m,u,a[N],b[N],tot,vis[N],q[N]; 5 void pre(){ 6 for(int i=tot,tmp;i;--i){ 7 tmp=0; 8 int x = q[i]; 9 for(int j=x*2,lst;j<=n;j=lst+x){10 lst=n/(n/j)/x*x;11 int t=lst<=u?a[lst]:b[n/lst];12 vis[tmp^t]=i;13 if(((lst-j)/x+1)&1)tmp^=t;14 }15 for(int j=1;;++j)if(vis[j]!=i){tmp=j;break;}16 if(x<=u)a[x]=tmp;else b[n/x]=tmp;17 }18 }19 int main(){20 #ifndef ONLINE_JUDGE21 freopen("bzoj4035.in","r",stdin);22 freopen("bzoj4035.out","w",stdout);23 #endif24 scanf("%d%d",&n,&m);u=sqrt(n);25 for(int i=1,lst;i<=n;i=lst+1){lst=n/(n/i);q[++tot]=lst;}26 pre();27 for(int i=1,x,tmp;i<=m;++i){28 scanf("%d",&x);tmp=0;29 for(int j=1,y;j<=x;++j){30 scanf("%d",&y);31 y=n/(n/y);32 tmp^= y<=u?a[y]:b[n/y];33 }34 puts(tmp?"Yes":"No");35 }36 return 0;37 }
1 #include2 using namespace std; 3 const int N=1010; 4 int n,vis[N],sg[N]; 5 int main(){ 6 // freopen("exp.in","r",stdin); 7 freopen("exp.out","w",stdout); 8 for(n=1;n<=1000;++n){ 9 for(int i=1;i<=n;++i)sg[i]=0;10 for(int i=n;i;--i){11 for(int j=0;j<=n/i;++j)vis[j]=0;12 int tmp = 0;13 for(int j=i+i;j<=n;j+=i){14 tmp ^= sg[j];15 vis[tmp]=1;16 }17 for(int j=1;j<=n/i;j++)if(!vis[j]){sg[i]=j;break;}18 }19 //for(int i=1;i<=100-n+1;++i)putchar(' ');20 //for(int i=1;i<=n;++i)putchar(' ');21 for(int i=1;i<=n;++i)printf("%d ",sg[i]);22 //printf("%d ",sg[n-2]);23 //for(int i=3;i<=n;i+=3)printf("%d ",sg[i]);24 puts("");25 }26 /*27 int now = 20, cnt=0;28 for(int i=now,j;i;i=j,now>>=1){29 j = i - ((now + 1)>>1);30 for(int k=i;k>j;--k)printf("%d",sg[k]),cnt++;31 puts("");32 }33 cout< <