题解 P3339 【[ZJOI2014]取石子游戏】

· · 题解

这道题我搞了好久，找半天找不到题解，最后只有靠着贴吧里的那一个糊到不行的图，一点一点看清是哪个字来做，我把做法大意和代码放在下面，供各位参考，如果有大佬知道为什么请私信告诉我。

首先暴力SG

SG[x]=mex\{SG[x-i]\ xor\ SG[x-2i]\ xor...xor\ SG[x-ki]|x>=ki\}

然后通过不知道怎么样的做法发现以下结论

SG[x]=A_k[i]

其中i是将x变为k+1进制后从低往高遇到的一个k的位数，若没有则i=0

然后A_k满足

A_k[0]=0,A_k[x]=mex\{A_k[x_1]\ xor\ A_k[x_2]...\ xor\ A_k[x_k]|x_1,x_2...x_k<x\}

所以当我们求出A_k时原问题就解决了，接下来是如何求出A_k 一直当x<=k+1时A_k[x]=(2^{x-1}),当x=k+2时A_k[x]=2^{k+1}-1 因为前面的不能全选，所以不同，后面A_k[x]继续是2^i的形式， 但是没隔k/2个因为不能全部凑出所以会隔断一次，然后后面又继续(这里说的不是很清楚可以看代码)。下面是代码

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pint pair<ll,ll>
#define mk(x,y) make_pair(x,y)
#define fir first
#define sec second
#define Rep(x,y,z) for(ll x=y;x<=z;++x)
#define Red(x,y,z) for(ll x=y;x>=z;--x)
using namespace std;
char buf[1<<12],*p1=buf,*p2=buf,nc;ll ny;
//inline char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
inline char gc(){return getchar();}
inline ll read(){
    ll x=0;ny=1;while(nc=gc(),(nc<48||nc>57)&&nc!=EOF)if(nc==45)ny=-1;if(nc<0)return nc;
    x=nc-48;while(nc=gc(),47<nc&&nc<58&&nc!=EOF)x=(x<<3)+(x<<1)+(nc^48);return x*ny;
}struct BigInteger {
    typedef unsigned long long LL;

    static const int BASE = 100000000;
    static const int WIDTH = 8;
    vector<int> s;

    BigInteger& clean(){while(!s.back()&&s.size()>1)s.pop_back(); return *this;}
    BigInteger(LL num = 0) {*this = num;}
    BigInteger(string s) {*this = s;}
    BigInteger& operator = (long long num) {
        s.clear();
        do {
            s.push_back(num % BASE);
            num /= BASE;
        } while (num > 0);
        return *this;
    }
    BigInteger& operator = (const string& str) {
        s.clear();
        int x, len = (str.length() - 1) / WIDTH + 1;
        for (int i = 0; i < len; i++) {
            int end = str.length() - i*WIDTH;
            int start = max(0, end - WIDTH);
            sscanf(str.substr(start,end-start).c_str(), "%d", &x);
            s.push_back(x);
        }
        return (*this).clean();
    }

    BigInteger operator + (const BigInteger& b) const {
        BigInteger c; c.s.clear();
        for (int i = 0, g = 0; ; i++) {
            if (g == 0 && i >= s.size() && i >= b.s.size()) break;
            int x = g;
            if (i < s.size()) x += s[i];
            if (i < b.s.size()) x += b.s[i];
            c.s.push_back(x % BASE);
            g = x / BASE;
        }
        return c;
    }
    BigInteger operator - (const BigInteger& b) const {
        assert(b <= *this); 
        BigInteger c; c.s.clear();
        for (int i = 0, g = 0; ; i++) {
            if (g == 0 && i >= s.size() && i >= b.s.size()) break;
            int x = s[i] + g;
            if (i < b.s.size()) x -= b.s[i];
            if (x < 0) {g = -1; x += BASE;} else g = 0;
            c.s.push_back(x);
        }
        return c.clean();
    }
    BigInteger operator * (const BigInteger& b) const {
        int i, j; LL g;
        vector<LL> v(s.size()+b.s.size(), 0);
        BigInteger c; c.s.clear();
        for(i=0;i<s.size();i++) for(j=0;j<b.s.size();j++) v[i+j]+=LL(s[i])*b.s[j];
        for (i = 0, g = 0; ; i++) {
            if (g ==0 && i >= v.size()) break;
            LL x = v[i] + g;
            c.s.push_back(x % BASE);
            g = x / BASE;
        }
        return c.clean();
    }
    BigInteger operator / (const BigInteger& b) const {
        assert(b > 0);  
        BigInteger c = *this;       
        BigInteger m;               
        for (int i = s.size()-1; i >= 0; i--) {
            m = m*BASE + s[i];
            c.s[i] = bsearch(b, m);
            m -= b*c.s[i];
        }
        return c.clean();
    }
    BigInteger operator % (const BigInteger& b) const { 
        BigInteger c = *this;
        BigInteger m;
        for (int i = s.size()-1; i >= 0; i--) {
            m = m*BASE + s[i];
            c.s[i] = bsearch(b, m);
            m -= b*c.s[i];
        }
        return m;
    }
    int bsearch(const BigInteger& b, const BigInteger& m) const{
        int L = 0, R = BASE-1, x;
        while (1) {
            x = (L+R)>>1;
            if (b*x<=m) {if (b*(x+1)>m) return x; else L = x;}
            else R = x;
        }
    }
    BigInteger& operator += (const BigInteger& b) {*this = *this + b; return *this;}
    BigInteger& operator -= (const BigInteger& b) {*this = *this - b; return *this;}
    BigInteger& operator *= (const BigInteger& b) {*this = *this * b; return *this;}
    BigInteger& operator /= (const BigInteger& b) {*this = *this / b; return *this;}
    BigInteger& operator %= (const BigInteger& b) {*this = *this % b; return *this;}

    bool operator < (const BigInteger& b) const {
        if (s.size() != b.s.size()) return s.size() < b.s.size();
        for (int i = s.size()-1; i >= 0; i--)
            if (s[i] != b.s[i]) return s[i] < b.s[i];
        return false;
    }
    bool operator >(const BigInteger& b) const{return b < *this;}
    bool operator<=(const BigInteger& b) const{return !(b < *this);}
    bool operator>=(const BigInteger& b) const{return !(*this < b);}
    bool operator!=(const BigInteger& b) const{return b < *this || *this < b;}
    bool operator==(const BigInteger& b) const{return !(b < *this) && !(b > *this);}
};
ostream& operator << (ostream& out, const BigInteger& x) {
    out << x.s.back();
    for (int i = x.s.size()-2; i >= 0; i--) {
        char buf[20];
        sprintf(buf, "%08d", x.s[i]);
        for (int j = 0; j < strlen(buf); j++) out << buf[j];
    }
    return out;
}
istream& operator >> (istream& in, BigInteger& x) {
    string s;
    if (!(in >> s)) return in;
    x = s;
    return in;
}
ll A2[70],A10[25],vis[1050],A30[60];
inline void pre(){
    ll t=0;
    Rep(i,1,1024){
        vis[i]=(vis[i>>1]^(i&1));
        if(vis[i])A2[++t]=i;
    }Rep(i,0,10)A10[i]=1<<i;Rep(i,12,16)A10[i]=1<<i-1;Rep(i,18,19)A10[i]=1<<i-2;
    A10[11]=(1<<11)-1,A10[17]=(1<<16)-(1<<11)+(1<<6)-1;
    Red(i,20,1)A10[i]=A10[i-1];A10[0]=0;
    Rep(i,0,30)A30[i]=1<<i;Rep(i,32,46)A30[i]=1ll<<i-1;Rep(i,48,54)A30[i]=1ll<<i-2;
    A30[31]=(1ll<<31)-1,A30[47]=(1ll<<46)-(1ll<<31)+(1<<16)-1;
    Red(i,55,1)A30[i]=A30[i-1];A30[0]=0;
}ll n,k;
inline ll Get(){
    ll x=read();
    for(ll cnt=1;x;x/=k+1,cnt++)if(x%(k+1)==k)return cnt;
    return 0;
}inline ll GetB(){
    BigInteger x;cin>>x;
    for(ll cnt=1;x!=0;x/=k+1,cnt++)if(x%(k+1)==k)return cnt;
    return 0;
}
inline void Solve1(){
    ll tot=0;
    Rep(i,1,n)tot^=read();
    if(tot)puts("Preempt.");else puts("Leapfrog.");
}inline void Solve2(){
    ll tot=0;
    Rep(i,1,n)tot^=A2[Get()];
    if(tot)puts("Preempt.");else puts("Leapfrog.");
}inline void Solve10(){
    ll tot=0;
    Rep(i,1,n)tot^=A10[Get()];
    if(tot)puts("Preempt.");else puts("Leapfrog.");
}inline void Solve30(){
    ll tot=0;
    Rep(i,1,n)tot^=A30[GetB()];
    if(tot)puts("Preempt.");else puts("Leapfrog.");
}
int main(){
//  freopen("std.in","r",stdin);
//  freopen("std.out","w",stdout);
    pre();
    for(ll t=read();t--;){
        n=read(),k=read();
        if(k==1)Solve1();
        else if(k==2)Solve2();
        else if(k==10)Solve10();
        else if(k==30)Solve30();
    }
    return 0;
}