Score : $450$ points

问题描述

Takahashi 拥有一个包含 $N$ 首歌曲的播放列表。第 $i$ 首歌（$1 \leq i \leq N$）持续时间为 $T_i$ 秒。

Takahashi 在时间 $0$ 开始以随机播放模式播放该播放列表。

随机播放会重复以下过程：从 $N$ 首歌中以相等的概率选择一首，并连续播放至结束。这里，歌曲是连续播放的：一旦一首歌结束，立即开始播放下一首被选中的歌曲。同一首歌可以连续被选中播放。

求在时间 $0$ 后 $(X + 0.5)$ 秒时正在播放第一首歌的概率，结果对 $998244353$ 取模。

如何打印模 $998244353$ 的概率

可以证明本题中要找的概率始终是一个有理数。此外，本题的条件保证了当这个概率表示为不可约分数 $\frac{y}{x}$ 时，$x$ 不会被 $998244353$ 整除。

因此，存在一个唯一的整数 $z$，满足 $0 \leq z \leq 998244352$，且 $xz \equiv y \pmod{998244353}$。请报告这个 $z$ 值。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 01:45:01