E. 物种关系树

    传统题 1000ms 512MiB

物种关系树

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

小明瞎看 OI-WIKI,看出来了下一个 T2

题目描述

小明最近喜欢研究生物,尤其是物种之间的基因关系。

比如, 猴子跟猩猩有直接的亲戚关系,猩猩跟猿有直接的亲戚关系,人和猿有直接的亲戚关系,那么就有这样四条边,我们可以认为人跟猴子之间的基因距离是 44,因为这中间一共经历了 44 个物种。

现在,生物教练徐老师提出了这样一个问题:

假设有 nn 个物种,他们构成了一棵 nn 个节点的有根树,其中:

(1)节点无标号顺序,也就是所有节点都是不可区分的。

(2)所有子树是有顺序的,也就是,如果一个点先接了子树 AA,再接了子树 BB,跟先接了子树 BB,再接了子树 AA 是有区别的。 (3)这棵树上最远的基因距离不超过 kk,也就是,任意两个节点之间的路径上,最多只有 kk 个点。

问:这样的树有多少种。

具体的解释请看第一组样例。

输入格式

第一行输入 n,kn,k

输出格式

输出一个数字表示答案 mod998244353\mod 998244353

样例输入 #1

4 4

样例输出 #1

5

样例解释 #1

由于跟距离没啥关系了,所以一共有 55 种满足要求的树。

样例输入 #2

5 4

样例输出 #2

10

样例解释 #2

一共有 1010 种满足要求的树:

样例输入 #3

80 80

样例输出 #3

381008905

样例输入 #4

80 50

样例输出 #4

164540686

样例输入 #5

10 6

样例输出 #5

2750

数据范围

本题共 20 个测试点。

测试点编号 nn kk
1 =5
2~5 15\leq 15 /
6~9 70\leq 70
10~11 100\leq 100
12~13 =n=n
14~15 /
16~20 /

对于全部测试数据:1kn5001\leq k\leq n\leq 500

联合测试第六场

未参加
状态
已结束
规则
OI
题目
6
开始于
2025-10-25 8:00
结束于
2025-10-26 18:00
持续时间
4 小时
主持人
参赛人数
117