#LX0023. 音乐播放器

音乐播放器

题目描述

赵喜娜有一个音乐播放器(赛后回家看)。

他的音乐播放器里面一共有nn首歌,赵喜娜对第ii首歌的喜爱程度是aia_i

赵喜娜今天选择了随机播放模式,具体地:

他的播放器会随机播放一首歌,等这首歌结束后,会继续随机播放下一首歌(不排除这首歌跟刚那首歌一样的可能性)。

当赵喜娜首次听到第ii首歌的时候,他的愉悦程度会增加aia_i,第二次及以后听到,则没有反应了。

当赵喜娜听完某首歌后,总的愉悦程度S\geq S,赵喜娜就会开心的关掉播放器,完成今天的听歌。

问:赵喜娜听到的最后一首歌是第ii首歌的概率是多少?

可以证明结果一定可以被化简为一个分数xy\frac{x}{y},你需要输出x/ymod998244353x/y \mod 998244353

提示:解此题的时候也许你可能不得不在 mod p\ mod \ p意义下除以一个数字(此处pp是质数),那么你就需要逆元这个东西。

如果你不会逆元的话,简单介绍一下逆元:

假设你现在需要求x/ymod px/y\mod \ p的结果,比如35/3mod73*5/3\mod 7,如果你直接每步mod 7mod\ 7计算的话,答案是(35%7)/3%7=0(3*5\%7)/3 \% 7=0。但实际上结果显然是55

所以你需要更高级的东西,费马小定理:假设有质数pp以及非负整数a<pa<p,那么ap1%p=1a^{p-1}\%p=1。也就是说,ap1a^{p-1}实际上就是mod p\mod\ p意义下的数字11

那么x/ymodpx/y\mod p就可以写成x×yp1/ymodpx\times y^{p-1}/y\mod p。反正乘以11等于没乘对吧。

也就是说,我们如果要/y/y的话,可以当成要乘以yp2y^{p-2}

yp2y^{p-2}就是yymodp\mod p意义下的逆元

输入格式

第一行输入n,Sn,S

接下来一行输入nn个正整数表示aia_i

输出格式

nn个数字表示答案。

样例输入 #1

4 3
1 2 3 4

样例输出 #1

582309206 582309206 915057324 915057324

样例解释 #1

想要以22结尾或者以11结尾,赵喜娜必须只听到歌11和歌22

那么听歌序列只能是111112111112或者是222221222221这样。

1212的概率是142\frac{1}{4}^2

112112的概率是143\frac{1}{4}^3

11121112的概率是144\frac{1}{4}^4

...

所以最终以22结尾的概率是116114=112\frac{\frac{1}{16}}{1-\frac{1}{4}}=\frac{1}{12}

11结尾的概率同样是112\frac{1}{12}

112\frac{1}{12}modp\mod p意义下是1×12p2=5823092061\times 12^{p-2}=582309206

3344结尾的概率一样,都是512\frac{5}{12}

样例输入 #2

4 7
1 2 3 4

样例输出 #2

582309206 582309206 748683265 83187030

数据范围

对于15%的数据:n8,S10n\leq 8,S\leq 10

对于40%的数据:n20,S100n\leq 20,S\leq 100

对于60%的数据:n20n\leq 20

对于另10%的数据:aia_i只有两种取值。

对于85%的数据:n100,S1000n\leq 100,S\leq 1000

对于100%的数据:$n\leq 100,S\leq 10000,1\leq a_i\leq S,\sum a_i \geq S$。