设 $sum=\sum_{i}w_i,kill=\sum_{i 被杀死了}w_i$ ，则当前杀死猎人 $k$ 的概率为：
$$
P=\frac{w_k}{sum-kill}\
$$
然后很显然，假设一次可以选择的猎人集合并非活着的猎人集合而是全集，但是如果选到了被杀了的猎人，就在选一次，很显然这个对答案没有任何影响。
那么就可以得到：
$$
P=\frac{kill}{sum}P+\frac{w_k}{sum}\
$$
这个式子和上面也是等价的。
考虑容斥，考虑求出 $T$ 集合中的所有猎人都在 $1$ 号猎人后面死，剩下的猎人随便的概率，很显然因为剩下的猎人随便，总概率为 $1$ ，无需考虑，只需要考虑这些猎人对 $1$ 号猎人的贡献，设 $qwq=\sum_{i\in T}w_i$ 。
则有：
$$
\begin{aligned}
res&=(-1)^{|T|}\sum_{i=0}^{\infty}(\frac{sum-qwq-w_1}{sum})^i\frac{w_1}{sum}\\
&=(-1)^{|T|}\sum_{i=0}^{\infty}(1-\frac{qwq+w_1}{sum})^i\frac{w_1}{sum}\\
&=(-1)^{|T|}\frac{w_1}{sum}\sum_{i=0}^{\infty}(1-\frac{qwq+w_1}{sum})^i\\
\end{aligned}
$$
$1-\frac{qwq-w+1}{sum}$ 的意思就是随便选不选中 $1$ 和 $T$ 中的元素的概率，$i$ 是枚举选的次数。
然后，因为有：
$$
\sum_{i=0}^{\infty}p^i=\frac{1}{1-p},p\in(1,-1)
$$
所以：
$$
\begin{aligned}
res&=(-1)^{|T|}\frac{w_1}{sum}\sum_{i=0}^{\infty}(1-\frac{qwq+w_1}{sum})^i\\
&=(-1)^{|T|}\frac{w_1}{sum}\frac{1}{1-(1-\frac{qwq+w_1}{sum})}\\
&=(-1)^{|T|}\frac{w_1}{sum}\frac{sum}{qwq+w_1}\\
&=(-1)^{|T|}\frac{w_1}{qwq+w_1}\\
\end{aligned}
$$
最后：
$$
ans=\sum_{T\in S}(-1)^{|T|}\frac{w_1}{qwq+w_1}
$$
可喜可贺 [手动滑稽]，我们得到了一个 $O(2^n)$ 的算法，期望得分 $20pts$。但是发现题目给定的范围和 $n$ 貌似没什么关系，而是和 $\sum_{i}w_i$ 有关…… 所以变化一下：
$$
ans=\sum_{qwq=0}^{sum}\frac{w_1}{qwq+w_1}\left(\sum_{T\in S}(-1)^{|T|}[\sum_{i\in T}w_i=qwq]\right)
$$
后面的容斥系数 $\left(\sum_{T\in S}(-1)^{|T|}[\sum_{i\in T}w_i=qwq]\right)$ 背包一下即可，于是就得到了一个 $O(n\times sum)$ 的算法，期望得分 $50pts$ 。
假设现在需要求出，只使用集合 $S$ 中的猎人的容斥系数。
考虑 $S$ 的一个子集 $T$ ，假设 $T$ 的容斥系数为多项式 $f_1$ ，$\rm{S-T}$ 的容斥系数为多项式 $f_2$ ，如果 $S$ 的容斥系数为多项式 $f$ ，则有：
$$
f(n)=\sum_{i=0}^{n}f_1(i)f_2(n-i)
$$
这可以直接 $\rm{NTT}$ 做到 $O(n\log n)$ 。
然后像建立线段树那样，每一次往上合并即可，时间复杂度 $O(n\log^2 n)$ .
也就是直接分治 $\rm{NTT}$ 即可 (注意这个分治不是 $cdq$ 分治).
Code：
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int mod=998244353;
int n,w[N],sum[N],sta[35],top;
int g[35][N<<1],f[N<<1];
template <typename _Tp> inline void IN(_Tp&x) {
char ch;bool flag=0;x=0;
while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
if(flag) x=-x;
}
namespace Poly {
int filp[N<<1];
inline int modpow(int x,int y,int res=1) {
for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod;
return res;
}
inline void NTT(int*f,int limit,short inv) {
for(int i=0;i<limit;++i)
if(i<filp[i]) swap(f[i],f[filp[i]]);
for(int p=2;p<=limit;p<<=1) {
int len=p>>1,tmp=modpow(3,(mod-1)/p);
for(int k=0;k<limit;k+=p) {
int buf=1;
for(int l=k;l<k+len;++l,buf=1ll*buf*tmp%mod) {
int t=1ll*f[l+len]*buf%mod;
f[l+len]=(f[l]-t+mod)%mod,f[l]=(f[l]+t)%mod;
}
}
}
if(inv==1) return;
int sl=modpow(limit,mod-2);reverse(f+1,f+limit);
for(int i=0;i<limit;++i) f[i]=1ll*f[i]*sl%mod;
}
}using namespace Poly;
inline void solve(int*f,int l,int r) {
if(l==r) {
f[0]=1,f[w[l]]=mod-1;
return;
}
int lc,rc,mid=(l+r)>>1,len=1,cnt=0;
lc=sta[top--],solve(g[lc],l,mid),
rc=sta[top--],solve(g[rc],mid+1,r);
while(len<=sum[r]-sum[l-1]) len<<=1,++cnt;
for(int i=0;i<len;++i) filp[i]=(filp[i>>1]>>1)|((i&1)<<(cnt-1));
NTT(g[lc],len,1),NTT(g[rc],len,1);
for(int i=0;i<len;++i) f[i]=1ll*g[lc][i]*g[rc][i]%mod;
NTT(f,len,-1);
for(int i=0;i<len;++i) g[lc][i]=g[rc][i]=0;
sta[++top]=lc,sta[++top]=rc;
}
int main() {
IN(n);
for(int i=1;i<=n;++i) IN(w[i]),sum[i]=sum[i-1]+w[i];
for(int i=1;i<=30;++i) sta[++top]=i;
solve(f,2,n);
int ans=0,limit=sum[n]-w[1];
for(int i=0;i<=limit;++i)
ans=(ans+1ll*f[i]*w[1]%mod*modpow(w[1]+i,mod-2)%mod)%mod;
printf("%d\n",ans);
return 0;
}
0 条评论