#P17611. Meltel

Meltel

题目描述

给定正整数 nn,请对 s=0,1,…,ns=0,1, \dots, n,计数满足存在恰好 ss 棵二叉树的 nn 个结点的由有标号有根树组成的有标号森林的个数。
对 998244353998244353 取模。

定义二叉树为每个结点只有不超过 22 个儿子的有标号有根树。
定义两片森林不同,当且仅当存在两个结点的父亲不同(根结点视为没有父亲)。

输入格式

第一行,一个正整数 nn。

输出格式

一行,n+1n+1 个非负整数,表示对于 s=0,1,…,ns=0,1,\dots,n 的答案。

输入输出样例 #1

输入 #1

3

输出 #1

0 9 6 1

输入输出样例 #2

输入 #2

4

输出 #2

4 60 48 12 1

输入输出样例 #3

输入 #3

5

输出 #3

85 560 480 150 20 1

说明/提示

【样例 11 说明】

33 个点只可能出现二叉树,因此 s=0s=0 的方案数为 00。
33 个点的有标号有根二叉树有 99 种,因此 s=1s=1 的方案数为 99。
22 个点的有标号有根二叉树有 22 种,因此 s=2s=2 的方案数为 3×2=63 \times 2 = 6。
单个结点也算有标号有根二叉树,因此 s=3s=3 的方案数为 11。

【数据规模与约定】

本题采用捆绑测试。

  • Subtask 1(5 points):n≤5n\le 5。
  • Subtask 2(5 points):n≤10n \le 10。
  • Subtask 3(30 points):n≤103n\le 10^3。
  • Subtask 4(30 points):n≤8×103n\le 8\times 10^3。
  • Subtask 5(30 points):无特殊限制。

对于 100%100\% 的数据,1≤n≤2×1051 \le n \le 2 \times 10^5。