猎人杀题解

题解

---

题意:

$n$个人随机开枪,每个人中弹的概率不同,由1号开始开枪,问1号活到最后地概率

solution

考虑容斥,不合法的答案是有一些数在1之后才被删除

定义全集$A=\{2,3,...,n\}$,以及令$sum=\displaystyle\sum\limits_{i=1}^n\omega_i$

那么我们很容易得到这样一个不合法概率的式子:

$$\begin{aligned} &\displaystyle\sum\limits_{S\subset A}\displaystyle\sum\limits_{i=0}^{\infty}(-1)^{|S|}\left(\cfrac{sum-\omega_1-\displaystyle\sum\limits_{x\in S}\omega_x}{sum}\right)^i\cfrac{\omega_1}{sum}\\ &=\cfrac{\omega_1}{sum}\displaystyle\sum\limits_{S\subset A}(-1)^{|S|}\displaystyle\sum\limits_{i=0}^{\infty}\left(\cfrac{sum-\omega_1-\displaystyle\sum\limits_{x\in S}\omega_x}{sum}\right)^i\\ \end{aligned}$$

而我们知道:

$$1+x+x^2+...+x^{n-1}+x^n+...=\frac{1}{x-1}$$

所以我们可以得到:

$$\begin{aligned} &\cfrac{\omega_1}{sum}\displaystyle\sum\limits_{S\subset A}(-1)^{|S|}\displaystyle\sum\limits_{i=0}^{\infty}\left(\cfrac{sum-\omega_1-\displaystyle\sum\limits_{x\in S}\omega_x}{sum}\right)^i\\ &=\cfrac{\omega_1}{sum}\displaystyle\sum\limits_{S\subset A}(-1)^{|S|}\frac{1}{\cfrac{sum-\omega_1-\displaystyle\sum\limits_{x\in S}\omega_x}{sum}-1}\\ &=-\cfrac{\omega_1}{sum}\displaystyle\sum\limits_{S\subset A}(-1)^{|S|}\frac{sum}{\omega_1+\displaystyle\sum\limits_{x\in S}\omega_x}\\ \end{aligned}$$

我们考虑套路地更换枚举顺序:

$$-\cfrac{\omega_1}{sum}\displaystyle\sum\limits_{S\subset A}(-1)^{|S|}\frac{sum}{\omega_1+\displaystyle\sum\limits_{x\in S}\omega_x}\\ =-\cfrac{\omega_1}{sum}\displaystyle\sum\limits_{x=1}^{sum-\omega_1}\frac{sum}{\omega_1+x}\displaystyle\sum\limits_{S\subset A}(-1)^{|S|}[\displaystyle\sum\limits_{u\in S}\omega_u==x]\\ =-\displaystyle\sum\limits_{x=1}^{sum-\omega_1}\frac{\omega_1}{\omega_1+x}\displaystyle\sum\limits_{S\subset A}(-1)^{|S|}[\displaystyle\sum\limits_{u\in S}\omega_u==x] \tag{1}$$

我们考虑后面地这个东西应该如何计算,不妨考虑他的生成函数:

$$F(x)=\displaystyle\prod_{i=2}^n(1-x^{\omega_i})\tag{2}$$

对于某个数$i$,$1$表示不选这个数,而$x^{\omega_i}$表示选这个数,那么我们所要的式子就是:

$$\displaystyle\sum\limits_{S\subset A}(-1)^{|S|}[\displaystyle\sum\limits_{u\in S}\omega_u==x]=[x^n]F(x)$$
我们观察数据范围,发现(1)可以直接暴力乘法得到,所以我们只需要考虑(2)式.

(2)式的处理我们考虑一个分治,并不是分治fft,只是单纯地每次将其分成两部分,再将两部分合并

所以我们要的答案就是:

$$1+\displaystyle\sum\limits_{x=1}^{sum-\omega_1}\frac{\omega_1}{\omega_1+x}\displaystyle\sum\limits_{S\subset A}(-1)^{|S|}[\displaystyle\sum\limits_{u\in S}\omega_u==x]$$
代码被我卡常卡地没有可读性/kk 就贴个剪贴板吧(