题目
题解
明显的$Multi-SG$游戏，可以枚举堆数然后判断各种大小堆的个数的奇偶性，这样复杂度是$O({\max(a_i)}^2)$的
发现讨论各种大小的堆的个数没有意义，因为只会有两种堆的大小
最小堆的大小在枚举堆数的时候是类似一个整除分块，某些堆数的最小堆大小可能一样，这样可以分最小堆个数为奇数和偶数讨论
预处理跑不过……只能记忆化搜索
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=1e5+5;
int T,n,F,Mx=-1,mx;
int a[MAX],sg[MAX],use[MAX];
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
int SG(int x)
{
if(sg[x]!=-1) return sg[x];
for(int l=2,r;l<=x;l=r+1)
{
r=x/(x/l);
for(int i=l,N,o,k;i<=min(l+1,r);++i)
{
N=x/i;
if(N*i==x) o=(i&1)?SG(N):0;
else k=x-N*i,o=((k&1)?SG(N+1):0)^((i-k&1)?SG(N):0);
use[o]=x;
}
}
for(int j=0;;++j)
if(use[j]!=x) return sg[x]=j;
}
int main()
{
T=read(),F=read();
memset(sg,-1,sizeof(sg));
for(int i=0;i<F;++i)
sg[i]=0;
while(T--)
{
n=read();
int x=0;
for(int i=1;i<=n;++i)
x^=SG(read());
x?printf("1 "):printf("0 ");
}
return 0;
}
