这题又是我什么时候做的(挠头)
首先是个和SG函数有关的博弈论,SG=0则先手必败.显然一堆石子就是一个游戏,而若干堆石子的SG值就是每堆SG的异或和,所以算出每堆石子SG就能知道答案
然后怎么求SG,根据定义,一个局面SG是后继局面SG的\(mex\),我们枚举某堆石子(有x个)分成多少堆i,然后能知道有若干堆石子有\(\lfloor\frac{x}{i}\rfloor\)个,还有的有\(\lceil\frac{x}{i}\rceil\)个.然后这两种石子的堆数也可以算出来,又因为异或某个数偶数次=0,所以只要分奇偶性看是否异或就好了.
上述过程可以加记忆化优化.但是暴力枚举还是不行的,注意到\(\lfloor\frac{x}{i}\rfloor\)最多只有\(2\sqrt n\)种取值,所以可以参考数论分块的做法,对于\(\lfloor\frac{x}{i}\rfloor\)相同的一些\(i\),只要计算最小的\(i\)以及\(i+1\),因为更大的\(i\)的贡献和\(i\)与\(i+1\)中某一个是相同的
#include<bits/stdc++.h>
#define LL long long
#define db double
#define il inline
#define re register
using namespace std;
const int N=1e5+10;
il int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int sg[N],mm[N];
int t,f,n;
il int sov(int o)
{
if(o<f) return 0;
if(~sg[o]) return sg[o];
sg[o]=0;
for(int i=2;i<=o;i=o/(o/i)+1)
{
int xx=0;
if((o%i)&1) xx^=sov(o/i+1);
if((i-o%i)&1) xx^=sov(o/i);
mm[xx]=o;
if(i==o) continue;
xx=0,++i;
if((o%i)&1) xx^=sov(o/i+1);
if((i-o%i)&1) xx^=sov(o/i);
mm[xx]=o,--i;
}
while(mm[sg[o]]==o) ++sg[o];
return sg[o];
}
int main()
{
t=rd(),f=rd();
memset(sg,-1,sizeof(sg));
while(t--)
{
int n=rd(),an=0;
while(n--) an^=sov(rd());
printf("%d ",an>0);
}
return 0;
}