设 \(s = \sum\limits_{i=1}^n w_i\)。
首先考虑转化一下题意：将第 \(i\) 个猎人被射中的概率固定为 \(\frac{w_i}{s}\)，并允许放空枪。
容易证明这样得到的答案是不变的。
于是容斥，钦点一部分猎人强制在 \(1\) 之后被打中。
有答案等于 \[
\begin{aligned}
& \sum\limits_{S \subseteq \{2,\dots,n\}} (-1)^{|S|} \sum\limits_{i=0}^{\infty} \left(\frac{s - w_1 - \sum_{k\in S} w_k}{s}\right)^i \frac{w_1}s \\
=& \sum\limits_{S \subseteq \{2,\dots,n\}} (-1)^{|S|} \frac{w_1}s \cdot \frac{s}{w_1+\sum_{k\in S}w_k} \\
=& \sum\limits_{S \subseteq \{2,\dots,n\}} \frac{(-1)^{|S|} w_1}{w_1 + \sum_{k\in S} w_k} \\
=& \sum\limits_{i=0}^{s-w_1} \frac{w_1}{w_1+i} [x^i] \prod\limits_{k=2}^n (1-x^{w_k})
\end{aligned}
\]
分治 NTT 即可。
时间复杂度 \(O(n \log^2 n)\)。
代码：
1 |
|