题解 P4077 【[SDOI2016]硬币游戏】

winxp_qwq · 2019-02-23 17:41:32 · 题解

如果换成下面这个游戏，是不是一眼可以看出是SG啊

①开始有一些地方有石子

②每次可以选择满足条件的p,q和一个位置，在这个位置去掉一个石子，在其它相应位置加一个石子

注意到这个问题对每个数是独立的，应用SG定理就可以马上解决

那么回到原游戏，我们发现原游戏就是这个游戏mod2的形式

并且呢，如果某方在原游戏下有必胜策略，那么在新游戏中如果对方动了一个位置，且：

①如果这个位置原有奇数个棋子，那按原游戏里面必胜策略下就可以

②否则复读（显然可以复读，而且这样mod2来看都是不变的）

这是新游戏的一个必胜策略

那么容易证明这两个游戏的获胜条件是相同的

那是不是直接SG就好了啊

（注意看清题意，看清每次合法操作都是什么以防WA）

#include <bits/stdc++.h>
using namespace std;
#define maxn 33333
int n,q;
int sg[maxn];
int cnt[303]={0};
void gao(int x,int p,int w) {
    int a,b,c=0,y=x;
    for(a=1;a<=q;a++) {
        if(y%p!=0) break;
        y/=p;c^=sg[y];
        if(c<303) cnt[c]=x;
    }
}
void get_sg(int x) {
    int a,b,c;
    for(b=2,a=1;;a++) {
        if(x%b!=0) break;
        gao(x,b,a);
        b*=2;
    }
    for(b=3,a=1;;a++) {
        if(x%b!=0) break;
        gao(x,b,a);
        b*=3;
    }
    for(a=0;;a++)
    if(cnt[a]!=x) {
        sg[x]=a;
        return;
    }
}
int main(){
    int T,t;
    scanf("%d",&T);
    for(t=1;t<=T;t++) {
        int a,b,c=0;
        memset(cnt,0,sizeof cnt);
        scanf("%d%d",&n,&q);
        for(a=1;a<=n;a++) get_sg(a);
        //for(a=1;a<=n;a++) printf("%d\n",sg[a]);
        for(a=1;a<=n;a++) {
            scanf("%d",&b);
            if(b==0) c^=sg[a];
        }
        if(c==0) printf("lose\n");
        else printf("win\n");
    }
    return 0;
}