[LOJ2541]「PKUWC2018」猎人杀descriptionsolcode

loj

description

有(n)个猎人，每个猎人有一个仇恨度(w_i)，每个猎人死后会开一枪打死一个还活着的猎人，打中每个猎人的概率与他的仇恨度成正比。
现在你开了第一枪，打死每个猎人的概率同样也和它的仇恨度成正比。现在第一个猎人想知道他最后一个死的概率。
(w_i>0,sum w_ile10^5)，模(998244353)

sol

容斥，考虑强制某个集合内的猎人在一号猎人之后被打死，剩下的猎人无所谓。
设这个集合内的猎人的仇恨度之和是(W),所有猎人的仇恨度之和是(Sum)，那么这个集合对答案的贡献就是：[sum_{i=0}^{inf}(1-frac{W+w_1}{Sum})^ifrac{w_1}{Sum}=frac{w_1}{W+w_1}]
我们可以把“在剩下还活着的人中选一个打死”改为“在所有人中选一个打，直至打到一个活着的人”，这样每个人被打到的概率就始终都是(frac{w_i}{Sum})，只不过开枪次数就没有了上限。不过显然这个无限等比数列是很容易进行求和的。
所以上面的式子的意思是：枚举前(i)枪都没有打中一号猎人和选中集合中的猎人，而接下来一枪刚好把一号猎人打死的概率。
于是现在关键在于枚举集合。我们发现对于(W)相同的集合可以一起计算，而(W)不同的集合至多只有(O(n))个，所以可以枚举(W)，计算有多少个集合的仇恨度之和为(W)。这里同时也要乘上容斥系数(1)或(-1)。
其实要计算的就是一个这样的东西：[prod_{i=2}^{n}1-x^{w_i}]
所以直接分治(NTT)就行了。

code

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int gi(){
    int x=0,w=1;char ch=getchar();
    while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if (ch=='-') w=0,ch=getchar();
    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return w?x:-x;
}
const int N = 4e5+5;
const int mod = 998244353;
int n,w[N],s[N],inv[N],tmp[50][N],Stack[50],top,rev[N],og[N],ans;
inline void add(int &x,int y){x+=y;if(x>=mod)x-=mod;}
inline int fastpow(int a,int b){
    int res=1;
    while(b){if(b&1)res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}
    return res;
}
void ntt(int *P,int opt,int len){
    int l=0;while((1<<l)<len)++l;--l;
    for (int i=0;i<len;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<l);
    for (int i=0;i<len;++i) if (i<rev[i]) swap(P[i],P[rev[i]]);
    for (int i=1;i<len;i<<=1){
        int W=fastpow(3,(mod-1)/(i<<1));
        if (opt==-1) W=fastpow(W,mod-2);
        og[0]=1;for (int j=1;j<i;++j) og[j]=1ll*og[j-1]*W%mod;
        for (int p=i<<1,j=0;j<len;j+=p)
            for (int k=0;k<i;++k){
                int x=P[j+k],y=1ll*og[k]*P[j+k+i]%mod;
                P[j+k]=(x+y)%mod;P[j+k+i]=(x-y+mod)%mod;
            }
    }
    if (opt==-1) for (int i=0,Inv=fastpow(len,mod-2);i<len;++i) P[i]=1ll*P[i]*Inv%mod;
}
void solve(int *P,int l,int r){
    if (l==r) {P[0]=1;P[w[l]]=mod-1;return;}
    int mid=l+r>>1,ls=Stack[top--];
    solve(tmp[ls],l,mid);
    int rs=Stack[top--];
    solve(tmp[rs],mid+1,r);
    int len=1;while(len<=s[r]-s[l-1])len<<=1;
    ntt(tmp[ls],1,len);ntt(tmp[rs],1,len);
    for (int i=0;i<len;++i) P[i]=1ll*tmp[ls][i]*tmp[rs][i]%mod;
    ntt(P,-1,len);
    Stack[++top]=ls;Stack[++top]=rs;
    for (int i=0;i<len;++i) tmp[ls][i]=tmp[rs][i]=0;
}
int main(){
    n=gi();inv[0]=inv[1]=1;
    for (int i=1;i<=n;++i) w[i]=gi(),s[i]=s[i-1]+w[i];
    for (int i=2;i<=s[n];++i) inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
    for (int i=1;i<50;++i) Stack[++top]=i;
    solve(tmp[0],2,n);
    for (int i=0;i<=s[n]-s[1];++i) add(ans,1ll*w[1]*inv[i+w[1]]%mod*tmp[0][i]%mod);
    printf("%dn",ans);
    return 0;
}