7002：流年烹茶

题目描述

我拥有 $n$ 个结点，它们被编号为 $1,2,\dots,n$。

我希望你把它们组成一片有根树森林。

我给定了非负整数 $s$，表示我希望总共有 $s$ 个点与其所在树的根结点距离恰好为 $1$ 条边。

我还给定了非负整数 $k$，表示我希望每棵树内只有不超过 $k$ 个点与根结点距离恰好为 $1$ 条边。

但是，我还希望你对于 $m = 1,2,\dots,s$，给出森林恰由 $m$ 棵树组成的方案数（单独一棵树算作森林）。

虽然要对 $998244353$ 取模。

输入解释

本题有多组测试数据。

第一行，一个正整数 $T$ $(1 \le T \le 5)$ 表示数据组数。

对于每组数据，第一行三个整数 $n,s,k$ $(1 \le n < 998244353,1 \le s,k \le 10^5)$。

输出解释

对于每组数据，一行 $s$ 个非负整数，表示对于 $m=1,2,\dots,s$ 的答案。

输入样例

输出样例

6
3 0
24 24
0 60 0
60 80 0

Hint
对于第一组数据：
显然题目的限制相当于计数 3 阶排列个数，则 3! = 6。

对于第二组数据：
若只有一棵树，显然其必然是如下形态：

  ○
 / \
○   ○


故只需要选择根的标号，方案数为 3。
若有两棵树，显然不存在满足条件的方案。

对于第三组数据：
若只有一棵树，显然其必然是如下形态：

    ○
   / \
  ○   ○
 /
○

故方案数是 C(4, 1) * C(3, 2) * 2 = 24。
若有两棵树，显然其必然是如下形态之一：

    ○            ○
   / \
  ○   ○   ,  
          or
    ○            ○
    |            |
    ○     ,      ○

故方案数为 C(4, 3) * 3 + C(4, 2) * 2 * 2 / 2 = 24。

对于第四组数据：  
若只有一棵树，由于 s=3 > k=2 故必然满足不了，方案数为 0。
若有两棵树，显然其必然是如下形态：

    ○            ○
   / \           |
  ○   ○   ,      ○

故方案数为 C(5, 3) * 3 * 2 = 60。
若有三棵树，考虑根的个数 3 加上 s=3 为 6>n=5，故必然满足不了。

对于第五组数据：
我有一个绝妙的解释，但这里空间太小写不下。

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2021 年百度之星·程序设计大赛 - 初赛一

源链接： HDU-7002

最后修改于 2021-10-23T19:11:00+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
20000/10000MS(Java/Others)	32768/32768K(Java/Others)