【LOJ2541】【PKUWC2018】猎人杀（容斥，FFT）

题面

题解

这题好神仙啊。

直接考虑概率很麻烦，因为分母总是在变化。

但是，如果一个人死亡之后，我们不让他离场，假装给他打一个标记（猎人印记？？？）

如果在一次选择的时候选中了一个已经被打过标记的人，那么我们就重新做一次选择。

这样显然没有任何影响。

现在考虑如何求第一个人最后一个被打上标记的概率。

我们容斥一下，枚举一下哪些人会在\(1\)之后被选择，那么容斥系数就是\((-1)\)的人数次方。

那么对于钦定的在\(1\)之后被选择的集合\(S\)，假设他们的\(w\)的和为\(S\)，所有人\(w\)的和为\(A\)。这个集合贡献的值就是\((-1)^{|S|}\sum_{i=1}^{\infty}(1-\frac{S+W_1}{A})^i\frac{W_1}{A}\)。后面的部分可以化简，结果就是\(\frac{W_1}{S+W_1}\)。

现在的问题就是求\(S\)了。

我们发现因为是一个分数的形式，如果直接计算显然是不能够直接\(dp\)。

换种思路，如果我们计算每一种分母分别出现了多少次，这个就非常好算了。

这样就可以通过\(dp\)计算，同时发现事实上这个\(dp\)就是一个\(01\)背包，所以可以用分治+\(NTT\)来优化计算。

时间复杂度\(O(nlogn^2)\)

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define MAX 250000

#define ll long long

#define MOD 998244353

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

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

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int fpow(int a,int b)

{

	int s=1;

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

	return s;

}

int n,w[MAX],ans;

int W[MAX],r[MAX];

void NTT(int *P,int len,int opt)

{

	int N,l=0;for(N=1;N<len;N<<=1)++l;

	for(int i=0;i<N;++i)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));

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

	for(int i=1;i<N;i<<=1)

	{

		int w=fpow(3,(MOD-1)/(i<<1));W[0]=1;

		for(int k=1;k<i;++k)W[k]=1ll*W[k-1]*w%MOD;

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

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

			{

				int X=P[j+k],Y=1ll*P[i+j+k]*W[k]%MOD;

				P[j+k]=(X+Y)%MOD;P[i+j+k]=(X+MOD-Y)%MOD;

			}

	}

	if(opt==-1)

	{

		reverse(&P[1],&P[N]);

		for(int i=0,inv=fpow(N,MOD-2);i<N;++i)P[i]=1ll*P[i]*inv%MOD;

	}

}

int tmp[50][MAX];

int S[MAX],top,P[MAX];

int Solve(int l,int r,int *P)

{

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

	int mid=(l+r)>>1,l1,l2,ls,rs,N;

	ls=S[top--];l1=Solve(l,mid,tmp[ls]);

	rs=S[top--];l2=Solve(mid+1,r,tmp[rs]);

	for(N=1;N<=l1+l2;N<<=1);

	NTT(tmp[ls],N,1);NTT(tmp[rs],N,1);

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

	NTT(P,N,-1);S[++top]=ls;S[++top]=rs;

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

	return l1+l2;

}

int main()

{

	n=read();

	for(int i=1;i<=n;++i)w[i]=read();

	for(int i=0;i<50;++i)S[++top]=i;

	int len=Solve(2,n,P);

	for(int i=0;i<=len;++i)ans=(ans+1ll*P[i]*fpow(w[1]+i,MOD-2))%MOD;

	ans=1ll*ans*w[1]%MOD;

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

	return 0;

}

巴特西

【LOJ2541】【PKUWC2018】猎人杀（容斥，FFT）

【LOJ2541】【PKUWC2018】猎人杀（容斥，FFT）

题面

题解

最新文章

热门文章