#2541. 「PKUWC2018」猎人杀

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: l0nl1f3

题目描述

猎人杀是一款风靡一时的游戏“狼人杀”的民间版本,他的规则是这样的:

一开始有 nn 个猎人,第 ii 个猎人有仇恨度 wiw_i ,每个猎人只有一个固定的技能:死亡后必须开一枪,且被射中的人也会死亡。

然而向谁开枪也是有讲究的,假设当前还活着的猎人有 [i1im][i_1\ldots i_m],那么有 wikj=1mwij\frac{w_{i_k}}{\sum\limits_{j = 1}^{m} w_{i_j}} 的概率是向猎人 iki_k 开枪。

一开始第一枪由你打响,目标的选择方法和猎人一样(即有 wij=1nwj\frac{w_i}{\sum\limits_{j=1}^{n}w_j} 的概率射中第 ii 个猎人)。由于开枪导致的连锁反应,所有猎人最终都会死亡,现在 11 号猎人想知道它是最后一个死的的概率。

答案对 998244353998244353 取模。

输入格式

第一行一个正整数nn

第二行nn个正整数,第ii个正整数表示wiw_i

输出格式

输出答案。

样例

样例输入

3
1 1 2

样例输出

915057324

样例解释

答案是24×12+14×23=1024\frac{2}{4}\times \frac{1}{2}+\frac{1}{4}\times \frac{2}{3}=\frac{10}{24}

数据范围与提示

对于10%10\%的数据,有1n101\leq n\leq 10

对于30%30\%的数据,有1n201\leq n\leq 20

对于50%50\%的数据,有1i=1nwi50001\leq \sum\limits_{i=1}^{n}w_i\leq 5000

另有10%10\%的数据,满足1wi21\leq w_i\leq 2,且w1=1w_1=1

另有10%10\%的数据,满足1wi21\leq w_i\leq 2,且w1=2w_1=2

对于100%100\%的数据,有wi>0w_i>0,且1i=1nwi1000001\leq \sum\limits_{i=1}^{n}w_i \leq 100000