自动搬运

查看原文

来自洛谷，原作者为

	TheLostWeak **

搬运于2025-08-24 22:12:53，当前版本为作者最后更新于2019-12-20 10:26:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

在博客查看

大致题意： 有$n$个人相互开枪，每个人有一个仇恨度$a_i$，每个人死后会开枪再打死另一个还活着的人，且第一枪由你打响。设当前剩余人仇恨度总和为$k$，则每个人被打中的概率为$\frac {a_i}k$。求第$1$个人最后被打死的概率。

一个重要性质

对于这题，首先我们可以发现，由于一个人死后，其他人被打中概率的分母会受到影响，产生了后效性，似乎很不可维护。

因此我们需要知道一个重要性质：设$tot=\sum_{i=1}^na_i$，则题意可以转化为，每个人被打中的概率为$\frac{a_i}{tot}$，不断开枪直至打中一个还活着的人，则这个人就会死掉。

为什么这个正确呢？我口胡一下，应该是两种情况下，此时活着的人被打中的概率比都是仇恨度之比，是一样的。

容斥

知道了这个性质，这道题就可做的多了。

直接求$1$最后被打死的概率似乎不太容易，因此我们可以容斥一下。

设在$1$之后死掉的人至少包含点集$S$内所有人的概率为$p(S)$。

则答案就是：

$$ans=\sum(-1)^{|S|}p(S)$$

这里的容斥系数应该好理解吧，就是常见的偶数情况方案减去奇数情况方案。

设$sum(S)=\sum_{i∈S}a_i$，考虑如何求$p(S)$。

由于至少包含点集$S$内的所有人，那么其实就相当于无限开枪，每次可以打除点$1$和点集$S$外的任意点（仇恨度总和为$tot-a_1-sum(S)$），直至打中点$1$。

如果用一个式子表示，也就是：

$$p(S)=\sum_{i=0}^\infty(\frac{tot-a_1-sum(S)}{tot})^i\cdot\frac{a_1}{tot} $$

单独考虑$\sum_{i=0}^\infty(\frac{tot-a_1-sum(S)}{tot})^i$这一式子，由于$\frac{tot-a_1-sum(S)}{tot}$显然满足在$[0,1)$范围内，所以它的$\infty$次项是无限接近于$0$的。

所以我们可以用等比数列求和公式，得到：

$$\sum_{i=0}^\infty(\frac{tot-a_1-sum(S)}{tot})^i=\frac{(\frac{tot-a_1-sum(S)}{tot})^\infty-1}{\frac{tot-a_1-sum(S)}{tot}-1}=\frac{0-1}{\frac{tot-a_1-sum(S)}{tot}-1}=\frac{1}{1-\frac{tot-a_1-sum(S)}{tot}}=\frac{1}{\frac{a_1+sum(S)}{tot}}=\frac{tot}{a_1+sum(S)} $$

代回原式得到：

$$p(S)=\frac{tot}{a_1+sum(S)}\cdot\frac{a_1}{tot}=\frac{a_1}{a_1+sum(S)} $$

把$p(S)$代入$ans$便可得到：

$$ans=\sum(-1)^{|S|}\frac{a_1}{a_1+sum(S)}$$

此时的式子已经好求了许多，但似乎依旧不太好搞。

生成函数

看一下数据范围，我们发现题目中似乎特意指出，$\sum_{i=1}^na_i\le10^5$，肯定有猫腻！

再看一眼上面的式子，立刻就能想到枚举$sum(S)$！

如果设：

$$f(i)=\sum_{sum(S)=i}(-1)^{|S|}$$

那么显然答案就是：

$$ans=\sum_{i=0}^{tot}f(i)\frac{a_1}{a_1+i}$$

但$f(i)$怎么求呢？不难想到可以利用生成函数。

如果没有$(-1)^{|S|}$这个烦人的家伙，而只是简单的$\sum_{sum(S)=i}1$，我们不难想到，就是生成函数$\prod_{i=2}^n(1+x^{w_i})$第$i$次项的系数。

