「PKUWC2018」LOJ #2541. 猎人杀 - 容斥 - 分治NTT

题目大意：给你$n$个球，每个球有个权重$w_i$，每次加权扔掉一个球，问最后一号球是最后一个被扔出去的概率。${\sum }_{i=1}^n{w}_i\le 10^5,\forall i\in [1,n],w_i>0$。
题解：
首先考虑容斥（本质上是$Min-Max$容斥，即要求其为全集的最大值，可以通过要求其为全集的子集的最小值来容斥），容斥至少$S$这个集合中的球在$1$号之后被扔掉的概率$\alpha (S)$，那么答案是
$$\sum _S(-1{)}^{|S|}\alpha (S)$$
考虑$\alpha (S)$怎么算，我们可以如此转化：每次随机选择一个球，若其被选择过了，就忽略不计。可以感性理解这样做和原来选择一个就扔掉一个是本质相同的。那么要求$1$在$S$之前出现，等价于，若枚举其是第$i+1$个出现的，则前面选择（注意这里不是出现）的都不是 S ⋃ { 1 } Sbigcup{1} S⋃{1}的元素，即：
$$\alpha (S)=\sum _{i\ge 0}{\left(1-\frac{A+w_1}{W}\right)}^i\frac{w_1}{W}=\frac{W}{A+w_1}\frac{w_1}{W}=\frac{w_1}{A+w_1}$$
其中$$W=\sum _{i=1}^n{w}_i,A=\sum _{x\in S}{w}_x$$
注意到$W\le 10^5$，使用分治NTT计算$A$固定时的容斥系数即可。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#define gc getchar()
#define pb push_back
#define lint long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define clr(a,n) memset(a,0,sizeof(int)*(n))
#define p 998244353
#define N 100010
#define debug(x) cerr<<#x<<"="<<x
#define sp <<" "
#define ln <<endl
using namespace std;
inline int inn()
{
	int x,ch;while((ch=gc)<'0'||ch>'9');
	x=ch^'0';while((ch=gc)>='0'&&ch<='9')
		x=(x<<1)+(x<<3)+(ch^'0');return x;
}
vector<int> v[N];int w[N],r[N<<2],a[N<<2],b[N<<2];
inline int fast_pow(int x,int k,int ans=1)
{	for(x%=p;k;k>>=1,x=(lint)x*x%p) (k&1)?ans=(lint)ans*x%p:0;return ans;	}
inline int NTT(int *a,int n,int s)
{
	for(int i=1;i<n;i++) if(i<r[i]) swap(a[i],a[r[i]]);
	for(int i=2;i<=n;i<<=1)
	{
		int wn=fast_pow(3,s>0?(p-1)/i:p-1-(p-1)/i);
		for(int j=0,t=i>>1;j<n;j+=i) for(int k=0,w=1,x,y;k<t;k++,w=(lint)w*wn%p)
			x=a[j+k],y=(lint)w*a[j+k+t]%p,((a[j+k]=x+y)>=p?a[j+k]-=p:0),((a[j+k+t]=x-y)<0?a[j+k+t]+=p:0);
	}
	if(s<0) for(int i=0,ninv=fast_pow(n,p-2);i<n;i++) a[i]=(lint)a[i]*ninv%p;return 0;
}
inline int tms(vector<int> &A,vector<int> &B,vector<int> &C)
{
	int m1=(int)A.size(),m2=(int)B.size(),n=1,L=0;
	while(n<m1+m2-1) n<<=1,L++;
	rep(i,1,n-1) r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));
	rep(i,0,m1-1) a[i]=A[i];clr(a+m1,n-m1),NTT(a,n,1);
	rep(i,0,m2-1) b[i]=B[i];clr(b+m2,n-m2),NTT(b,n,1);
	rep(i,0,n-1) a[i]=(lint)a[i]*b[i]%p;NTT(a,n,-1);
	C.resize(m1+m2-1);rep(i,0,m1+m2-2) C[i]=a[i];return 0;
}
inline int solve(int l,int r)
{
	if(l==r) return v[l].resize(w[l]+1,0),v[l][0]=1,v[l][w[l]]=p-1;int mid;
	return mid=(l+r)>>1,solve(l,mid),solve(mid+1,r),tms(v[l],v[mid+1],v[l]);
}
int main()
{
	int n=inn(),s=0;lint ans=0;
	if(n==1) return !printf("1n");
	rep(i,1,n) w[i]=inn(),s+=(i>1)*w[i];solve(2,n);
	rep(i,0,s) ans+=(lint)v[2][i]*fast_pow(i+w[1],p-2)%p;
	return !printf("%lldn",ans%p*w[1]%p);
}

最后

以上就是微笑茉莉为你收集整理的「PKUWC2018」LOJ #2541. 猎人杀 - 容斥 - 分治NTT的全部内容，希望文章能够帮你解决「PKUWC2018」LOJ #2541. 猎人杀 - 容斥 - 分治NTT所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。