【SG+推性质】数组游戏

博弈

传送门：BZOJ4035

思路：

  • 似乎可以把黑格子当作白格子$\times 2$；
  • 考虑直接求出每个白格子的SG值，然后TLE；
  • 推一波性质发现每个格子SG值只与能条的步数有关，所以状态只有$\sqrt n$级别。

注意：

  • 存储时可以使用一些高超的技巧。srO lych_cys Orz

代码如下（srO lych_cys Orz）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 120000
int n,m,t,p,x,ans,sg[2][N],mex[N];
int nxt(int x,int y){return (x==y)?y+1:x/(x/(y+1));}
int main(){
	scanf("%d",&n); m=(int)sqrt(n);
	sg[0][1]=1;
	for (int i=2;i<=n;i=nxt(n,i)){
		int tmp=0,now=0;
		for (int j=2;j<=i;j=nxt(i,j)){
			x=i/j; if (x<=m) tmp=sg[0][x]; else tmp=sg[1][n/x];
			mex[now^tmp]=i;
			if ((i/x-i/(x+1))&1) now^=tmp;
		}
		if (i<=m) sg[0][i]=1; else sg[1][n/i]=1;
		for (int j=1;mex[j]==i;j++)	if (i<=m) sg[0][i]=j+1; else sg[1][n/i]=j+1;
	}
	scanf("%d",&t);
	while (t--){
		scanf("%d",&p); ans=0;
		for (int i=1;i<=p;i++){scanf("%d",&x); x=n/x; ans^=x<=m?sg[0][x]:sg[1][n/x];}
		if (ans) puts("Yes"); else puts("No");
	}
	
	return 0;
}