← 返回题目列表

AtCoder · abc323_e

H. 播放列表

中文机器翻译题面 查看原题

分数: 450 点

问题陈述

Takahashi 有一个播放列表 N 歌曲。 宋 i (1 \leq i \leq N) 持续 T_i 秒。
Takahashi 已开始随机播放播放列表 0.

随机播放重复以下内容:从歌曲中选择一首 N 歌曲具有相同的概率,并将该歌曲播放到底。 在这里,歌曲是连续播放的:一旦一首歌曲结束,下一首选择的歌曲立即开始。 可以连续选择同一首歌曲。

求这首歌的概率 1 正在播放 (X + 0.5) 时间后的秒数 0,模数 998244353.

如何打印概率模数 998244353

可以证明,在这个问题中找到的概率总是有理数。 另外,这个问题的约束保证了当要找到的概率表示为不可约分数时 \frac{y}{x}, x 不能被整除 998244353.

那么,有一个唯一的整数 z 之间 0 和 998244352,包含在内,这样 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

输出

打印概率,模数 998244353,正在播放播放列表中的第一首歌曲 (X+0.5) 时间后的秒数 0.


样本输入 1

3 6
3 5 6

示例输出 1

369720131

歌曲 1 即将播放 6.5 时间后的秒数 0 如果歌曲按以下顺序之一播放。

  • 歌曲 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.5 时间后的秒数 0,第一首要播放的歌曲仍在播放,所以求的概率为 \frac{1}{5}.
请注意,不同的歌曲可能具有相同的长度。


示例输入 3

5 10000
1 2 3 4 5

示例输出 3

586965467