[R24E]成环概率 - 代码源竞赛平台

时空限制

1S/512M

题目描述

apiadu 有 $n$ 条绳子。每条绳子有两个绳头，总共有 $2n$ 个绳头。

apiadu 将 $2n$ 个头任意两两相连，保证对于所有可能的最终配对方案，其出现的概率均相同。

这个过程结束后，所有的绳子会形成若干个闭合的环（圈）。请你分别计算出，最终恰好形成 $1,2,3,\cdots,n$ 个圈的概率分别是多少。

你需要将结果对 $998244353$ 取模。

格式

输入格式

第一行包含一个正整数 $n$，表示绳子的数量。

输出格式

第一行输出 $n$ 个正整数，第 $i$ 个整数形成 $i$ 个环的概率。

样例

样例输入 #1

2

样例输出 #1

665496236 332748118

样例解释 #1

假设两条绳子分别称为：绳子 $1$ 和 绳子 $2$。 绳子 $1$ 的两个头记为 1A 和 1B。 绳子 $2$ 的两个头记为 2A 和 2B。

有 $3$ 种连接方式：

1. 1A 与 1B 相连，2A 与 2B，此时构成 $2$ 个环。
2. 1A 与 2A 相连。那么剩下的 1B 和 2B 只能互相连接。此时构成 $1$ 个环。
3. 1A 与 2B 相连。那么剩下的 1B 和 2A 只能互相连接。此时构成 $1$ 个环。

故构成 $1$ 个环的概率为 $\frac{2}{3}$，构成 $2$ 个环的概率为 $\frac{1}{3}$。

数据规模

对于 $20\%$ 的数据，$1 \leq n \leq 5$。

对于 $50\%$ 的数据，$1 \leq n \leq 100$。

对于 $100\%$ 的数据，$1 \leq n \leq 1000$。