/ 
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 で出力せよ。
入力例 1
3 6 3 5 6
出力例 1
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 を出力します。
入力例 2
5 0 1 2 1 2 1
出力例 2
598946612
時刻 0 から 0.5 秒後には最初に再生された曲が再生されているため、求める確率は \frac{1}{5} となります。
同じ長さの異なる曲が存在することがあることに注意してください。
入力例 3
5 10000 1 2 3 4 5
出力例 3
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 1
3 6 3 5 6
Sample Output 1
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 2
5 0 1 2 1 2 1
Sample Output 2
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 3
5 10000 1 2 3 4 5
Sample Output 3
586965467