AT_abc323_e [ABC323E] Playlist

题目描述

高桥君有一个包含 $N$ 首歌曲的播放列表。第 $i$ 首歌曲（$1 \leq i \leq N$）的时长为 $T_i$ 秒。
高桥君在时刻 $0$ 开始以随机播放的方式播放该播放列表。

在随机播放中，每次会等概率地从 $N$ 首歌曲中选择一首，并将其播放至结束。播放过程不间断，一首歌播放结束后，立即开始播放下一首被选中的歌曲。相同的歌曲可能会被连续选中。

请计算在时刻 $0$ 到 $(X+0.5)$ 秒后，第 $1$ 首歌曲正在播放的概率，并对 $998244353$ 取模输出。

概率 $\bmod\ 998244353$ 的定义：本题中要求的概率一定可以表示为有理数。并且，在本题的约束下，若将概率表示为最简分数 $\frac{y}{x}$，则 $x$ 保证不会被 $998244353$ 整除。

此时，存在唯一的 $0$ 到 $998244352$ 之间的整数 $z$，使得 $xz \equiv y \pmod{998244353}$。请输出这个 $z$。

输入格式

输入以以下格式从标准输入读入。

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

输出格式

请输出从时刻 $0$ 到 $(X+0.5)$ 秒后，第 $1$ 首歌曲正在播放的概率，$\bmod\ 998244353$。

输入输出样例 #1

输入 #1

3 6
3 5 6

输出 #1

369720131

输入输出样例 #2

输入 #2

5 0
1 2 1 2 1

输出 #2

598946612

输入输出样例 #3

输入 #3

5 10000
1 2 3 4 5

输出 #3

586965467

说明/提示

约束条件

• $2 \leq N \leq 10^3$
• $0 \leq X \leq 10^4$
• $1 \leq T_i \leq 10^4$
• 所有输入均为整数

样例解释 1

在时刻 $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

在时刻 $0$ 到 $0.5$ 秒后，正在播放的就是最初被选中的那首歌，因此概率为 $\frac{1}{5}$。注意，不同的歌曲可能有相同的时长。

由 ChatGPT 4.1 翻译