题解：P1839 Play with Power
cccz
·
·
题解
我的思路和大佬差不多，也是记忆化搜索。
$f(a + 1,b)$ 和 $f(a,b + 1)$ 表示下一个人胜负情况，若两个均胜，则本次先手的人必输，若有至少一个为负，因为是最优策略，则本次必胜。
当 $a = 1$ 时，因为 $a$ 的任何次幂都为 $1$，所以两个人会无限的执行 $b + 1$，只能平局。
当 $a = 2$ 时，如果 $b > 27,a^b$ 超过 $n$ 最大值，也要判断一下。
希望上述内容可以帮助大家理解。
最后，献上蒟蒻的代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
string s;
int n,t,a,b;
int ans[114514][30];
int dfs(int x,int y){
if(x==1&&y>27){
return 3;// 当b>27时，2^27>1e8，所以只能加b，但是1的任何次幂都是1，所以只能平局
}
if(y==1&&x>n/x){
return ((n-x)&1)?1:2;//当b=1时，若a^2>n，则只能a+1，若n-a为偶数，则 S胜，反之M胜 。
}
if(ans[x][y]){
return ans[x][y];//已经有了这个状态，直接返回即可 。
}
if(n<pow(x,y)){
return 1;
}
int xx=dfs(x+1,y),yy=dfs(x,y+1); //题解里面已经说了。
if(xx==1&&yy==1){
return ans[x][y]=2;
}else if(xx==2||yy==2){
return ans[x][y]=1;
}else{
return ans[x][y]=3;
}
}
signed main(){
cin>>n>>t;
ans[1][27]=3;
for(int i=1;i<=t;i++){
scanf("%d%d",&a,&b);
int temp=dfs(a,b);
if(temp==1){
printf("Masha\n");
}else if(temp==2){
printf("Stas\n");
}else if(temp==3){
printf("Missing\n");
}
}
return 0;
}
```