description

有$n$个猎人，每个猎人有一个仇恨度$w_i$，每个猎人死后会开一枪打死一个还活着的猎人，打中每个猎人的概率与他的仇恨度成正比。

现在你开了第一枪，打死每个猎人的概率同样也和它的仇恨度成正比。现在第一个猎人想知道他最后一个死的概率。

$w_i>0,\sum w_i\le10^5$，模$998244353$

sol

容斥，考虑强制某个集合内的猎人在一号猎人之后被打死，剩下的猎人无所谓。

设这个集合内的猎人的仇恨度之和是$W$,所有猎人的仇恨度之和是$Sum$，那么这个集合对答案的贡献就是：$$\sum_{i=0}i\frac{w_1}{Sum}=\frac{w_1}{W+w_1}$$

我们可以把“在剩下还活着的人中选一个打死”改为“在所有人中选一个打，直至打到一个活着的人”，这样每个人被打到的概率就始终都是$\frac{w_i}{Sum}$，只不过开枪次数就没有了上限。不过显然这个无限等比数列是很容易进行求和的。

所以上面的式子的意思是：枚举前$i$枪都没有打中一号猎人和选中集合中的猎人，而接下来一枪刚好把一号猎人打死的概率。

于是现在关键在于枚举集合。我们发现对于$W$相同的集合可以一起计算，而$W$不同的集合至多只有$O(n)$个，所以可以枚举$W$，计算有多少个集合的仇恨度之和为$W$。这里同时也要乘上容斥系数$1$或$-1$。

其实要计算的就是一个这样的东西：$$\prod_{i=2}{w_i}$$

所以直接分治$NTT$就行了。

code

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int gi(){

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

const int N = 4e5+5;

const int mod = 998244353;

int n,w[N],s[N],inv[N],tmp[50][N],Stack[50],top,rev[N],og[N],ans;

inline void add(int &x,int y){x+=y;if(x>=mod)x-=mod;}

inline int fastpow(int a,int b){

	int res=1;

	while(b){if(b&1)res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}

	return res;

}

void ntt(int *P,int opt,int len){

	int l=0;while((1<<l)<len)++l;--l;

	for (int i=0;i<len;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<l);

	for (int i=0;i<len;++i) if (i<rev[i]) swap(P[i],P[rev[i]]);

	for (int i=1;i<len;i<<=1){

		int W=fastpow(3,(mod-1)/(i<<1));

		if (opt==-1) W=fastpow(W,mod-2);

		og[0]=1;for (int j=1;j<i;++j) og[j]=1ll*og[j-1]*W%mod;

		for (int p=i<<1,j=0;j<len;j+=p)

			for (int k=0;k<i;++k){

				int x=P[j+k],y=1ll*og[k]*P[j+k+i]%mod;

				P[j+k]=(x+y)%mod;P[j+k+i]=(x-y+mod)%mod;

			}

	}

	if (opt==-1) for (int i=0,Inv=fastpow(len,mod-2);i<len;++i) P[i]=1ll*P[i]*Inv%mod;

}

void solve(int *P,int l,int r){

	if (l==r) {P[0]=1;P[w[l]]=mod-1;return;}

	int mid=l+r>>1,ls=Stack[top--];

	solve(tmp[ls],l,mid);

	int rs=Stack[top--];

	solve(tmp[rs],mid+1,r);

	int len=1;while(len<=s[r]-s[l-1])len<<=1;

	ntt(tmp[ls],1,len);ntt(tmp[rs],1,len);

	for (int i=0;i<len;++i) P[i]=1ll*tmp[ls][i]*tmp[rs][i]%mod;

	ntt(P,-1,len);

	Stack[++top]=ls;Stack[++top]=rs;

	for (int i=0;i<len;++i) tmp[ls][i]=tmp[rs][i]=0;

}

int main(){

	n=gi();inv[0]=inv[1]=1;

	for (int i=1;i<=n;++i) w[i]=gi(),s[i]=s[i-1]+w[i];

	for (int i=2;i<=s[n];++i) inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;

	for (int i=1;i<50;++i) Stack[++top]=i;

	solve(tmp[0],2,n);

	for (int i=0;i<=s[n]-s[1];++i) add(ans,1ll*w[1]*inv[i+w[1]]%mod*tmp[0][i]%mod);

	printf("%d\n",ans);

	return 0;

}

猎人

[LOJ2541]「PKUWC2018」猎人杀

description

sol

code