然而出现了$(-1)^{|S|}$，其实也并不会很难，其实就相当于生成函数$\prod_{i=2}^n(1-x^{w_i})$第$i$次项的系数。

而这个生成函数，我们可以用分治$NTT$来求出。

分治$NTT$

什么是分治$NTT$？

说起来是个很高大上的东西，但至少这道题的分治$NTT$，是很简单的。

考虑我们当前要把$[l,r]$范围内的多项式全部乘起来，那么我们可以递归求出$[l,mid]$和$[mid+1,r]$中多项式全部乘起来的结果，然后乘在一起，就是$[l,r]$范围内的多项式的乘积了。

代码

#include<bits/stdc++.h>
#define Tp template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define LN 20
#define X 998244353
#define Qinv(x) Qpow(x,X-2)
using namespace std;
int n,a[N+5],tot[N+5],f[4*N+5];
I int Qpow(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}
class FastIO
{
	private:
		#define FS 100000
		#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)
		#define tn (x<<3)+(x<<1)
		#define D isdigit(c=tc())
		char c,*A,*B,FI[FS];
	public:
		I FastIO() {A=B=FI;}
		Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);}
}F;
template<int SZ,int PR> class Poly//多项式算法，求解分治NTT
{
	private:
		int IPR,P,L,R[4*N+5],K,S[2*LN+5],g[2*LN+5][4*N+5];
		Tp I void T(Ty *s,CI op)
		{
			RI i,j,k,U,S,x,y;for(i=0;i^P;++i) i<R[i]&&(x=s[i],s[i]=s[R[i]],s[R[i]]=x);
			for(i=1;i^P;i<<=1) for(U=Qpow(~op?PR:IPR,(X-1)/(i<<1)),j=0;j^P;j+=i<<1)
				for(S=1,k=0;k^i;++k,S=1LL*S*U%X) s[j+k]=((x=s[j+k])+(y=1LL*S*s[i+j+k]%X))%X,s[i+j+k]=(x-y+X)%X;
		}
	public:
		I Poly() {IPR=Qinv(PR);for(RI i=1;i<=2*LN;++i) S[++K]=i;}//初始化可用多项式的栈
		Tp I void Solve(Ty *a,Ty *f,CI l,CI r)//分治NTT
		{
			if(l==r) return (void)(f[0]=1,f[a[l]]=X-1);RI i,mid=l+r>>1,lc,rc;//边界直接赋值
			lc=S[K--],Solve(a,g[lc],l,mid),rc=S[K--],Solve(a,g[rc],mid+1,r);//递归处理子区间
			P=1,L=0;W(P<=tot[r]-tot[l-1]) P<<=1,++L;for(i=0;i^P;++i) R[i]=(R[i>>1]>>1)|((i&1)<<L-1);//初始化
			for(T(g[lc],1),T(g[rc],1),i=0;i^P;++i) f[i]=1LL*g[lc][i]*g[rc][i]%X;//NTT
			RI t=Qinv(P);for(T(f,-1),i=0;i<=tot[r]-tot[l-1];++i) f[i]=1LL*f[i]*t%X;//NTT
			for(i=0;i^P;++i) g[lc][i]=g[rc][i]=0;S[++K]=lc,S[++K]=rc;//清空后扔回栈中，以重复利用
		}
};Poly<N,3> P;
int main()
{
	RI i,ans=0;for(F.read(n),i=1;i<=n;++i) F.read(a[i]),tot[i]=tot[i-1]+a[i];//读入，求前缀和方便后续处理
	for(P.Solve(a,f,2,n),i=0;i<=tot[n]-tot[1];++i) ans=(1LL*f[i]*a[1]%X*Qinv((a[1]+i)%X)+ans)%X;//分治NTT后统计答案
	return printf("%d",ans),0;
}