题目概述

LOJ2541

解题报告

可以把题目转化为，有一个外人向 $n$ 个人开枪，打到第 $i$ 个人的概率是 $w_i\over \sum w$ ，并且可以对死人开枪（但没有效果），问最后才打死 $1$ 的概率。

这样转化之后每次打中 $i$ 的概率和之前无关。由于最后才打死 $1$ 不好处理，考虑容斥，定义 $f(S)$ 表示 $1$ 死后至少还有 $S$ 这个集合活着的概率，则不难得出：

$$ f(S)={w_1\over w_1+\sum_{i\in S}w_i}\\ ans=\sum_{S}(-1)^{|S|}f(S) $$

即 $1$ 和 $S$ 中，$1$ 先被打死的概率（其他人的顺序任意）。

由于 $\sum_{i\in S}w_i$ 出现在分母中，倒数很难合并，因此考虑求出所有 $\sum_{i\in S}w_i=j$ 的容斥系数 $sum(j)$ ，然后 $ans=\sum_{j}sum(j){w_1\over w_1+j}$ 。

定义 $f_{i,j}$ 表示前 $i$ 个人，$\sum_{i\in S}w_i=j$ 的容斥系数，则显然 $f_{i,j}=f_{i-1,j}-f_{i-1,j-w_i}$ 。

考虑生成函数即 $F_i(x)=F_{i-1}(x)(1-x^{w_j})$ ，分治NTT即可。

示例程序

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;typedef vector<int> PN;
const int maxn=100000,maxt=1<<17,MOD=998244353;

int n,w[maxn+5],ans;
int wn[maxt+5],temA[maxt+5],temB[maxt+5];
PN p[maxn+5],P;

inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;}
inline int MUL(int x,int y) {return (LL)x*y%MOD;}
int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=MUL(w,w)) if (b&1) s=MUL(s,w);return s;}
void NTTPre(){
    int x=Pow(3,(MOD-1)/maxt);
    wn[maxt>>1]=1;
    for (int i=(maxt>>1)+1;i<maxt;i++) wn[i]=MUL(wn[i-1],x);
    for (int i=(maxt>>1)-1;i;i--) wn[i]=wn[i<<1];
}
void NTT(int *a,int n,int f){
    if (f>0){
        for (int k=n>>1;k;k>>=1)
            for (int i=0;i<n;i+=k<<1)
                for (int j=0;j<k;j++){
                    int x=a[i+j],y=a[i+j+k];
                    a[i+j+k]=MUL(x+MOD-y,wn[k+j]);
                    a[i+j]=ADD(x,y);
                }
    } else {
        for (int k=1;k<n;k<<=1)
            for (int i=0;i<n;i+=k<<1)
                for (int j=0;j<k;j++){
                    int x=a[i+j],y=MUL(a[i+j+k],wn[k+j]);
                    a[i+j+k]=ADD(x,MOD-y);
                    a[i+j]=ADD(x,y);
                }
        for (int i=0,INV=MOD-(MOD-1)/n;i<n;i++) a[i]=MUL(a[i],INV);
        reverse(a+1,a+n);
    }
}
PN operator * (const PN &a,const PN &b){
    static PN c;
    int n=a.size(),m=b.size(),t;
    for (t=1;t<n+m-1;t<<=1);
    for (int i=0;i<n;i++) temA[i]=a[i];for (int i=n;i<t;i++) temA[i]=0;
    for (int i=0;i<m;i++) temB[i]=b[i];for (int i=m;i<t;i++) temB[i]=0;
    NTT(temA,t,1);NTT(temB,t,1);
    for (int i=0;i<t;i++) temA[i]=MUL(temA[i],temB[i]);
    NTT(temA,t,-1);
    c.resize(n+m-1);for (int i=0;i<n+m-1;i++) c[i]=temA[i];
    return c;
}
PN Solve(int L,int R) {if (L==R) return p[L];int mid=L+(R-L>>1);return Solve(L,mid)*Solve(mid+1,R);}
int main(){
    NTTPre();
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&w[i]);
    if (n==1) {puts("1");return 0;}
    for (int i=2;i<=n;i++){
        p[i].resize(w[i]+1);
        p[i][0]=1;p[i][w[i]]=MOD-1;
    }
    P=Solve(2,n);
    for (int j=0,si=P.size();j<si;j++) ans=ADD(ans,MUL(MUL(w[1],Pow(w[1]+j,MOD-2)),P[j]));
    printf("%d\n",ans);
    return 0;
}