随机播放列表中特定歌曲的概率问题
/n/n /n
/n/n问题
高桥君有一个由N首歌曲组成的播放列表。/n第i首歌曲（1 /leq i /leq N）的长度为T_i秒。
/n高桥君在时刻0开始随机播放播放列表。
随机播放是指从N首歌曲中以相等的概率选择一首歌曲并播放至结束，然后不间断地播放下一首歌曲。/n同时，可能会连续选择同一首歌曲。
/n请计算从时刻0到(X+0.5)秒后，播放的是第1首歌曲的概率，并对/text{mod}998244353取模。
/n/n
/n/n/text{mod } 998244353概率的定义
/n/n可以证明，在这个问题中所求的概率一定是有理数。/n并且，在该问题的约束条件下，当将所求概率表示为既约分数/frac{y}{x}时，保证x不能被998244353整除。
/n此时，满足xz /equiv y /pmod{998244353}的0至998244352之间的整数z是唯一确定的。请输出这个z。
/n/n/n /n
/n/n约束
- /n
- 2 /leq N/leq 10^3 /n
- 0 /leq X/leq 10^4 /n
- 1 /leq T_i/leq 10^4 /n
- 输入均为整数 /n
/n
/n
/n/n/n/n /n
/n/n输入
输入以以下格式从标准输入中给出：
/nN X/nT_1 T_2 /ldots T_N/n/n
/n/n /n
/n输出
输出从时刻0到(X+0.5)秒后，播放列表的第1首歌曲的概率，并对/text{mod}998244353取模。
/n/n
/n/n /n
/n/n输入例子1
3 6/n3 5 6/n/n
/n/n /n
/n/n输出例子1
369720131/n/n
从时刻0到6.5秒后，第1首歌曲播放的可能情况有：
/n- /n
- 曲目1 /to 曲目1 /to 曲目1 /n
- 曲目2 /to 曲目1 /n
- 曲目3 /to 曲目1 /n
以上三种情况的发生概率均为/frac{7}{27}。
/n由于369720131/times 27/equiv 7 /pmod{998244353}，因此输出369720131。
/n
/n/n /n
/n/n输入例子2
5 0/n1 2 1 2 1/n/n
/n/n /n
/n/n输出例子2
598946612/n/n
从时刻0到0.5秒后，最初播放的是第一首歌曲，因此所求概率为/frac{1}{5}。
/n请注意，存在不同长度的相同歌曲。
/n
/n/n /n
/n/n输入例子3
5 10000/n1 2 3 4 5/n/n
/n/n /n
输出例子3
586965467/n
原文地址: https://www.cveoy.top/t/topic/o9vO 著作权归作者所有。请勿转载和采集!