CF1739C Card Game

考虑一个有 $n$ 张牌的游戏（$n$ 是偶数）。每张牌上都写有一个数字，数字范围在 $1$ 到 $n$ 之间。所有牌上的数字都不相同。我们称，若一张牌上的数字 $x$ 大于另一张牌上的数字 $y$，则 $x$ 这张牌比 $y$ 这张牌“强”。 有两名玩家，Alex 和 Boris，进行此游戏。开始时，他们每人各获得恰好 $\frac{n}{2}$ 张牌，因此每张牌只属于其中一名玩家。然后，他们轮流出牌。Alex 先手，然后是 Boris，再然后又轮到 Alex，如此交替进行。 在玩家的回合，他必须打出自己手中的一张牌。然后，如果对手没有比这张牌更强的牌，则对手输掉比赛，游戏结束。否则，对手必须用一张更强的牌应对（同样只能出一张牌）。这两张牌都从游戏中移除，回合结束。如果双方都没有牌了，游戏以平局结束；否则轮到对手出牌。 请考虑所有可能的分牌方式，使得每人各获得一半的牌。你需要计算三个数： - 能让 Alex 获胜的分牌方式数； - 能让 Boris 获胜的分牌方式数； - 能让游戏以平局结束的分牌方式数。 你可以假设两位玩家都会采取最优策略（即如果某位玩家无论对手如何应对都能获胜，则他会获胜）。如果某种分牌方式下，至少有一张牌在 Alex 和 Boris 的归属不同，则认为这两种分牌方式不同。 例如，假设 $n=4$，Alex 得到的牌为 $[2, 3]$，Boris 得到的牌为 $[1, 4]$。那么游戏可能如下进行： - 如果 Alex 打出 $2$，Boris 必须用 $4$ 应对。然后轮到 Boris，他只剩 $1$，打出后，Alex 用 $3$ 应对。游戏以平局结束； - 如果 Alex 打出 $3$，Boris 仍然必须用 $4$ 应对。然后轮到 Boris，他只剩 $1$，打出后，Alex 用 $2$ 应对。游戏以平局结束。 所以在这种情况下，游戏以平局结束。

第一行包含一个整数 $t$（$1 \le t \le 30$），表示测试用例的数量。 接下来有 $t$ 行，第 $i$ 行包含一个偶数 $n$（$2 \le n \le 60$）。

对于每个测试用例，输出三个整数： - 能让 Alex 获胜的分牌方式数； - 能让 Boris 获胜的分牌方式数； - 能让游戏以平局结束的分牌方式数。 由于答案可能很大，请对 $998244353$ 取模后输出。

在第一个测试用例中，如果 Alex 得到 $2$ 号牌（他打出后，Boris 无法应对），则 Alex 获胜。如果 Alex 得到 $1$ 号牌，则游戏以平局结束。 在第二个测试用例中： - 如果 Alex 得到 $[3, 4]$、$[2, 4]$ 或 $[1, 4]$，则 Alex 获胜； - 如果 Alex 得到 $[1, 2]$ 或 $[1, 3]$，则 Boris 获胜； - 如果 Alex 得到 $[2, 3]$，则游戏以平局结束。 由 ChatGPT 4.1 翻译