题目地址：https://www.luogu.com.cn/problem/P3235
题目意思是这样的：
给定(n)堆石子，每次操作选择一堆石子数目(x)((x>=f))，把它分成(m)堆((2<=m<=x))，分出来的每一堆中石子数目最大值和最小值相差不超过(1)（也就是均分的意思），问你先手是否必胜。
其实这个问题可以转化成(n)个子问题，每一个子问题都只对一堆石子进行操作。
然后就可以转化成(SG)函数的问题了。
SG定理：(SG=SG(a_1) igoplus SG(a_2) igoplus SG(a_3)... igoplus SG(a_n))，及总问题的SG值为分问题的SG值的异或和，本文就不进行证明了。
想法1
考虑到(x)的(SG)值只跟(f)有关，题目在最开始已经把(f)告诉我们了，我们可以考虑预处理。
我们用枚举每个(x)分成的石子堆数(m)((2<=m<=x))，将这(m)堆石子的(SG)异或起来，然后对于所有的(m)的异或和取(mex)。
这显然是(O(x^2))的做法，会直接TLE。
所以我们不能预处理，我们就想到了记忆化搜索。
想法2
受到想法1的启发，我们可以枚举(m)，然后异或和取(mex)，这不过这一次我们不预处理出(SG)值，而是边暴力递归边存(SG)值，遇到已经算过的(SG)值直接返回即可。
那么如何计算异或和呢？
我们用到异或的一个性质(x igoplus x=0)
看到下面这张图
我们发现把(x)分成(m)份的异或和只有可能是(0,SG(x/m),SG(x/m+1),SG(x/m) igoplus SG(x/m+1))
那么接下来该如何计算(mex)值呢
我们每一次算完异或和以后，用一个数字打上一个特殊的标记，然后最后统计(mex)值的时候找到第一个没有这种标记的值即可
然后我们就可以拿到了70分（TLE30）
#include<bits/stdc++.h>
using namespace std;
int T,F,sg[200000];
int n,a,po[200000],q=0;
int SG(int x,int pos)
{
if(sg[x]>-1)return q--,sg[x];//已经算出来过
if(x<F)return q--,0;//不可再分
sg[x]=0;
for(int i=2;i<=x;i++)//计算异或和
{
int x1=x/i,x2=x/i+1,n2=x-x1*i,n1=i-n2;//计算分出来的两个值和两个值所占的数量
if(n1%2==0&&n2%2==1)po[SG(x2,++q)]=pos;
if(n1%2==0&&n2%2==0)po[0]=pos;
if(n1%2==1&&n2%2==1)po[SG(x2,++q)^SG(x1,++q)]=pos;
if(n1%2==1&&n2%2==0)po[SG(x1,++q)]=pos;
}
int pp=0;
while(po[pp]==pos)pp++;//计算mex值
return sg[x]=pp;
}
int main()
{
scanf("%d%d",&T,&F);
if(F==1)sg[1]=0;
memset(sg,-1,sizeof(sg));
while(T--)
{
memset(po,0,sizeof(po));
scanf("%d",&n);
int res=0;//res是总的SG值
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
res^=SG(a,++q);
}
if(res==0)printf("0 ");
else printf("1 ");
}
return 0;
}
想法3
我们可以观察到其实同一个(x)分成(m)份时会出现(t)和(t+1)两个值，我们可以把分出来的(t)和(t+1)都相同的(m)一起算，此时答案只有可能是(SG(t),SG(t) igoplus SG(t+1))两种，而且存在一定的奇偶关系
我们可以发现，同一个t和t+1,m0与m0+2的答案是一样的，因此我们可以枚举t,然后算出对应的前两个m即可
可以看下面这个图，尤其是1和2的蓝色部分，规律非常明显
AC Code
#include<bits/stdc++.h>
using namespace std;
int T,F,sg[200000];
int n,a,po[200000],q=0;
int SG(int x,int pos)
{
if(sg[x]>-1)return q--,sg[x];
if(x<F)return q--,0;
sg[x]=0;
int i=2;
while(i<=x)
{
if((x/i)==(x/(i-1))&&(x/i)==(x/(i-2)))i=(x/(x/i));//算完前两个后跳过
int x1=x/i,x2=x/i+1,n2=x-x1*i,n1=i-n2;
if(n1%2==0&&n2%2==1)po[SG(x2,++q)]=pos;
if(n1%2==0&&n2%2==0)po[0]=pos;
if(n1%2==1&&n2%2==1)po[SG(x2,++q)^SG(x1,++q)]=pos;
if(n1%2==1&&n2%2==0)po[SG(x1,++q)]=pos;
i++;
}
int pp=0;
while(po[pp]==pos)pp++;
return sg[x]=pp;
}
int main()
{
scanf("%d%d",&T,&F);
if(F==1)sg[1]=0;
memset(sg,-1,sizeof(sg));
while(T--)
{
memset(po,0,sizeof(po));
scanf("%d",&n);
int res=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
res^=SG(a,++q);
}
if(res==0)printf("0 ");
else printf("1 ");
}
return 0;
}