题目描述

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

一开始有 $n$ 个猎人，第 $i$ 个猎人有仇恨度 $w_i$ ，每个猎人只有一个固定的技能：死亡后必须开一枪，且被射中的人也会死亡

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

一开始第一枪由你打响，目标的选择方法和猎人一样（即有 $\frac{w_i}{\sum\limits_{j=1}^{n}w_j}$ 的概率射中第 $i$ 个猎人）

由于开枪导致的连锁反应，所有猎人最终都会死亡，现在 $1$ 号猎人想知道它是最后一个死的的概率

答案对 $998244353$ 取模

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

题解

不妨对于每一个猎人，如果他死亡后不要把他移除游戏，而是如果在某次选择到他的时候就再选择一次，直到选择了一个存活的猎人

设 $A$ 为总人数的 $w$ 的和，$B$ 为已经死亡的人数的 $w$ 的和，$P$ 为选择一个权值为 $w$ 的存活的人的概率，显然 $P=\frac{w}{A-B}$

如果用上面那个做法来计算概率，有：

$$
P=\frac{B}{A}P+\frac{w}{A} \Rightarrow P=\frac{w}{A-B}
$$

于是这个模型是一个完全等价的

考虑容斥，设 $f(S)$ 表示 $S$ 中的人比 $1$ 后死亡的概率，设 $x=\sum_{y \in S} w_y$，则：

$$
\begin{aligned}
f(S)
&=(-1)^{|S|}\sum_{i=0}^{\infty} (1-\frac{x+w_1}{A})^{i}\frac{w_1}{A} \\
&=(-1)^{|S|} \frac{1}{1-(1-\frac{x+w_1}{A})} \frac{w_1}{A} \\
&=(-1)^{|S|}\frac{w_1}{w_1+x} \\
\end{aligned}
$$

于是只需要计算 $g(x)$ 表示权值和为 $x$ 时，$(-1)^{|S|}$ 的和即可

相当于一个背包问题，每个物品有权值 $w$，每次选择一个贡献 $-1$ 的系数

也就是说每个物品看作 $1-x^{w}$，它们卷积起来就行了，即 $\prod_{i=2}^{n}(1-x^{w_{i}})$

分治 $fft$ 一下就好了