题解 P5635 【【CSGRound1】天下第一】
Eason_AC
·
·
题解
标签里面说要记忆化搜索？
个人感觉其实没有必要，只需要稍微带一点小技巧的搜索就可以过了。
因为不能决出胜负的局肯定到最后会进入死循环，所以我们可以限制搜索的层数（就是说达到一定的层数就干脆不搜了，直接跳出搜索），然后就是平常地搜索就行了。
```cpp
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
int x, y, mod, t;
int dfs(int x, int y, int dep) {
if(dep > 10000) return 0;
if(!x) return 1;
if(!y) return 2;
// printf("%d\n", dep);
if(dep % 2) return dfs((x + y) % mod, y, dep + 1);
return dfs(x, (x + y) % mod, dep + 1);
}
int main() {
scanf("%d%d", &t, &mod);
while(t--) {
scanf("%d%d", &x, &y);
if(!dfs(x, y, 1)) puts("error");
else printf("%d\n", dfs(x, y, 1));
}
return 0;
}
```