[SDOI2016]硬币游戏

佚名 6年前 (2019-04-26) 随笔 1823人围观抢沙发百度已收录

题目

翻硬币游戏啊

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

首先对于这类游戏只要满足如下的规则，就可以用一种特殊的方式解决了

我们假定只能翻正面朝上的硬币

我们可以根据某些约束条件的翻硬币（一次反掉连续几个，或者具有某些特殊性质的），但是翻掉的硬币中最右边的那个比如是从正面反到反面
谁不能翻硬币了谁输

对于满足这样的特征的硬币游戏，我们有这样一个定理：局面的\(SG\)函数等于局面中每一个正面朝上的硬币单独存在的局面的\(SG\)函数的异或和

去论文里偷了一张图，大概就是这个样子

对于这个题我们能翻动的是反面朝上的硬币，所以我们求一下所有反面朝上的硬币但对存在的时候的\(SG\)函数，求一个异或和就好了

我们发现这个题硬币翻动情况，只和这个硬币的位置\(x\)分解成\(x=2^a\times 3^b\times c\)时候的\(a,b\)有关系

于是我们可以设\(sg[a][b]\)表示一枚位于\(=2^a\times 3^b\times c\)的硬币单独存在的\(SG\)函数值

于是我们按照题意模拟一下这个硬币能转移到的局面，取一个\(mex\)就好了

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read() {
    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
int T,n,M,m;
int sg[16][15],tax[100005];
inline void Pre() {
    sg[0][0]=0;
    for(re int a=0;a<=15;a++)
        for(re int b=0;b<=10;b++) {
            if(!a&&!b) continue;++m;
            for(re int p=1;p<=a;p++)
                for(re int q=1;q<=M&&p*q<=a;q++) {
                    int now=0;
                    for(re int j=0;j<=q;j++)
                        now^=sg[a-p*j][b];
                    tax[now]=m;
                }
            for(re int p=1;p<=b;p++)
                for(re int q=1;q<=M&&p*q<=b;q++) {
                    int now=0;
                    for(re int j=0;j<=q;j++)
                        now^=sg[a][b-p*j];
                    tax[now]=m;
                }
            while(tax[sg[a][b]]==m) sg[a][b]++;
        }
}
int main() {
    T=read();
    while(T--) {
        n=read(),M=read();memset(sg,0,sizeof(sg));Pre();
        int ans=0;
        for(re int x,i=1;i<=n;i++) {
            x=read();if(x) continue;
            int a=0,b=0;int pos=i;
            while(pos%2==0) pos/=2,a++;
            while(pos%3==0) pos/=3,b++;
            ans^=sg[a][b];
        }
        puts(ans?"win":"lose");
    }
    return 0;
}