Logo Universal Online Judge

UOJ

时间限制:3 s 空间限制:512 MB
Statistics

对于一棵根为 $r$ 的有根树 $T = (V, E)$,若 $V$ 上的置换 $\sigma \colon V \to V$ 满足:

  • $\sigma(r) = r$,
  • 对于 $\forall u, v \in V$,$(u, v) \in E$ 当且仅当 $\bigl( \sigma(u), \sigma(v) \bigr) \in E$,

则称 $\sigma$ 是 $T$ 的一个自同构。已经证明,$T$ 的所有自同构关于置换的合成构成一个群,称为 $T$ 的自同构群,记作 $\operatorname{Aut}(T)$。

现在,给定正整数 $n, m$,你需要对每个 $k = 1, 2, \ldots, n$,求出有多少个无标号有根树 $T$ 满足 $|T| = k$ 且 $\bigl| \operatorname{Aut}(T) \bigr| = m$。

由于答案可能过大,你只需要输出其模 $998\,244\,353$ 的结果。

输入:

输入共一行,包含两个正整数 $n, m$,分别表示树的点数上限和自同构群的大小。

输出:

输出共 $n$ 行,每行一个整数,第 $i$ 行的整数表示满足 $|T| = i$ 且 $\bigl| \operatorname{Aut}(T) \bigr| = m$ 的无标号有根树的数量模 $998\,244\,353$ 的结果。

样例1:
6 1

$6$ 个顶点的 (无标号) 有根树共有 $20$ 个,其中自同构群大小为 $1, 2, 4, 6, 24, 120$ 的分别有 $6, 8, 1, 3, 1, 1$ 个。

{{ s('sample', 2) }}

{{ render(json.dumps('\enlargethispage*{16pt}'), 'tex') }}

{{ self.sample_text() }}

{{ s('sample', 3) }}

{{ self.sample_file() }}

{{ s('数据范围与提示') }}

对于所有的测试点,保证 $1 \leq n \leq 200$,$1 \leq m \leq 10^9$。

具体的测试点的数据规模见下表:

{{ tbl('constraints', width = [0.2, 0.2, 0.2, 0.2]) }}