Wooden Spoon
Contest: VK Cup 2022 - Финальный раунд (Engine)
Difficulty rating: 2400
Tags: combinatorics, dp

$$$2^n$$$ people, numbered with distinct integers from $$$1$$$ to $$$2^n$$$, are playing in a single elimination tournament. The bracket of the tournament is a full binary tree of height $$$n$$$ with $$$2^n$$$ leaves.

When two players meet each other in a match, a player with the smaller number always wins. The winner of the tournament is the player who wins all $$$n$$$ their matches.

A virtual consolation prize "Wooden Spoon" is awarded to a player who satisfies the following $$$n$$$ conditions:

- they lost their first match;
- the player who beat them lost their second match;
- the player who beat that player lost their third match;
- $$$\ldots$$$;
- the player who beat the player from the previous condition lost the final match of the tournament.

It can be shown that there is always exactly one player who satisfies these conditions.

Consider all possible $$$(2^n)!$$$ arrangements of players into the tournament bracket. For each player, find the number of these arrangements in which they will be awarded the "Wooden Spoon", and print these numbers modulo $$$998\,244\,353$$$.

Input format:
The only line contains a single integer $$$n$$$ ($$$1 \le n \le 20$$$) — the size of the tournament.

There are $$$20$$$ tests in the problem: in the first test, $$$n = 1$$$; in the second test, $$$n = 2$$$; $$$\ldots$$$; in the $$$20$$$-th test, $$$n = 20$$$.

Output format:
Print $$$2^n$$$ integers — the number of arrangements in which the "Wooden Spoon" is awarded to players $$$1, 2, \ldots, 2^n$$$, modulo $$$998\,244\,353$$$.

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

Note:
In the first example, the "Wooden Spoon" is always awarded to player $$$2$$$.

In the second example, there are $$$8$$$ arrangements where players $$$1$$$ and $$$4$$$ meet each other in the first match, and in these cases, the "Wooden Spoon" is awarded to player $$$3$$$. In the remaining $$$16$$$ arrangements, the "Wooden Spoon" is awarded to player $$$4$$$.

Example input:
1

Example output:
0
2

Example input:
2

Example output:
0
0
8
16

Editorial:
Let's focus on the sequence of players beating each other $$$1 = a_0 < a_1 < \ldots < a_n$$$: $$$a_0$$$ is the tournament champion, $$$a_0$$$ beats $$$a_1$$$ in the last match, $$$a_1$$$ beats $$$a_2$$$ in the second-to-last match, $$$\ldots$$$, $$$a_{n-1}$$$ beats $$$a_n$$$ in the first match.
For a fixed such sequence, how many ways are there to fill the tournament bracket?
Let's look at the sequence in reverse.
There are $$$2^n$$$ ways to put player $$$a_n$$$ somewhere.
Player $$$a_{n-1}$$$ has to be the opponent of player $$$a_n$$$ in the first match.
Player $$$a_{n-2}$$$ has to beat some player $$$b > a_{n-2}$$$ in the first match, and then beat $$$a_{n-1}$$$ in the second match. There are $$$2^n - a_{n-2} - 2$$$ ways to choose player $$$b$$$ (since it can not be equal to $$$a_{n-1}$$$ and $$$a_n$$$), and there are also $$$2$$$ ways to order $$$a_{n-2}$$$ and $$$b$$$.
Player $$$a_{n-3}$$$ has to be the winner of a subbracket containing $$$3$$$ other players $$$c_1, c_2, c_3 > a_{n-3}$$$, and then beat $$$a_{n-2}$$$ in the third match. There are $$$2^n - a_{n-3} - 4$$$ players to choose $$$c_i$$$ from (since they can not be equal to $$$a_{n-2}$$$, $$$a_{n-1}$$$, $$$a_n$$$, and $$$b$$$), and there are $$$\binom{2^n - a_{n-3} - 4}{3}$$$ ways to do so, and there are also $$$4!$$$ ways to order $$$a_{n-3}$$$, $$$c_1$$$, $$$c_2$$$, and $$$c_3$$$.
In general, player $$$a_{n - i}$$$ has to be the winner of a subbracket containing $$$2^{i-1} - 1$$$ other players, and there are $$$2^n - a_{n-i} - 2^{i-1}$$$ players to choose from, and there are $$$\binom{2^n - a_{n-i} - 2^{i-1}}{2^{i-1} - 1}$$$ ways to choose, and also $$$(2^{i-1})!$$$ ways to order this subbracket.
You can see that the total number of brackets for a fixed sequence $$$1 = a_0 < a_1 < \ldots < a_n$$$ can be represented as $$$f(a_0, 0) \cdot f(a_1, 1) \cdot \ldots \cdot f(a_{n-1}, n-1) \cdot f(a_n, n)$$$, where $$$f(a_i, i)$$$ is some function of a player number and a round number.
Now let's use dynamic programming: let $$$d(a_i, i)$$$ be the sum of products of $$$f(a_0, 0) \cdot f(a_1, 1) \cdot \ldots \cdot f(a_i, i)$$$ over all sequences $$$1 = a_0 < a_1 < \ldots < a_i$$$. Then:
• $$$d(1, 0) = f(1, 0)$$$;
• $$$d(a_0, 0) = 0$$$ for $$$a_0 > 1$$$;
• $$$d(a_i, i) = f(a_i, i) \cdot \sum \limits_{a_{i-1}=1}^{a_i-1} d(a_{i-1}, i-1)$$$ for $$$i > 0$$$.
The answer for player $$$x$$$ is $$$d(x, n)$$$.
This DP has $$$O(n \cdot 2^n)$$$ states, and note that the inner sums in the formulas for $$$d(a_i, i)$$$ and $$$d(a_i + 1, i)$$$ only differ by one summand. Thus, by using cumulative sums for transitions, we can achieve an $$$O(n \cdot 2^n)$$$ time complexity.