自动搬运

查看原文

来自洛谷，原作者为

	winxp_qwq 退役菜鸡

搬运于2025-08-24 21:56:14，当前版本为作者最后更新于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;
}