题目

LOJ链接

思路

首先认识到:对于好几堆石子来说,它们总的SG值等于每一个石子的SG值的亦或和。

证明:

参见: 浅谈算法——博弈论(从零开始的博弈论)

对于每一个需要求SG值的\(x\)

首先考虑70分的暴力写法:
可以直接暴力求SG

void GetSG(int n,int f){
    for(int i=f;i<=n;i++){
        memset(mark,0,sizeof(mark));
        for(int j=2;j<=i;j++){
            int t=i/j,d=i%j;
            int tmp=0;
            if(d&1)tmp^=sg[t+1];
            if((j-d)&1)tmp^=sg[t];
            mark[tmp]=1;
        }
        while(mark[sg[i]])sg[i]++;
    }
}
//code from WangZY

然后考虑优化:

考虑两个性质:

  1. \(\lfloor\frac{n}{i}\rfloor\)的取值最多只有\(2*\sqrt{n}\)

  2. \(\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{i+2}\rfloor​\)的时候,两个数的SG值一定相同。

证明:

对于1,显然成立(请读者自行证明)

对于2。

观察代码:

 if(d&1)tmp^=sg[t+1];
 if((j-d)&1)tmp^=sg[t];

它们的区别仅仅在于奇偶性,所以由于\(i\)\(i+2\)的奇偶性相同,所以它们在这段代码中的if执行情况是一致的。

这样我们就可以确定解法,枚举\(\lfloor\frac{n}{i}\rfloor\)的值,然后奇偶讨论,这样的复杂度是\(O(n\sqrt{n})\)的。

代码

#include<bits/stdc++.h>
#define M 100005
using namespace std;
int n,F;
int sg[M];
namespace P70{
    bool mark[M];
    void GetSG(int n,int f){
        for(int i=f;i<=n;i++){
            memset(mark,0,sizeof(mark));
            for(int j=2;j<=i;j++){
                int t=i/j,d=i%j;
                int tmp=0;
                if(d&1)tmp^=sg[t+1];
                if((j-d)&1)tmp^=sg[t];
                mark[tmp]=1;
            }
            while(mark[sg[i]])sg[i]++;
        }
    }
    void solve(){
        GetSG(1000,F);
        for(int i=1,m;i<=n;i++){
            scanf("%d",&m);
            int ans=0,t;
            while(m--)
                ans^=sg[(scanf("%d",&t)*t)];
            printf("%d%c",ans>0," \n"[i==n]);
        }
        
    }
}
namespace P100{
    int Getsg(int x){
        if(sg[x]!=-1)return sg[x];
        bool mark[x+1];
        memset(mark,0,sizeof(mark));
        for(int i=2;i<=x;i=x/(x/i)+1)
            for(int j=i;j<=i+1&&j<=x;j++){
                int t=x/j,d=x%j,res=0;
                if(d&1)res^=Getsg(t+1);
                if((j-d)&1)res^=Getsg(t);
                mark[res]=1;
            }
        sg[x]=0;
        while(mark[sg[x]])sg[x]++;
        return sg[x];
    }
    void solve(){
        memset(sg,-1,sizeof(sg));
        for(int i=0;i<F;i++)sg[i]=0;
        for(int i=1,m,t;i<=n;i++){
            scanf("%d",&m);
            int res=0;
            while(m--)res^=Getsg(scanf("%d",&t)*t);
            printf("%d%c",res>0," \n"[i==n]);
        }
    }
}
int main(){
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    scanf("%d%d",&n,&F);
    F=max(F,2);
    P100::solve();
    return 0;
}
//code from WangZY