传统题 文件IO:species 2000ms 256MiB

物种关系(24-4)

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

题目背景

小一最近对生物进化非常感兴趣,她发现不同物种之间存在亲缘关系,可以用一棵有根树来表示这些基因联系。通过研究树的形状,她想知道在限制最大基因距离的条件下,有多少种可能的进化树结构。

题目描述

小一加入了生物兴趣小组。最近她尤其喜欢研究物种之间的基因关系。比如,猴子跟猩猩有直接的亲戚关系,猩猩跟猿有直接的亲戚关系,猿和人有直接的亲戚关系,那么就有这样四个物种沿着一条链,我们可以认为人跟猴子之间的基因距离是4,因为这中间一共经历了4个物种。

现在,生物教练岐岐提出了这样一个问题:
假设有 nn 个物种,它们构成了一棵有 nn 个节点的有根树,其中:
(1) 节点无标号顺序,也就是所有节点都是不可区分的。
(2) 所有子树是有顺序的,也就是说,如果一个点先接了子树 AA,再接了子树 BB,与先接了子树 BB 再接子树 AA 是不同的。
(3) 这棵树上最远的基因距离不超过 kk,也就是任意两个节点之间的路径上,最多包含 kk 个点。

问:满足上述条件的不同有根有序树共有多少种?

小一觉得可以借助程序快速回答岐岐的问题。你的程序运行结果会和她的一样吗?

输入格式

第一行包含两个整数 nnkk

输出格式

输出一个整数,表示满足条件的树的数量。结果需对 998244353998244353 取模。

样例

4 4
5

样例解释 #1
k=4k=4 时,树的最大深度限制不影响所有结构,总共有 5 种不同的有根有序树。

img

5 4
10

样例解释 #2
n=5,k=4n=5, k=4 时,最多允许的基因距离为 4,一共有 10 种满足要求的树。

img

80 80
381008905
80 50
164540686
10 6
2750

数据范围

本题共 20 个测试点。

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

对于所有测试数据,满足

1kn500.1 \le k \le n \le 500.

CSP-X/J 模拟赛3 补题

未参加
状态
已结束
规则
IOI
题目
8
开始于
2025-10-8 20:00
结束于
2025-10-19 6:00
持续时间
250 小时
主持人
参赛人数
26