310115: CF1784D. Wooden Spoon
Memory Limit：512 MB
Time Limit：4 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Wooden Spoon
题意翻译
有 $2^n$ 个人，进行 $n$ 轮比赛，比赛图是一棵完全二叉树。现在编号小的人一定会赢编号大的人，如果一个人满足： 这个人第一次被另一个人打败。 打败这个人的人又被第三个人打败。 第三个人又被第四个人打败 …… 也就是从这个叶子一直往上一直输，那么这个人就会获得安慰奖“木质勺子”。 求对于每个人，有多少种编号的排列来比赛（叶子的排列），使得他能获得“木质勺子”。题目描述
$ 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 $ .输入输出格式
输入格式
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 $ .
输出格式
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 $ .
输入输出样例
输入样例 #1
1输出样例 #1
0
2输入样例 #2
2输出样例 #2
0
0
8
16输入样例 #3
3输出样例 #3
0
0
0
1536
4224
7680
11520
15360说明
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 $ .Input
题意翻译
有 $2^n$ 个人，进行 $n$ 轮比赛，比赛图是一棵完全二叉树。现在编号小的人一定会赢编号大的人，如果一个人满足： 这个人第一次被另一个人打败。 打败这个人的人又被第三个人打败。 第三个人又被第四个人打败 …… 也就是从这个叶子一直往上一直输，那么这个人就会获得安慰奖“木质勺子”。 求对于每个人，有多少种编号的排列来比赛（叶子的排列），使得他能获得“木质勺子”。Output
**木质勺子**
**题意翻译**
有 $2^n$ 个人，进行 $n$ 轮比赛，比赛图是一棵完全二叉树。现在编号小的人一定会赢编号大的人，如果一个人满足：
- 这个人第一次被另一个人打败。
- 打败这个人的人又被第三个人打败。
- 第三个人又被第四个人打败
- ...
- 从这个叶子一直往上一直输，那么这个人就会获得安慰奖“木质勺子”。
求对于每个人，有多少种编号的排列来比赛（叶子的排列），使得他能获得“木质勺子”。
**题目描述**
$2^n$ 个人，编号为从 $1$ 到 $2^n$ 的不同整数，在进行单淘汰锦标赛。锦标赛的淘汰图是一棵高度为 $n$ 的满二叉树，有 $2^n$ 个叶子节点。
当两个选手相遇时，编号较小的选手总是赢。锦标赛的胜者是赢得所有 $n$ 场比赛的选手。
一种虚拟的安慰奖“木质勺子”会颁发给满足以下 $n$ 个条件的选手：
- 他们第一轮比赛输了；
- 打败他们的选手第二轮比赛输了；
- 打败那个选手的选手第三轮比赛输了；
- ...
- 打败上一条件中选手的选手输掉了锦标赛的最后一轮比赛。
可以证明总会有一个选手满足这些条件。
考虑所有可能的 $(2^n)!$ 种选手进入锦标赛淘汰图的方式。对于每个选手，找出他们能获得“木质勺子”的排列数，并模 $998,244,353$ 后输出这些数字。
**输入输出格式**
**输入格式**
只有一行，包含一个整数 $n$ ($1 \le n \le 20$) —— 锦标赛的大小。
问题中有 $20$ 个测试：在第一个测试中，$n = 1$；在第二个测试中，$n = 2$；...；在第 $20$ 个测试中，$n = 20$。
**输出格式**
输出 $2^n$ 个整数 —— “木质勺子”分别颁发给选手 $1, 2, \ldots, 2^n$ 的排列数，模 $998,244,353$ 后的结果。
**输入输出样例**
**输入样例 #1**
```
1
```
**输出样例 #1**
```
0
2
```
**输入样例 #2**
```
2
```
**输出样例 #2**
```
0
0
8
16
```
**输入样例 #3**
```
3
```
**输出样例 #3**
```
0
0
0
1536
4224
7680
11520
15360
```
**说明**
在第一个例子中，“木质勺子”总是颁发给编号为 $2$ 的选手。
在第二个例子中，有 $8$ 种排列是编号 $1$ 和 $4$ 的选手在第一轮相遇，在这些情况下，“木质勺子”会颁发给编号为 $3$ 的选手。在剩余的 $16$ 种排列中，“木质勺子”会颁发给编号为 $4$ 的选手。**木质勺子** **题意翻译** 有 $2^n$ 个人，进行 $n$ 轮比赛，比赛图是一棵完全二叉树。现在编号小的人一定会赢编号大的人，如果一个人满足： - 这个人第一次被另一个人打败。 - 打败这个人的人又被第三个人打败。 - 第三个人又被第四个人打败 - ... - 从这个叶子一直往上一直输，那么这个人就会获得安慰奖“木质勺子”。 求对于每个人，有多少种编号的排列来比赛（叶子的排列），使得他能获得“木质勺子”。 **题目描述** $2^n$ 个人，编号为从 $1$ 到 $2^n$ 的不同整数，在进行单淘汰锦标赛。锦标赛的淘汰图是一棵高度为 $n$ 的满二叉树，有 $2^n$ 个叶子节点。 当两个选手相遇时，编号较小的选手总是赢。锦标赛的胜者是赢得所有 $n$ 场比赛的选手。 一种虚拟的安慰奖“木质勺子”会颁发给满足以下 $n$ 个条件的选手： - 他们第一轮比赛输了； - 打败他们的选手第二轮比赛输了； - 打败那个选手的选手第三轮比赛输了； - ... - 打败上一条件中选手的选手输掉了锦标赛的最后一轮比赛。 可以证明总会有一个选手满足这些条件。 考虑所有可能的 $(2^n)!$ 种选手进入锦标赛淘汰图的方式。对于每个选手，找出他们能获得“木质勺子”的排列数，并模 $998,244,353$ 后输出这些数字。 **输入输出格式** **输入格式** 只有一行，包含一个整数 $n$ ($1 \le n \le 20$) —— 锦标赛的大小。 问题中有 $20$ 个测试：在第一个测试中，$n = 1$；在第二个测试中，$n = 2$；...；在第 $20$ 个测试中，$n = 20$。 **输出格式** 输出 $2^n$ 个整数 —— “木质勺子”分别颁发给选手 $1, 2, \ldots, 2^n$ 的排列数，模 $998,244,353$ 后的结果。 **输入输出样例** **输入样例 #1** ``` 1 ``` **输出样例 #1** ``` 0 2 ``` **输入样例 #2** ``` 2 ``` **输出样例 #2** ``` 0 0 8 16 ``` **输入样例 #3** ``` 3 ``` **输出样例 #3** ``` 0 0 0 1536 4224 7680 11520 15360 ``` **说明** 在第一个例子中，“木质勺子”总是颁发给编号为 $2$ 的选手。 在第二个例子中，有 $8$ 种排列是编号 $1$ 和 $4$ 的选手在第一轮相遇，在这些情况下，“木质勺子”会颁发给编号为 $3$ 的选手。在剩余的 $16$ 种排列中，“木质勺子”会颁发给编号为 $4$ 的选手。
**题意翻译**
有 $2^n$ 个人，进行 $n$ 轮比赛，比赛图是一棵完全二叉树。现在编号小的人一定会赢编号大的人，如果一个人满足：
- 这个人第一次被另一个人打败。
- 打败这个人的人又被第三个人打败。
- 第三个人又被第四个人打败
- ...
- 从这个叶子一直往上一直输，那么这个人就会获得安慰奖“木质勺子”。
求对于每个人，有多少种编号的排列来比赛（叶子的排列），使得他能获得“木质勺子”。
**题目描述**
$2^n$ 个人，编号为从 $1$ 到 $2^n$ 的不同整数，在进行单淘汰锦标赛。锦标赛的淘汰图是一棵高度为 $n$ 的满二叉树，有 $2^n$ 个叶子节点。
当两个选手相遇时，编号较小的选手总是赢。锦标赛的胜者是赢得所有 $n$ 场比赛的选手。
一种虚拟的安慰奖“木质勺子”会颁发给满足以下 $n$ 个条件的选手：
- 他们第一轮比赛输了；
- 打败他们的选手第二轮比赛输了；
- 打败那个选手的选手第三轮比赛输了；
- ...
- 打败上一条件中选手的选手输掉了锦标赛的最后一轮比赛。
可以证明总会有一个选手满足这些条件。
考虑所有可能的 $(2^n)!$ 种选手进入锦标赛淘汰图的方式。对于每个选手，找出他们能获得“木质勺子”的排列数，并模 $998,244,353$ 后输出这些数字。
**输入输出格式**
**输入格式**
只有一行，包含一个整数 $n$ ($1 \le n \le 20$) —— 锦标赛的大小。
问题中有 $20$ 个测试：在第一个测试中，$n = 1$；在第二个测试中，$n = 2$；...；在第 $20$ 个测试中，$n = 20$。
**输出格式**
输出 $2^n$ 个整数 —— “木质勺子”分别颁发给选手 $1, 2, \ldots, 2^n$ 的排列数，模 $998,244,353$ 后的结果。
**输入输出样例**
**输入样例 #1**
```
1
```
**输出样例 #1**
```
0
2
```
**输入样例 #2**
```
2
```
**输出样例 #2**
```
0
0
8
16
```
**输入样例 #3**
```
3
```
**输出样例 #3**
```
0
0
0
1536
4224
7680
11520
15360
```
**说明**
在第一个例子中，“木质勺子”总是颁发给编号为 $2$ 的选手。
在第二个例子中，有 $8$ 种排列是编号 $1$ 和 $4$ 的选手在第一轮相遇，在这些情况下，“木质勺子”会颁发给编号为 $3$ 的选手。在剩余的 $16$ 种排列中，“木质勺子”会颁发给编号为 $4$ 的选手。**木质勺子** **题意翻译** 有 $2^n$ 个人，进行 $n$ 轮比赛，比赛图是一棵完全二叉树。现在编号小的人一定会赢编号大的人，如果一个人满足： - 这个人第一次被另一个人打败。 - 打败这个人的人又被第三个人打败。 - 第三个人又被第四个人打败 - ... - 从这个叶子一直往上一直输，那么这个人就会获得安慰奖“木质勺子”。 求对于每个人，有多少种编号的排列来比赛（叶子的排列），使得他能获得“木质勺子”。 **题目描述** $2^n$ 个人，编号为从 $1$ 到 $2^n$ 的不同整数，在进行单淘汰锦标赛。锦标赛的淘汰图是一棵高度为 $n$ 的满二叉树，有 $2^n$ 个叶子节点。 当两个选手相遇时，编号较小的选手总是赢。锦标赛的胜者是赢得所有 $n$ 场比赛的选手。 一种虚拟的安慰奖“木质勺子”会颁发给满足以下 $n$ 个条件的选手： - 他们第一轮比赛输了； - 打败他们的选手第二轮比赛输了； - 打败那个选手的选手第三轮比赛输了； - ... - 打败上一条件中选手的选手输掉了锦标赛的最后一轮比赛。 可以证明总会有一个选手满足这些条件。 考虑所有可能的 $(2^n)!$ 种选手进入锦标赛淘汰图的方式。对于每个选手，找出他们能获得“木质勺子”的排列数，并模 $998,244,353$ 后输出这些数字。 **输入输出格式** **输入格式** 只有一行，包含一个整数 $n$ ($1 \le n \le 20$) —— 锦标赛的大小。 问题中有 $20$ 个测试：在第一个测试中，$n = 1$；在第二个测试中，$n = 2$；...；在第 $20$ 个测试中，$n = 20$。 **输出格式** 输出 $2^n$ 个整数 —— “木质勺子”分别颁发给选手 $1, 2, \ldots, 2^n$ 的排列数，模 $998,244,353$ 后的结果。 **输入输出样例** **输入样例 #1** ``` 1 ``` **输出样例 #1** ``` 0 2 ``` **输入样例 #2** ``` 2 ``` **输出样例 #2** ``` 0 0 8 16 ``` **输入样例 #3** ``` 3 ``` **输出样例 #3** ``` 0 0 0 1536 4224 7680 11520 15360 ``` **说明** 在第一个例子中，“木质勺子”总是颁发给编号为 $2$ 的选手。 在第二个例子中，有 $8$ 种排列是编号 $1$ 和 $4$ 的选手在第一轮相遇，在这些情况下，“木质勺子”会颁发给编号为 $3$ 的选手。在剩余的 $16$ 种排列中，“木质勺子”会颁发给编号为 $4$ 的选手。