Playlist

题目描述

Takahashi 有一个包含 $N$ 首歌曲的播放列表。 第 $i$ 首歌 $(1 \leq i \leq N)$ 时长为 $T_i$ 秒。
Takahashi 在时间 $0$ 开始随机播放该播放列表。 随机播放重复以下过程：从这 $N$ 首歌中以相等的概率选择一首歌并将其播放至结束。 这里，歌曲是连续播放的：一首歌结束后，下一个被选中的歌曲立即开始播放。 同一首歌可以连续被选中。 求在时间 $0$ 之后 $(X + 0.5)$ 秒时正在播放第 1 首歌的概率，对 $998244353$ 取模。

输入格式

从标准输入读入，格式如下： $N$ $X$ $T_1$ $T_2$ $\ldots$ $T_N$

输出格式

输出在时间 $0$ 之后 $(X+0.5)$ 秒时正在播放第 1 首歌的概率，对 $998244353$ 取模。

3 6
3 5 6

369720131

5 0
1 2 1 2 1

598946612

5 10000
1 2 3 4 5

586965467

提示

$2 \leq N\leq 10^3$ $0 \leq X\leq 10^4$ $1 \leq T_i\leq 10^4$ 所有输入值均为整数。在时间 $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$.
在时间 $0.5$ 秒后，第一首被选中的歌仍在播放，因此所求概率是 $\frac{1}{5}$.
注意不同歌曲的时长可能相同。

标签: AtCoder|abc323E

来源

AtCoder|abc323E