题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3576
很显然，这是一个multi-nim游戏。
注意：1.一个点的SG值就是一个不等于它的后继点的SG的且大于等于零的最小整数。(mex)
2.主游戏的SG值等于所有子游戏的异或和
所以区分好主游戏和后继点的区别。
一开始多个石子堆组合起来形成了一个主游戏。
一个石子堆可以分为多个石子堆，每一种分发构成了一个主游戏，这些主游戏的异或和构成的当前这个点(状态)的SG函数。
显然有一个${m^{2}}$做法，即记忆化搜索SG函数。
考虑${x/i}$只有$\sqrt{n}$种取值，再考虑一下它们的奇偶性，然后分块来做。
70Code:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
#define maxn 100100
#define llg long long
#define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
llg n,m,bj[maxn],sg[maxn],T,F,a[maxn]; llg dp(llg x)
{
if (bj[x]) return sg[x];
bj[x]=;
sg[x]=;
bool e[maxn];
memset(e,,sizeof(e));
for (llg m=;m<=x;m++)
{
llg v1=m-x%m,v2=x%m;
llg nsg=;
if (v1&) nsg^=dp(x/m);
if (v2&) nsg^=dp(x/m+);
e[nsg]=;
}
for (llg i=;;i++) if (!e[i]) {sg[x]=i; return sg[x];}
} int main()
{
yyj("game");
cin>>T>>F;
for (llg i=;i<F;i++) bj[i]=;
while (T--)
{
scanf("%lld",&n);
llg ans=;
for (llg i=;i<=n;i++)
{
scanf("%lld",&a[i]);
ans^=dp(a[i]);
}
if (ans) printf("");else printf("");
if (T) printf(" ");
}
return ;
}
100Code:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
#define maxn 100100
#define llg int
#define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
llg n,m,bj[maxn],sg[maxn],T,F,a[maxn]; llg dp(llg x)
{
if (bj[x]) return sg[x];
bj[x]=;
sg[x]=;
bool e[maxn];
memset(e,,sizeof(e));
for (llg m=,j=;m<=x;m=j+)
{
j=x/(x/m);
llg v1=m-x%m,v2=x%m,cnt=j-m+;
llg nsg=;
if (v1&) nsg^=dp(x/m);
if (v2&) nsg^=dp(x/m+);
e[nsg]=;
if (cnt>=)
{
nsg=;
if (((m+)-x%(m+))&) nsg^=dp(x/(m+));
if ((x%(m+))&) nsg^=dp(x/(m+)+);
e[nsg]=;
}
}
for (llg i=;;i++) if (!e[i]) {sg[x]=i; return sg[x];}
} int main()
{
yyj("game");
cin>>T>>F;
for (llg i=;i<F;i++) bj[i]=;
while (T--)
{
scanf("%d",&n);
llg ans=;
for (llg i=;i<=n;i++)
{
scanf("%d",&a[i]);
ans^=dp(a[i]);
}
if (ans) printf("");else printf("");
if (T) printf(" ");
}
return ;
}