← 返回题目列表

AtCoder · arc217_c

C. 贪婪的顾客2

中文机器翻译题面 查看原题

分数: 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。