好题分享（P5644 [PKUWC2018]猎人杀）

P5644 [PKUWC2018]猎人杀

P5644 [PKUWC2018]猎人杀

题目大意

一开始有$n$个猎人，第$i$个猎人有仇恨度$w_i$。每次可以开枪射杀一个活着的猎人。

假设活着的猎人为$i_1,i_2,\dots ,i_m$，则第$i_k$个猎人被射杀的概率是$\frac{w_{i_k}}{\sum _{j=1}^m{w}_{i_j}}$。

求$1$号猎人最后一个被射杀的概率。输出答案对$998244353$取模。

对于 $10\%$ 的数据，有 $1\le n\le 10$

对于 $30\%$ 的数据，有 $1\le n\le 20$

对于 $50\%$ 的数据，有 $1\le \sum _{i=1}^n{w}_i\le 5000$

另有 $10\%$ 的数据，满足 $1\le w_i\le 2$，且 $w_1=1$

另有 $10\%$ 的数据，满足 $1\le w_i\le 2$，且 $w_1=2$

对于 $100\%$ 的数据，有 $w_i>0$，且 $1\le \sum _{i=1}^n{w}_i\le 10^5$

题解

10pts

枚举所有情况并计算概率，时间复杂度为$O(n!)$，可以过$1\le n\le 10$的部分分。

30pts

在不断射杀的过程中，概率的分母会不断改变。所以，我们可以稍微转化一下题意。

令$sum=\sum _{i=1}^n{w}_i$，题意转化为：第$i$个人被射杀的概率为$\frac{w_i}{sum}$，已经被射杀的人仍能继续被射杀。如果打中一个活着的人，那么这个人就死去。

为什么呢？因为在每次射杀的时候，每个活人被射杀的概率都他的仇恨度除以所有活人仇恨度的和。这样相对于原来，多了一个射杀死人的过程，但因为活人最终总会被射杀，所以本质上是一样的。

直接求$1$号最后被射杀的概率比较困难，我们考虑使用容斥。

设在$1$号之后被射杀的人的子集为$S$的概率为$p(S)$，则答案为

$$ans=\sum (?1{)}^{|S|}p(S)$$

然后，我们考虑如何求$p(S)$。

设$v(S)=\sum _{i\in S}{w}_i$。因为在$1$号之后被射杀的人包含$S$，所以就相当于射杀若干次，每次射杀除了$1$号和集合$S$之外的人，直到打中$1$号。

$$p(S)=\sum _{i=0}^{+\infty }(\frac{sum?w_1?v(S)}{sum}{)}^i?\frac{w_1}{sum}$$

接下来求$\sum _{i=0}^{+\infty }(\frac{sum?w_1?v(S)}{sum}{)}^i$。由等比数列求和公式可得

$$\sum _{i=0}^{+\infty }(\frac{sum?w_1?v(S)}{sum}{)}^i=\frac{1?(\frac{sum?w_1?v(S)}{sum}{)}^{+\infty }}{1?\frac{sum?w_1?v(S)}{sum}}=\frac{1}{\frac{w_1+v(S)}{sum}}=\frac{sum}{w_1+v(S)}$$

所以

$$p(S)=\frac{sum}{w_1+v(S)}?\frac{w_1}{sum}=\frac{w_1}{w_1+v(S)}$$

那么

$$ans=\sum (?1{)}^{|S|}\frac{w_1}{w_1+v(S)}$$

枚举所有$S$来计算$ans$，时间复杂度为$O(2^n)$，可以过$1\le n\le 20$的部分分。

50pts

我们注意到$\sum _{i=1}^n{w}_i$的范围并不是很大，所以我们可以枚举$v(S)$。

令

$$g(i)=\sum _{v(S)=i}(?1{)}^{|S|}$$

那么

$$ans=\sum _{i=0}^{sum}g(i)?\frac{w_1}{w_1+i}$$

于是问题就转化为求$g(i)$了。我们可以用背包来$O(su{m}^2)$求出$g(i)$，这可以过$1\le \sum _{i=1}^n{w}_i\le 5000$的部分分。

另外20pts

有$20$分是满足$1\le w_i\le 2$且确定了$w_1$是$1$或者是$2$，这部分我不太清楚怎么做，留给大家思考。

100pts

我们考虑如何快速求出$g(i)$。我们发现，$g(i)$其实就是$\prod _{i=2}^n(1?x^{w_i})$的第$i$次项的系数。

接下来，我们要用$NTT$来求$\prod _{i=2}^n(1?x^{w_i})$。

用分治，求$[l,r]$的多项式时，先求出$[l,mid]$和$[mid+1,r]$的多项式，再将两个多项式相乘即可。

我们把求的过程看作$\log n$层，每层的时间复杂度为$O(sum\log sum)$，所以总时间复杂度为$O(sum\log sum\log n)$，可以看作$O(n{\log }^{2}n)$。