[HNOI2014] 江南乐

题意：

考虑一个博弈游戏：有n堆石子，每堆$a_{i}$个。

给定一个数F，每次你可以选择一堆个数$geq F$的石子和一个数M，将这堆石子平分成M份（只有一种分法）。

最后不能操作的人输，问先手是否必胜。

$T,nleq 100,F,a_i leq 10^{5}$。

题解：

根据博弈论的常规套路，答案即为所有$SG(a_{i})$的异或和。

考虑暴力求SG函数值的过程，设当前堆石子有x个，分成m份，则每份的个数为$lfloor frac{x}{m} floor$或$lfloor frac{x}{m} floor +1$。

那么$SG(x)=SG(lfloor frac{x}{m} floor)oplus cdots oplus SG(lfloor frac{x}{m} floor) oplus SG(lfloor frac{x}{m} floor +1)oplus cdots oplus SG(lfloor frac{x}{m} floor +1)$。

根据异或的性质，当$x\%m$为奇数时$SG(lfloor frac{x}{m} floor +1)$有贡献，当$x-x\%m$为奇数时$SG(lfloor frac{x}{m} floor)$有贡献。

这样做可以满足每个局面的SG值只被计算一次，但可能被遍历$a_{max}$次，所以复杂度是$O(T{a_{max}}^{2})$的。

注意到假如$lfloor frac{x}{m} floor=lfloor frac{x}{m+2} floor$，那么分m份和m+2份的SG值是相同的。

而子局面的SG值只对求mex（最小的没出现过的非负整数）有用，所以完全可以不枚举分m+2份这个局面。

那么考虑整除分块，对每块只计算分m份和m+1份的SG值即可。

复杂度$O(T{a_{max}}sqrt{a_{max}})$。

套路：

• 博弈论基本定理：每个局面的SG值等于子局面SG值的mex，等于子问题SG值的异或和。
• 整除分块公式：设值域为m，则一块为$[x,lfloor frac{m}{lfloor frac{m}{x} floor} floor]$。

代码：

#include<bits/stdc++.h>
#define maxn 100005
#define maxm 500005
#define inf 0x7fffffff
#define ll long long
#define rint register int
#define debug(x) cerr<<#x<<": "<<x<<endl
#define fgx cerr<<"--------------"<<endl
#define dgx cerr<<"=============="<<endl

using namespace std;
int F,SG[maxn],mex[maxn];

inline int read(){
    int x=0,f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}

inline int dfs(int m){
    if(SG[m]!=-1) return SG[m];
    if(m<F) return (SG[m]=0);
    SG[m]=0; int res=0;
    for(rint i=2;i<=m;i=(m/(m/i)+1))
        for(rint j=i;j<=min((m/(m/i)),i+1);j++){
            res=0;
            if((m%j)&1) res^=dfs(m/j+1);
            if((j-(m%j))&1) res^=dfs(m/j);
            mex[res]=m;
        }
    while(mex[SG[m]]==m) SG[m]++;
    return SG[m];
}

int main(){
    //freopen("game8.in","r",stdin);
    //freopen("1.out","w",stdout);
    int T=read();F=read();
    for(rint i=1;i<=T;i++){
        memset(SG,-1,sizeof(SG));
        int n=read(),ans=0;
        for(rint j=1;j<=n;j++)
            {int x=read();ans^=dfs(x);}
        printf("%d ",(ans?1:0));
    }
    return 0;
}