【题解】loj2541 猎人杀 容斥+分治 NTT ——litble

感觉哪里不好下手？
猎人死了的话，$\sum w_i$会变。
怎么办呢？嗯，那么死了的猎人不下场，选到死了的猎人，就重新选一次。

现在 1 号猎人是最后一个死的，也就是我们要除掉别的猎人在 1 号之后死的情况。假设有几个猎人在 1 号之后死，他们的权值和为 $S$，那么这种情况的概率就是：

$$f(S)=\sum^{inf} (1-\frac{w_1+S}{\sum w})\frac{w_1}{\sum w}$$
（当然了，这种计算方法下，可能还是有除了权值和为 $S$的那些猎人以外的猎人在 1 后面死也被算进去了，所以要容斥）

我们现在容斥一下，首先取 $S=0$，然后减去至少一个猎人在 1 后死的，加上至少两个的，减去至少三个的……
可以发现构造一个生成函数 $\sum_{i=2}^n(1-x^{w_i})$，设 $x^i$的系数为 $a_i$，那么答案就是 $\sum a_i f(i)$
设 $W$是 $w_i$中的最大值。用分治 NTT 计算该生成函数，复杂度是 $O(WlogWlogn)$

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
const int mod=998244353,N=262150,G=3;
int n,ans,w[N],A[20][N],rev[N],sz[20];
int qm(int x) {return x>=mod?x-mod:x;}
int ksm(int x,int y) {
    int re=1;
    for(;y;y>>=1,x=1LL*x*x%mod) if(y&1) re=1LL*re*x%mod;
    return re;
}
void NTT(int *a,int n,int x) {
    for(RI i=1;i<n;++i) if(rev[i]>i) swap(a[i],a[rev[i]]);
    for(RI i=1;i<n;i<<=1) {
        int gn=ksm(G,(mod-1)/(i<<1));
        for(RI j=0;j<n;j+=(i<<1)) {
            int g=1,t1,t2;
            for(RI k=0;k<i;++k,g=1LL*g*gn%mod) {
                t1=a[j+k],t2=1LL*g*a[j+i+k]%mod;
                a[j+k]=qm(t1+t2),a[j+i+k]=qm(t1-t2+mod);
            }
        }
    }
    if(x==1) return;
    int inv=ksm(n,mod-2);reverse(a+1,a+n);
    for(RI i=0;i<n;++i) a[i]=1LL*a[i]*inv%mod;
}
void getrev(int n,int len)
    {for(RI i=0;i<n;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1));}
void work(int l,int r,int d) {
    if(l==r) {
        sz[d]=w[l];
        for(RI i=0;i<=sz[d];++i) A[d][i]=0;
        A[d][0]=1,A[d][w[l]]=mod-1;return;
    }
    int mid=(l+r)>>1,kn=1,len=0;
    work(l,mid,d),work(mid+1,r,d+1);
    sz[d]+=sz[d+1];while(kn<=sz[d]) kn<<=1,++len;
    getrev(kn,len);
    for(RI i=sz[d]-sz[d+1]+1;i<kn;++i) A[d][i]=0;
    for(RI i=sz[d+1]+1;i<kn;++i) A[d+1][i]=0;
    NTT(A[d],kn,1),NTT(A[d+1],kn,1);
    for(RI i=0;i<kn;++i) A[d][i]=1LL*A[d][i]*A[d+1][i]%mod;
    NTT(A[d],kn,-1);
}
int main()
{
    n=read();
    for(RI i=1;i<=n;++i) w[i]=read();
    if(n==1) {puts("1");return 0;}
    work(2,n,0);
    for(RI i=0;i<=sz[0];++i)
        ans=qm(ans+1LL*A[0][i]*w[1]%mod*ksm(qm(i+w[1]),mod-2)%mod);
    printf("%d\n",ans);
    return 0;
}