Card Game

题意翻译

有 $n$ 张卡牌，每张卡牌上写了 $[1,n]$ 中的一个整数，卡牌上的数字互不相同。 Alex 和 Boris 在玩游戏，每人有 $n\over 2$ 张卡牌，有 $n\over 2$ 轮。第一轮 Alex 先出牌，第二轮 Boris 先出牌，以此类推。 在一轮中，若先手出的牌上写的数为 $x$，则后手必须出一张比 $x$ 大的牌，如果没有则后手失败。双方都出完了牌则是平局。 假设两人都绝顶聪明，求所有分配牌的方案中，Alex 获胜、Boris 获胜和平局的方案数。

题目描述

Consider a game with $ n $ cards ( $ n $ is even). Each card has a number written on it, between $ 1 $ and $ n $ . All numbers on the cards are different. We say that a card with number $ x $ is stronger than a card with number $ y $ if $ x > y $ . Two players, Alex and Boris, play this game. In the beginning, each of them receives exactly $ \frac{n}{2} $ cards, so each card belongs to exactly one player. Then, they take turns. Alex goes first, then Boris, then Alex again, and so on. On a player's turn, he must play exactly one of his cards. Then, if the opponent doesn't have any cards stronger than the card played, the opponent loses, and the game ends. Otherwise, the opponent has to play a stronger card (exactly one card as well). These two cards are removed from the game, and the turn ends. If there are no cards left, the game ends in a draw; otherwise it's the opponent's turn. Consider all possible ways to distribute the cards between two players, so that each of them receives exactly half of the cards. You have to calculate three numbers: - the number of ways to distribute the cards so that Alex wins; - the number of ways to distribute the cards so that Boris wins; - the number of ways to distribute the cards so that the game ends in a draw. You may assume that both players play optimally (i. e. if a player can win no matter how his opponent plays, he wins). Two ways to distribute the cards are different if there is at least one card such that, in one of these ways, it is given to Alex, and in the other way, it is given to Boris. For example, suppose $ n = 4 $ , Alex receives the cards $ [2, 3] $ , and Boris receives the cards $ [1, 4] $ . Then the game may go as follows: - if Alex plays the card $ 2 $ , then Boris has to respond with the card $ 4 $ . Then, Alex's turn ends, and Boris' turn starts. Boris has only one card left, which is $ 1 $ ; he plays it, and Alex responds with the card $ 3 $ . So, the game ends in a draw; - if Alex plays the card $ 3 $ , then Boris has to respond with the card $ 4 $ . Then, Alex's turn ends, and Boris' turn starts. Boris has only one card left, which is $ 1 $ ; he plays it, and Alex responds with the card $ 2 $ . So, the game ends in a draw. So, in this case, the game ends in a draw.

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1 \le t \le 30 $ ) — the number of test cases. Then, $ t $ lines follow. The $ i $ -th line contains one even integer $ n $ ( $ 2 \le n \le 60 $ ).

输出格式

For each test case, print three integers: - the number of ways to distribute the cards so that Alex wins; - the number of ways to distribute the cards so that Boris wins; - the number of ways to distribute the cards so that the game ends in a draw. Since the answers can be large, print them modulo $ 998244353 $ .

输入输出样例

输入样例 #1

5
2
4
6
8
60

输出样例 #1

1 0 1
3 2 1
12 7 1
42 27 1
341102826 248150916 1

说明

In the first test case, Alex wins if he receives the card $ 2 $ (he plays it, and Boris cannot respond). If Alex receives the card $ 1 $ , the game ends in a draw. In the second test case: - Alex wins if he receives the cards $ [3, 4] $ , $ [2, 4] $ or $ [1, 4] $ ; - Boris wins if Alex receives the cards $ [1, 2] $ or $ [1, 3] $ ; - the game ends in a draw if Alex receives the cards $ [2, 3] $ .

**题意翻译**

有 $ n $ 张卡牌，每张卡牌上写了 $[1,n]$ 中的一个整数，卡牌上的数字互不相同。

Alex 和 Boris 在玩游戏，每人有 $ \frac{n}{2} $ 张卡牌，有 $ \frac{n}{2} $ 轮。第一轮 Alex 先出牌，第二轮 Boris 先出牌，以此类推。

在一轮中，若先手出的牌上写的数为 $ x $，则后手必须出一张比 $ x $ 大的牌，如果没有则后手失败。双方都出完了牌则是平局。

假设两人都绝顶聪明，求所有分配牌的方案中，Alex 获胜、Boris 获胜和平局的方案数。

**题目描述**

考虑一个游戏，有 $ n $ 张卡牌（$ n $ 是偶数）。每张卡牌上写着一个在 $ 1 $ 和 $ n $ 之间的数字。所有卡牌上的数字都不相同。如果一张卡牌上的数字 $ x $ 大于另一张卡牌上的数字 $ y $，我们说数字 $ x $ 的卡牌比数字 $ y $ 的卡牌强。

