/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 700 点
問題文
AtCoder 商店には N 個の品物があります。i 番目の品物は A_i 円です。
AtCoder 商店に N 人の人が順番にやってきます。各人の所持金は C 円で、以下の手続きを行います。
- 買い物に使う予算として、1 以上 C 以下の整数 x を一様ランダムに選ぶ。
- AtCoder 商店に残っている品物の中に x 円以下のものが存在すれば、その中で最も高価なものを 1 つ購入する。存在しない場合は何も購入せず店を去る。
AtCoder 商店の経営者であるあなたは、品物が何個売れるか知りたくなりました。k=0,1,2,\ldots,N について、最終的に品物がちょうど k 個売れる確率を \ \text{mod}\ 998244353 で求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
確率 \ \text{mod}\ 998244353 の定義
求める確率は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、求める有理数を既約分数 \displaystyle \frac{P}{Q} で表した時、Q \neq 0 \bmod 998244353 となることが証明できます。 よって、R \times Q \equiv P \bmod 998244353, 0 \leq R \lt 998244353 を満たす整数 R が一意に定まります。 この 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 番目のテストケースについて考えます。
例えば各人の手続きは以下のように進行します。
- 1 人目：x=2 を選ぶ。2 円以下で最も値段が高い品物は 1 番目の品物なので、1 番目の品物を購入する。
- 2 人目：x=1 を選ぶ。1 円以下の品物は存在しないので、何も購入せず店を去る。
この場合、最終的に品物はちょうど 1 個売れます。
品物がちょうど 0,1,2 個売れる確率はそれぞれ \displaystyle 0, \frac49,\frac59 です。
Score : 700 points
Problem Statement
AtCoder Store has N items. The i-th item costs A_i yen.
N people visit the store one by one. Each person has C yen and performs the following procedure.
- Choose an integer x uniformly at random between 1 and C, inclusive, as the budget for shopping.
- If there is an item remaining in the store that costs at most x yen, purchase one of the most expensive ones among them. Otherwise, leave the store without purchasing anything.
As the owner of the store, you want to know how many items will be sold. For k=0,1,2,\ldots,N, find the probability, modulo 998244353, that exactly k items are sold in the end.
You are given T test cases; solve each of them.
Definition of probability \ \text{mod}\ 998244353
It can be proved that the probabilities to be found are always rational numbers. Moreover, under the constraints of this problem, when each such rational number is expressed as an irreducible fraction \displaystyle \frac{P}{Q}, it can be proved that Q \neq 0 \bmod 998244353. Thus, there is a unique integer R satisfying R \times Q \equiv P \bmod 998244353, 0 \leq R \lt 998244353. Find this R.
Constraints
- 1\le T
- 1\le N
- The sum of N over all test cases is at most 100.
- 1\le A_i \le C < 998244353
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N C A_1 A_2 \ldots A_N
Output
Output the answers for the test cases in order, separated by newlines.
For each test case, output the answers for k=0,1,\ldots,N in order, separated by spaces.
Sample Input 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
Sample Output 1
0 776412275 221832079 465698363 588015298 487439081 455335965 0 0 0 0 0 1 366062443 766314649 169448288 553531286 643499511 890090646 604030590
Consider the first test case.
For example, the procedure for each person proceeds as follows.
- Person 1: Chooses x=2. The most expensive item that costs at most 2 yen is the first item, so they purchase the first item.
- Person 2: Chooses x=1. There are no items costing at most 1 yen, so they leave without purchasing anything.
In this case, exactly one item is sold in the end.
The probabilities that exactly 0,1,2 items are sold are \displaystyle 0, \frac49,\frac59, respectively.