「雅礼集训 2018 Day8」C

ID: 17493

传统题

2000ms

512MiB

难度: (无)

上传者:

标签>

DFT（含 NTT）及FFT

雅礼集训

生成函数 / 母函数

分治

2018

题目描述

计算化学式为 ${\rm C}_n{\rm H}_{2n+2}$ 的烷烃的同分异构体个数。

多组数据，答案对 $998244353$ 取模。

提示：如果你不知道什么是烷烃，那么你可以认为这个问题等价于求 $n$ 个点的无标号无根树并满足每个点的度数 $\leq 4$ 的树的个数。

第一行一个整数 $T$ ，表示数据组数。

接下来 $T$ 行，每行一个整数 $n$ ，表示询问化学式为 ${\rm C}_n{\rm H}_{2n + 2}$ 的烷烃的同分异构体个数。

共输出 $T$ 行，每行一个整数，表示答案。

测试点编号	$T$	$n$	分值
$1$	$=1$	$\leq 8$	$5$
$2$		$\leq 200$	$5$
$3$		$\leq 200$	$5$
$4$		$\leq 2000$	$5$
$5$			$5$
$6$			$5$
$7$		$= 66666$	$5$
$8$		$\leq 10^5$	$5$
$9$			$5$
$10$			$5$
$11$			$5$
$12$			$5$
$13$	$=10^5$		$40$