题解-PKUWC2018 猎人杀

Problem

loj2541

题意概要：给定 \(n\) 个人的倒霉度 \(\{w_i\}\)，每回合会有一个人死亡，每个人这回合死亡的概率为 自己的倒霉度/目前所有存活玩家的倒霉度之和，求第 \(1\) 个人最后一个死亡的概率

Solution

设 \(B = \sum_{i=2}^nw_i\)

要求 \(1\) 号最后一个被选中有点不好做，但是求 \(1\) 号第一个被选中还是比较好做的（\(\frac {w_1}{\sum_{i=1}^nw_i}\)）

至于这两者怎么联系起来，使用 \(\mathrm {min-max}\) 容斥（和 HAOI2015按位或 有点像：前者是求 \(1\) 号最后一个被选中的概率；后者是求集合内最后一个被选中的期望次数）

\(\mathrm{min-max}\) 容斥的式子为：

\[\max\{S\}=\sum_{T\subseteq S}(-1)^{|T|-1}\min\{T\} \]

由于 \(1\) 为需要求的点，将其从 \(S,T\) 的定义中刨除，即

\[\max\{S\}=\sum_{T\subseteq S}(-1)^{|T|}\min\{T\} \]

而同时

\[\min\{T\}=\frac {w_1}{w_1+\sum_{x\in T}w_i} \]

发现 \(\min\{T\}\) 最多有 \(B\) 种，可以考虑计算出每一项的容斥系数再 \(O(B)\) 计算

至于计算容斥系数，可使用母函数求得，即求出下面式子的每一项系数：

\[\prod_{i=2}^n(1-x^{w_i}) \]

分治 ntt 求解，每一层母函数度数和为 \(B\)，复杂度 \(O(B\log B)\)，总复杂度 \(O(B\log^2B)\)

Code

#include 
using namespace std;
typedef long long ll;

inline void read(int&x){
	char ch=getchar();x=0;while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
}

const int N = 200200, T = 37, p = 998244353;
int stk[T], tp;
int brr[T][N], L[T];
int w[N], rev[N];

inline int qm(const int&x) {return x < p ? x : x - p;}
inline int qpow(int A, int B) {
	int res = 1; while(B) {
		if(B&1) res = (ll)res * A%p;
		A = (ll)A * A%p, B >>= 1;
	} return res;
}

void dft(int*a,int n,int sgn) {
	for(int i=1;i>1]>>1) | ((i&1) << l-1);
	dft(ar, nn, 1), dft(br, nn, 1);
	for(int i=0;i> 1;
	int ls = binary(l, mid), rs = binary(mid+1, r);
	int id = stk[--tp]; mul(ls, rs, id);
	stk[tp++] = ls, stk[tp++] = rs;
	return id;
}

int main() {
	for(int i=0;i