盒子
盒子
文章目录
  1. 题目描述
  2. 题解

【loj 2541】「PKUWC2018」猎人杀

题目链接

题目描述

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

一开始有 $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$ 一下就好了

支持一下
扫一扫,支持nekko
  • 微信扫一扫