题解 P1839 【Play with Power_NOI导刊2011提高（05）】

· · 题解

这么有趣的一道题居然没人发题解？

乍一看是博弈论......

注意到N<=10^8,那么当Ai不小于2时2人轮流操作，最多30来次(log₂(n)).

所以我们很容易想到类似于dp的思想，好吧其实是记忆化搜索...

设f(a,b)表示当前值a,b的状态，f(a,b)=0表示必败,=1表示平局,=2表示必胜，则f(a,b)的值可以由f(a+1,b)和f(a,b+1)推过来。

即：对于f(a,b)：

方便起见，设n1=f(a+1,b),n2=f(a,b+1).

1. n1=n2=2.......==>f(a,b)=0;

2. n1=0或n2=0..==>f(a,b)=2;

3. 其余情况..........==>f(a,b)=1.

还有，毕竟是记忆化搜索，得另开一个数组g[i][j]表示i^j，当i^j>n是g[i][j]=-1.

然而没有那么那么简单

注意点：

1. 保险一点（我也没试过）最好开long long；

2. 用快速幂(不要告诉我你没想到要用快速幂)求幂的过程中还会超long long，其实是超n，此时应直接返回-1，不然会超范围；

3. 但是还是会超long long......

....极限数据：当a=1或b=1时会出现死循环或是爆long long，具体解决方法见代码

4. 右上角点个赞谢谢~

附上丑陋的 c++代码

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cmath>
#define ll long long
using namespace std;
ll rd(){ll x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();
    return x;
}   //毫无用处的读优...
ll n=rd(),t=rd(),a,b,g[35][10005];
int c;
ll max(ll a,ll b){return a>b?a:b;}
ll p(ll a,ll x){ll ans=1;
    if(a>n) return -1;//不判的话可能一乘就炸了...
    while(x){
        if(x&1) ans*=a;
        a*=a,x>>=1;
        if(ans>n) return -1;
    }
    return ans;
}    //快速幂
inline int f(ll a,ll b){
    if(b>30) return 1;//对于a=1,如果直接判a是否为1,那在第一次调用f时会返回错误的答案1，另外，先手可以通过使a+1来让后手输
    if(!g[b][a]) g[b][a]=p(a,b);//试过删掉g，好像T掉了...
    if(!~g[b][a]) return 2;//~就是!=-1，下同
    int n1=f(a+1,b),n2=f(a,b+1);
    if(n1==2&&n2==2) return 0;//n1=n2=2
    if(!n1||!n2) return 2;//n1=0或n2=0
    return 1;//其余情况
}
int main(){
    double ss=sqrt(n);
    while(t--){
        a=rd(),b=rd();
        if(a>ss) c=b==1?(n-a&1?2:0):0;//对于特别大的a，快速幂中乘一次就没了...所以在p之前要先进行判断
        else c=!~p(a,b)?0:f(a,b);//a^b>n,必输（额，好像题目中说了不会的...O__O）
        switch(c){
            case 0:printf("Stas\n"); break;
            case 1:printf("Missing\n"); break;
            case 2:printf("Masha\n"); break;
        }
    }
    return 0;
}

提前祝大家：

╭┘└┘└╮

└┐．．┌┘────╮

╭┴──┤ ├╮

│ｏｏ│ │ ●

╰─┬─╯ │

HAPPY 牛 YEAR

——蒟蒻:Je