Card Game
Contest: Educational Codeforces Round 136 (Rated for Div. 2)
Difficulty rating: 1500
Tags: combinatorics, constructive algorithms, dp, games

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.

Input format:
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$$$).

Output format:
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$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
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]$$$.

Example input:
5
2
4
6
8
60

Example output:
1 0 1
3 2 1
12 7 1
42 27 1
341102826 248150916 1

Editorial:
The example tests suggest that there is only one possible distribution with a draw. Let's find out why it is so. We will use a process similar to induction/recursion to distribute the cards between the two players so that the game ends in a draw:
• suppose Alex receives the card $$$n$$$. Then he wins since he can play it immediately. So, for the game to result in a draw, Boris must receive the card $$$n$$$.
• suppose Boris receives the card $$$n-1$$$. Then he wins since he also has the card $$$n$$$, he can use it to answer any first move of Alex, and then win the game by playing $$$n-1$$$. So, for the game to result in a draw, Alex must receive the card $$$n-1$$$.
• suppose Boris receives the card $$$n-2$$$. Then he wins since he also has the card $$$n$$$: if Alex plays the card $$$n-1$$$, Boris responds with $$$n$$$ and then plays $$$n-2$$$; if Alex plays some other card, Boris responds with $$$n-2$$$ and the plays $$$n$$$. So, for the game to result in a draw, Alex must receive the card $$$n-2$$$.
• and so on.
In fact, if Alex receives the card $$$n-1$$$ and Boris receives the card $$$n$$$, Alex must play the card $$$n-1$$$ or something equivalent to it on the first move, and Boris must respond with the card $$$n$$$, so we can consider the game without these two cards with the roles swapped.
So, if we consider the distribution of cards as a string with characters A and B, where A denotes the card belonging to Alex, and B denotes the card belonging to Boris, and the $$$i$$$-th character of the string represents the card $$$n-i+1$$$, the only possible distribution for the draw is BAABBAAB... But there's more to this string representation of the distribution of cards: the first character that is different from this pattern denotes the winner; if the first different character is A in the draw distribution and B in the distribution we consider, the winner is Boris; otherwise, the winner is Alex.
This may lead us to the following ways to count the number of possible distributions which win/lose for Alex:
• we can use dynamic programming of the form $$$dp_{x,y,t}$$$, where $$$x$$$ is the number of characters A we used, $$$y$$$ is the number of characters B we used, and $$$t$$$ is $$$0$$$, $$$1$$$ or $$$2$$$ depending on whether our string coincides with the draw string ($$$t = 0$$$), differs from it in a way that Alex wins ($$$t = 1$$$), or differs from it in a way that Boris wins ($$$t = 2$$$); the actual value of $$$dp_{x,y,t}$$$ must be the number of ways to reach this state of dynamic programming. The answer then is stored in the states of the form $$$dp_{\frac{n}{2},\frac{n}{2},t}$$$.
• or we can use combinatorics: let's iterate on the length of the prefix that is common in the draw string and in the string representing the distribution of cards, and then count the number of ways to distribute the remaining characters with a binomial coefficient. To calculate the binomial coefficients, we can use one of the following methods: Pascal's triangle, precalculating factorials and modular inverses to then, or calculating factorials with big integers in Java or Python.