E - Playlist

Contest Duration: 2023-10-07(Sat) 12:00 - 2023-10-07(Sat) 13:40 (local time) (100 minutes) Back to Home

E - Playlist Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $450$ 点

問題文

高橋君は $N$ 曲からなるプレイリストを持っています。曲 $i$ $(1 \leq i \leq N)$ の長さは $T_i$ 秒です。
高橋君は時刻 $0$ にプレイリストのランダム再生を開始しました。

ランダム再生では、 $N$ 曲の中から等確率で $1$ つを選びその曲を最後まで再生することが繰り返されます。ここで、曲の再生は休みなく行われ、 $1$ つの曲が終わったらすぐに次に選ばれた曲が始まります。また、同じ曲が連続して選ばれる事もあります。

時刻 $0$ から $(X+0.5)$ 秒後に曲 $1$ が再生されている確率を $\text{mod}998244353$ で求めてください。

確率 $\text{mod } 998244353$ の定義

この問題で求める確率は必ず有理数になることが証明できます。また、この問題の制約下では、求める確率を既約分数 $\frac{y}{x}$ で表したときに $x$ が $998244353$ で割り切れないことが保証されます。

このとき $xz \equiv y \pmod{998244353}$ を満たすような $0$ 以上 $998244352$ 以下の整数 $z$ が一意に定まります。この $z$ を答えてください。

制約

$2 \leq N\leq 10^3$
$0 \leq X\leq 10^4$
$1 \leq T_i\leq 10^4$
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $X$ 
 $T_1$   $T_2$   $\ldots$   $T_N$

出力

時刻 $0$ から $(X+0.5)$ 秒後にプレイリストの $1$ 番目の曲が再生されている確率を $\text{mod}998244353$ で出力せよ。

入力例 1Copy

Copy

3 6
3 5 6

出力例 1Copy

Copy

369720131

時刻 $0$ から $6.5$ 秒後に曲 $1$ が流れているパターンとしてあり得るのは、

曲 $1$ $\to$ 曲 $1$ $\to$ 曲 $1$
曲 $2$ $\to$ 曲 $1$
曲 $3$ $\to$ 曲 $1$

の順で音楽が再生された場合であり、これらのいずれかが起こる確率は $\frac{7}{27}$ となります。
$369720131\times 27\equiv 7 \pmod{998244353}$ であるため、 $369720131$ を出力します。

入力例 2Copy

Copy

5 0
1 2 1 2 1

出力例 2Copy

Copy

598946612

時刻 $0$ から $0.5$ 秒後には最初に再生された曲が再生されているため、求める確率は $\frac{1}{5}$ となります。
同じ長さの異なる曲が存在することがあることに注意してください。

入力例 3Copy

Copy

5 10000
1 2 3 4 5

出力例 3Copy

Copy

586965467

Score : $450$ points

Problem Statement

Takahashi has a playlist with $N$ songs. Song $i$ $(1 \leq i \leq N)$ lasts $T_i$ seconds.
Takahashi has started random play of the playlist at time $0$ .

Random play repeats the following: choose one song from the $N$ songs with equal probability and play that song to the end. Here, songs are played continuously: once a song ends, the next chosen song starts immediately. The same song can be chosen consecutively.

Find the probability that song $1$ is being played $(X + 0.5)$ seconds after time $0$ , modulo $998244353$ .

How to print a probability modulo $998244353$

It can be proved that the probability to be found in this problem is always a rational number. Also, the constraints of this problem guarantee that when the probability to be found is expressed as an irreducible fraction $\frac{y}{x}$ , $x$ is not divisible by $998244353$ .

Then, there is a unique integer $z$ between $0$ and $998244352$ , inclusive, such that $xz \equiv y \pmod{998244353}$ . Report this $z$ .

Constraints

$2 \leq N\leq 10^3$
$0 \leq X\leq 10^4$
$1 \leq T_i\leq 10^4$
All input values are integers.

Input

The input is given from Standard Input in the following format:

 $N$   $X$ 
 $T_1$   $T_2$   $\ldots$   $T_N$

Output

Print the probability, modulo $998244353$ , that the first song in the playlist is being played $(X+0.5)$ seconds after time $0$ .

Sample Input 1Copy

Copy

3 6
3 5 6

Sample Output 1Copy

Copy

369720131

Song $1$ will be playing $6.5$ seconds after time $0$ if songs are played in one of the following orders.

Song $1$ $\to$ Song $1$ $\to$ Song $1$
Song $2$ $\to$ Song $1$
Song $3$ $\to$ Song $1$

The probability that one of these occurs is $\frac{7}{27}$ .
We have $369720131\times 27\equiv 7 \pmod{998244353}$ , so you should print $369720131$ .

Sample Input 2Copy

Copy

5 0
1 2 1 2 1

Sample Output 2Copy

Copy

598946612

$0.5$ seconds after time $0$ , the first song to be played is still playing, so the sought probability is $\frac{1}{5}$ .
Note that different songs may have the same length.

Sample Input 3Copy

Copy

5 10000
1 2 3 4 5

Sample Output 3Copy

Copy

586965467