DTOJ#4170. 「PKUWC2018」猎人杀

本文主要是介绍DTOJ#4170. 「PKUWC2018」猎人杀，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

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

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

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

一开始第一枪由你打响，目标的选择方法和猎人一样（即有 $\frac{w_i}{\sum _{j=1}^n{w}_j}$ 的概率射中第 $i$ 个猎人）。由于开枪导致的连锁反应，所有猎人最终都会死亡，现在 $1$ 号猎人想知道它是最后一个死的的概率。

答案对 $998244353$ 取模。
题解：
考虑对于每一次开枪，要知道当前存活的人，才能知道概率，这样需要状压记录状态，显然不可行。于是考虑是否能将每次开枪看作可以选所有人，这样要考虑若选到已死的人，肯定不能照常，而是要继续选，直到选到未死的，这样就和原来的操作一样了。对于计算1号最后死的概率，直接算肯定不好算，故考虑容斥掉不合法的概率，枚举在它后面死的至少有i人，设$\sum _{i=1}^n{w}_i=A$,i后面死的人的w和为s，于是有：$ans=\sum _{i=1}^n(-1{)}^i\ast \frac{w_1}{A}\ast \sum _{j=0}^{\infty }\frac{A-s-w_1}{A}$，化简得$\sum _{i=1}^n(-1{)}^i\ast \frac{1}{s+w_1}$，发现式子的变量是s，又注意到数据范围，A<=1e5,考虑对于每一个相同的s，计算出它的容斥系数，于是就按套路，对于每一个猎人，将其看成一个多项式$x^{w_i}-1$，所有猎人卷积的每一项系数即是s的容斥系数，分治NTT求解即可。

这篇关于DTOJ#4170. 「PKUWC2018」猎人杀的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---