天下第一

P5635 【CSGRound1】天下第一 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

• 误区：第一次记录用的数组开三层，分别表示x，y，和第几回合的最终答案（分别代表谁赢），但空间始终过大了
• 第三层可以不用，因为对于某两个连续的回合（1，2     3，4）只可能有一个能赢，所以完全不需要第三层
• 对于平局的处理：每次dfs进去之间先把ans数组标记，如果又回到相同的x，y值，那么代表这个比赛是一直循环没有结果的直接返回平局
• 其他就按记忆化搜索做，有答案直接返回答案，没答案就先判断是不是到比赛终点了，如果是就标记输出，不是就按题目要求处理再往dfs递归

#include <bits/stdc++.h>
using namespace std;
#define MAX 10001
int t, mod;
short ans[MAX][MAX];
short dfs(int x, int y)
{
    if (ans[x][y] == -1)
    {
        printf("error/n");
        return -1;
    }
    if (ans[x][y])
    {
        printf("%d", ans[x][y]);
        return ans[x][y];
    }
    if (x == 0)
    {
        printf("1/n");
        ans[x][y] = 1;
        return 1;
    }
    else if (y == 0)
    {
        printf("2/n");
        ans[x][y] = 2;
        return 2;
    }
    ans[x][y] = -1;
    ans[x][y] = dfs((x + y) % mod, ((x + y) % mod + y) % mod);
    return ans[x][y];
}
int main()
{
    cin >> t >> mod;
    int x, y;
    while (t--)
    {
        ans[x][y] = -1;
        scanf("%d%d", &x, &y);
        ans[x][y] = dfs(x, y);
    }
}