[LOJ2541]猎人杀

好题==

先转化一下，每个人被杀死后给他打标记，以后随机杀人时选到有标记的人就继续随机，这样并不会改变每个人被杀死的概率

直接算很难算，考虑容斥，我们枚举$S$表示在$1$死后才死的人至少在集合$S$中，并设$A=\sum\limits_{i=2}^nw_i$，那么它对答案的贡献为$(-1)^{|S|}\sum\limits_{i\geq0}\left(1-\frac{w_1+\sum\limits_{x\in S}w_x}A\right)^i\frac{w_1}A=(-1)^{|S|}\frac{w_1}{w_1+\sum\limits_{x\in S}w_x}$

所以答案为$\sum\limits_{1\notin S}(-1)^{|S|}\frac{w_1}{w_1+\sum\limits_{x\in S}w_x}$

直接算不太好算，但因为$\sum\limits_iw_i\leq10^5$，所以我们考虑对每个不同的$t=\sum\limits_{x\in S}w_x$算出容斥系数之和，容易得出$t=[x^t]\prod\limits_{i=2}^n1-x^{w_i}$，然后就可以直接算了

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mod=998244353;
int mul(int a,int b){return(ll)a*b%mod;}
int ad(int a,int b){return(a+b)%mod;}
int de(int a,int b){return(a-b)%mod;}
int pow(int a,int b){
	int s=1;
	while(b){
		if(b&1)s=mul(s,a);
		a=mul(a,a);
		b>>=1;
	}
	return s;
}
int rev[131072],N,iN;
void pre(int n){
	int i,k=0;
	for(N=1,k=0;N<=n;N<<=1)k++;
	for(i=0;i<N;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
	iN=pow(N,mod-2);
}
void ntt(int*a,int on){
	int i,j,k,t,w,wn;
	for(i=0;i<N;i++){
		if(i<rev[i])swap(a[i],a[rev[i]]);
	}
	for(i=2;i<=N;i<<=1){
		wn=pow(3,on==1?(mod-1)/i:mod-1-(mod-1)/i);
		for(j=0;j<N;j+=i){
			w=1;
			for(k=0;k<i>>1;k++){
				t=mul(a[i/2+j+k],w);
				a[i/2+j+k]=de(a[j+k],t);
				a[j+k]=ad(a[j+k],t);
				w=mul(w,wn);
			}
		}
	}
	if(on==-1){
		for(i=0;i<N;i++)a[i]=mul(a[i],iN);
	}
}
int ta[131072],tb[131072];
void conv(int*a,int n,int*b,int m,int*c){
	pre(n+m);
	memset(ta,0,N<<2);
	memcpy(ta,a,(n+1)<<2);
	memset(tb,0,N<<2);
	memcpy(tb,b,(m+1)<<2);
	ntt(ta,1);
	ntt(tb,1);
	for(int i=0;i<N;i++)ta[i]=mul(ta[i],tb[i]);
	ntt(ta,-1);
	memcpy(c,ta,(n+m+1)<<2);
}
int w[100010],s[100010];
int*solve(int l,int r){
	int*res,mid;
	res=new int[s[r]-s[l-1]+1];
	if(l==r){
		memset(res,0,(w[l]+1)<<2);
		res[0]=1;
		res[w[l]]=-1;
		return res;
	}
	mid=(l+r)>>1;
	conv(solve(l,mid),s[mid]-s[l-1],solve(mid+1,r),s[r]-s[mid],res);
	return res;
}
int inv[100010];
int main(){
	int n,i,*p,ans;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",w+i);
		s[i]=s[i-1]+w[i];
	}
	p=solve(2,n);
	inv[1]=1;
	for(i=2;i<=s[n];i++)inv[i]=-mul(mod/i,inv[mod%i]);
	ans=0;
	for(i=0;i<=s[n]-w[1];i++)(ans+=(ll)p[i]*w[1]%mod*inv[i+w[1]]%mod)%=mod;
	printf("%d",(ans+mod)%mod);
}

巴特西

[LOJ2541]猎人杀

最新文章

热门文章