分数: 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