【SG+奇偶性压状态】江南乐

博弈

传送门：BZOJ3576

思路：

  • 考虑暴力求出不同个数石子的SG值，直接枚举后继状态，然后会TLE；
  • 发现对于i个石子，分成j堆数后每堆石子的个数可能是$\large \lfloor\frac{i}{j}\rfloor,\lfloor\frac{i}{j}\rfloor+1$；
  • 对于相同的i，显然可以找到不同的$\large \lfloor\frac{i}{j}\rfloor,\lfloor\frac{i}{j}\rfloor+1$，而后继状态实际只与个数为$\large \lfloor\frac{i}{j}\rfloor,\lfloor\frac{i}{j}\rfloor+1$石子的堆数的奇偶性有关，所以有很多状态是重复的；
  • 考虑快速求出$\large \lfloor\frac{i}{j}\rfloor$相同时的后继状态：如果j只有1个，那么直接算；如果有多个j，只需算前2个即可。

代码如下：

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
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define M 100005
int t,n,m,ans,nxt,x,sg[M],mex[M];
void getsg(){
	for (int i=m;i<=M;i++){
		for (int j=2;j<=i;j=nxt+1){
			int k=i/j,a,b,tmp; nxt=i/k;
			if (nxt==j){
				b=i-j*k; a=j-b; tmp=0;
				if (a&1) tmp^=sg[k];
				if (b&1) tmp^=sg[k+1];
				mex[tmp]=i;
			}
			else{
				b=i-j*k; a=j-b; tmp=0;
				if (a&1) tmp^=sg[k];
				if (b&1) tmp^=sg[k+1];
				mex[tmp]=i;
				j++; b=i-j*k; a=j-b; tmp=0;
				if (a&1) tmp^=sg[k];
				if (b&1) tmp^=sg[k+1];
				mex[tmp]=i;
			}
		}
		for (int j=0;mex[j]==i;j++) sg[i]=j+1;
	}
}
int main(){
	scanf("%d%d",&t,&m);
	getsg();
	while (t--){
		scanf("%d",&n); ans=0;
		for (int i=1;i<=n;i++){scanf("%d",&x); ans^=sg[x];}
		if (ans==0) printf("%d%s",0,t?" ":"\n");
		else printf("%d%s",1,t?" ":"\n");
	}
	
	return 0;
}