#1645. 烷基计数 加强版 加强版

烷基计数 加强版 加强版

题目描述

原版见 LOJ #6185
众所周知,大连 24 中是一所神奇的学校,在那里,化竞的同学很多都擅长写代码。

有一天,化学不及格的胡小兔向化竞巨佬晴岚请教化学题:

nn 个碳原子的烷基共有多少种同分异构体?」

刚刚得了化竞全市第一的晴岚听了,认为这道题十分简单,建议胡小兔写个程序解决这个问题。但胡小兔弱得连什么是同分异构体都不知道,于是晴岚给胡小兔画了个图——例如 n=4n = 4 时(即丁基),有 44 种同分异构体:

chem.png

同理,其他常见烷基同分异构体数目如下表:

nn 同分异构体数目
11 11
22 11
33 22
44 44
55 88
66 1717

现在已知碳原子个数 nn,求对应的烷基有多少种同分异构体。

注意:这里的烷基计数不用考虑空间异构,能否稳定存在等各种特殊情况。也就是说,你要求的是 nn 个点的每个点度数不超过 44 且根的度数不超过 33 的有根树的数目。

P.S. 2017.11.30 更新:化竞巨佬晴岚高二进国集保送北大了……

输入格式

输入一行,一个整数 n n ,表示烷基中碳原子的数目。

输出格式

作为良心出题人,本题只要求输出该烷基同分异构体的数目 mod  998244353\text{mod}\;998244353

样例

6
17

数据范围与提示

1n1051\le n\le 10^5