分数: 700 点
问题陈述
AtCoder 商店有 N 项目。的 i第一项成本 A_i 日元。
N 人们一一参观商店。每个人都有 C 日元并执行以下过程。
- 选择一个整数 x 之间均匀随机 1 和 C,包含在内,作为购物预算。
- 如果商店中剩余的商品成本最高 x 日元,购买其中最贵的之一。否则,不要购买任何东西就离开商店。
作为商店的所有者,您想知道将售出多少商品。对于 k=0,1,2,\ldots,N,求概率,模 998244353,正是如此 k 物品最终售出。
你被给予 T 测试用例;解决它们中的每一个。
概率的定义 \ \text{mod}\ 998244353
可以证明,要找到的概率总是有理数。而且,在这个问题的约束下,当每个这样的有理数都表示为不可约分数时 \displaystyle \frac{P}{Q},可以证明 Q \neq 0 \bmod 998244353。因此,有一个唯一的整数 R 满意 R \times Q \equiv P \bmod 998244353, 0 \leq R \lt 998244353。找到这个 R.
约束
- 1\le T
- 1\le N
- 总和 一个输入文件中的 N 所有测试用例最多 100.
- 1\le A_i \le C < 998244353
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N C A_1 A_2 \ldots A_N
输出
按顺序输出测试用例的答案,以换行符分隔。
对于每个测试用例,输出以下答案 k=0,1,\ldots,N 按顺序排列,用空格分隔。
样本输入 1
4 2 3 1 3 3 17 9 9 8 5 2025 1 1 1 1 1 6 1000 544 105 450 715 479 992
示例输出 1
0 776412275 221832079 465698363 588015298 487439081 455335965 0 0 0 0 0 1 366062443 766314649 169448288 553531286 643499511 890090646 604030590
考虑第一个测试用例。
例如,每个人的程序如下进行。
- 人 1:选择 x=2。成本最高的最昂贵的物品 2 日元是第一个项目,因此他们购买第一个项目。
- 人 2:选择 x=1。没有最高花费的物品 1 日元,所以他们没有购买任何东西就离开了。
在这种情况下,最终仅售出了一件商品。
确切的概率 0,1,2 出售的物品是 \displaystyle 0, \frac49,\frac59。