Description
Alice和Bob正在玩一个非常无聊的游戏以打发时间。游戏是这样的。初始的时候，有n个箱子和m个物品。箱子、物
品都是不同的。因此有nm种方法把这些物品放到箱子里。两个人轮流操作。每一次操作，游戏者有两种选择：添加
一个新的箱子或者添加一个新的物品。不可以不操作。如果某人操作以后，将物品放入箱子的方法数大于或等于c
，那么这个人就输了。保证最初c > nm。对于一组给定的n和m，假设游戏者足够聪明，请问是先手必胜，还是后手
必胜，还是平局（即无人能获胜）呢？注意，输入文件包含多组测试数据。
Input
第一行包含一个整数T，表示有T组测试数据。
接下来T行，每行包含三个整数n，m，c。
1≤n < c，1≤m≤30，2≤c≤109，1≤T≤5
Output
输出T行，依次表示每组测试数据的答案。若先手必胜输出"Alice"，后手必胜输出"Bob"，平局输出"Draw"。
有效状态数非常少，可以记忆化搜索或dp
若n=1，m足够大使2^m>=c，则游戏不会结束，故为平局
若m=1,n足够大使n^2>=c，则可以直接判定胜负
一个状态为必胜态，当且仅当存在一个后继状态为必败态，一个状态为必败态，当且仅当没有后继或所有后继为必胜态，否则为平局状态
#include<cstdio> #include<map> #include<algorithm> typedef long long i64; int T,n,m,c; std::map<std::pair<int,int>,int>mp; bool chk(i64 a,int b){ i64 v=1; for(;b&&v<c;b>>=1){ if(b&1)v=v*a; a=a*a; } return v<c; } int calc(int a,int b){ if(!chk(a,b))return 2; if(a==1&&(1ll<<b)>=c)return 1; if(b==1&&i64(a)*a>=c)return ((c-a+1&1)<<1); std::pair<int,int>st=std::make_pair(a,b); if(mp.find(st)!=mp.end())return mp[st]; int x=calc(a+1,b),y=calc(a,b+1); if(!x||!y)return mp[st]=2; if(x==2&&y==2)return mp[st]=0; return mp[st]=1; } int main(){ for(scanf("%d",&T);T;--T){ scanf("%d%d%d",&n,&m,&c); mp.clear(); int w=calc(n,m); puts(w==0?"Bob":w==1?"Draw":"Alice"); } return 0; }