33OJ
登录 注册

#P17624. [qaswed12 OI R1] BrrTree

    ID: 20181 远端评测题 1500ms 512MiB 尝试: 0 已通过: 0 显示难度省选/NOI− 上传者: 标签>O2优化组合数学二项式定理容斥原理Stirling 数生成函数快速数论变换 NTT拉格朗日反演Prüfer 序列

[qaswed12 OI R1] BrrTree

背景

Brr Brr patapim 是一只意大利山海经动物。

题目描述

我们定义一颗 brr 树为叶节点数严格大于总节点数二分之一且以 11 为根的有标号树。

给定 TT 组数据,每组数据给定一个整数 nn。
请你求出本质不同的,有 nn 个节点的 brr 树的数量,答案对 998244353998244353 取模。

两棵 brr 树本质不同当且仅当,存在点 ii 和点 jj 在恰好其中一棵 brr 树中有连边。
某个点为叶子节点当且仅当其没有儿子节点。

输入格式

第一行一个整数 TT 表示询问组数。
接下来 TT 行,每行一个正整数 nn。

输出格式

共 TT 行,每行一个整数表示答案。

6
2
3
5
11
1145
14587
0
1
29
239726411
165996705
197549689

提示

样例解释

当 n=2n=2 时显然无解。
当 n=3n=3 时,2,32,3 均为 11 的儿子结点显然为一组解。
当 n=5n=5 时,对于形态如下的树,各有 1,4,12,121,4,12,12 种:


其中 a,b,c,da,b,c,d 是 2,3,4,52,3,4,5 的一个排列。
于是答案为 1+4+12+12=291+4+12+12=29 种。

注意本题要求本质不同的树,即如下两棵树算作相同:

数据范围与约定

本题开启捆绑测试,请注意本题特殊的时间限制。

子任务编号 n≤n \le 分值
11 66 1010
22 1010 1515
33 2020 2020
44 20002000
55 10510^{5} 3535

对于 100%100\% 的数据,满足 1≤T≤101 \le T \le 10,1≤n≤105.1 \le n \le 10^{5}.