两个玩家，Alex 和 Boris，玩这个游戏。一开始，他们各自得到 $ \frac{n}{2} $ 张卡牌，所以每张卡牌恰好属于一个玩家。然后，他们轮流进行游戏。Alex 先出，然后是 Boris，然后是 Alex，依此类推。

在玩家的回合，他必须打出一张自己的卡牌。然后，如果对手没有比打出的卡牌更强的卡牌，对手就输了，游戏结束。否则，对手必须打出一张更强的卡牌（同样只能是一张）。这两张卡牌从游戏中移除，本回合结束。如果没有卡牌剩下，游戏以平局结束；否则，轮到对手的回合。

考虑所有可能的分配卡牌的方式，使得他们各自得到一半的卡牌。你需要计算三个数：

- 分配卡牌的方式中，Alex 获胜的方案数；
- 分配卡牌的方式中，Boris 获胜的方案数；
- 分配卡牌的方式中，游戏以平局结束的方案数。

你可以假设两个玩家都玩得非常聪明（即如果一个玩家不管对手怎么玩都能赢，那他就赢了）。如果至少有一张卡牌，在一种分配方式中给了 Alex，在另一种分配方式中给了 Boris，那么这两种分配方式是不同的。

**输入输出格式**

**输入格式**

第一行包含一个整数 $ t $（$ 1 \le t \le 30 $）——测试用例的数量。

然后，跟随 $ t $ 行。第 $ i $ 行包含一个偶数整数 $ n $（$ 2 \le n \le 60 $）。

**输出格式**

对于每个测试用例，打印三个整数：

- 分配卡牌的方式中，Alex 获胜的方案数；
- 分配卡牌的方式中，Boris 获胜的方案数；
- 分配卡牌的方式中，游戏以平局结束的方案数。

由于答案可能很大，请将它们模 $ 998244353 $ 后输出。

**输入输出样例**

**输入样例 #1**

```
5
2
4
6
8
60
```

**输出样例 #1**

```
1 0 1
3 2 1
12 7 1
42 27 1
341102826 248150916 1
```**题意翻译** 有 $ n $ 张卡牌，每张卡牌上写了 $[1,n]$ 中的一个整数，卡牌上的数字互不相同。 Alex 和 Boris 在玩游戏，每人有 $ \frac{n}{2} $ 张卡牌，有 $ \frac{n}{2} $ 轮。第一轮 Alex 先出牌，第二轮 Boris 先出牌，以此类推。 在一轮中，若先手出的牌上写的数为 $ x $，则后手必须出一张比 $ x $ 大的牌，如果没有则后手失败。双方都出完了牌则是平局。 假设两人都绝顶聪明，求所有分配牌的方案中，Alex 获胜、Boris 获胜和平局的方案数。 **题目描述** 考虑一个游戏，有 $ n $ 张卡牌（$ n $ 是偶数）。每张卡牌上写着一个在 $ 1 $ 和 $ n $ 之间的数字。所有卡牌上的数字都不相同。如果一张卡牌上的数字 $ x $ 大于另一张卡牌上的数字 $ y $，我们说数字 $ x $ 的卡牌比数字 $ y $ 的卡牌强。 两个玩家，Alex 和 Boris，玩这个游戏。一开始，他们各自得到 $ \frac{n}{2} $ 张卡牌，所以每张卡牌恰好属于一个玩家。然后，他们轮流进行游戏。Alex 先出，然后是 Boris，然后是 Alex，依此类推。 在玩家的回合，他必须打出一张自己的卡牌。然后，如果对手没有比打出的卡牌更强的卡牌，对手就输了，游戏结束。否则，对手必须打出一张更强的卡牌（同样只能是一张）。这两张卡牌从游戏中移除，本回合结束。如果没有卡牌剩下，游戏以平局结束；否则，轮到对手的回合。 考虑所有可能的分配卡牌的方式，使得他们各自得到一半的卡牌。你需要计算三个数： - 分配卡牌的方式中，Alex 获胜的方案数； - 分配卡牌的方式中，Boris 获胜的方案数； - 分配卡牌的方式中，游戏以平局结束的方案数。 你可以假设两个玩家都玩得非常聪明（即如果一个玩家不管对手怎么玩都能赢，那他就赢了）。如果至少有一张卡牌，在一种分配方式中给了 Alex，在另一种分配方式中给了 Boris，那么这两种分配方式是不同的。 **输入输出格式** **输入格式** 第一行包含一个整数 $ t $（$ 1 \le t \le 30 $）——测试用例的数量。 然后，跟随 $ t $ 行。第 $ i $ 行包含一个偶数整数 $ n $（$ 2 \le n \le 60 $）。 **输出格式** 对于每个测试用例，打印三个整数： - 分配卡牌的方式中，Alex 获胜的方案数； - 分配卡牌的方式中，Boris 获胜的方案数； - 分配卡牌的方式中，游戏以平局结束的方案数。 由于答案可能很大，请将它们模 $ 998244353 $ 后输出。 **输入输出样例** **输入样例 #1** ``` 5 2 4 6 8 60 ``` **输出样例 #1** ``` 1 0 1 3 2 1 12 7 1 42 27 1 341102826 248150916 1 ```