当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

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$ 的答案。
输入样例
5
3 1 3
3 2 3
4 2 3
5 3 2
5 3 5
输出样例
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

源链接: HDU-7002

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

共提交 0

通过率 --%
时间上限 内存上限
20000/10000MS(Java/Others) 32768/32768K(Java/Others)