Best Coder ^beta
VIP | STD Contests
DIY | Web-DIY ^beta

流年烹茶

Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 43 Accepted Submission(s): 5

Problem Description

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

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

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

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

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

虽然要对 $998244353$ 取模。

Input

本题有多组测试数据。

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

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

Output

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

Sample Input

Sample Output

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，故必然满足不了。

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

Source

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

Statistic | Submit | Discuss | Note

Home | Top

Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-11-25 00:12:36, Gzip enabled

Administration