103234: [Atcoder]ABC323 E - Playlist
Description
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
Output
问题描述
高桥有一份包含$N$首歌曲的播放列表。
歌曲$i$ $(1 \leq i \leq N)$的时长为$T_i$秒。
高桥在时间0开始随机播放播放列表。
随机播放重复以下操作：以相等的概率从$N$首歌曲中选择一首，并播放到结束。 这里，歌曲是连续播放的：一旦一首歌曲结束，下一首选择的歌曲立即开始。 相同的歌曲可以连续选择。
求在时间0后$(X + 0.5)$秒播放列表中的第一首歌曲的概率，取模为$998244353$。
如何取模$998244353$打印概率
可以证明本问题中要找到的概率总是有理数。 此外，本问题的约束保证了当要找到的概率表示为不可约分数$\frac{y}{x}$时，$x$不会被$998244353$整除。
那么，存在一个在$0$到$998244352$之间的整数$z$，使得$xz \equiv y \pmod{998244353}$。报告这个$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)$秒正在播放的概率，取模为$998244353$。
样例输入1
3 6 3 5 6
样例输出1
369720131
如果按以下顺序播放歌曲，则歌曲$1$将在时间0后$6.5$秒播放。
- 歌曲$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