loj#2541. 「PKUWC 2018」猎人杀【容斥+概率dp+生成函数+分治FFT】

本文链接：https://blog.csdn.net/cdsszjj/article/details/80496777

本文介绍了一种使用容斥原理和分治FFT解决概率问题的方法。通过将原问题转化为每轮选择概率不变的问题，并利用容斥原理进行求解。进一步地，通过生成函数和分治FFT来高效计算所有可能情况的概率总和。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

传送门

解题思路：

思路巧妙……

原题中每轮概率都在变化，一脸不可做，但注意到对问题的转化：
我们杀人后将其打上标记，但还是可以以他为目标重复选，直到选到一个未打标记的人。
这和原问题等价，而且这样每轮选中每人的概率都不变。

考虑容斥，枚举强制在1号后面死的人，即1号至少在这些人前面，令 $A=\sum w_i$ ， $S$ 为枚举到的人的 $w_i$ 之和， $t$ 为人数，则

a n s = (- 1)^{t} \sum_{i = 0}^{\infty} (1 - \frac{S + w_{1}}{A})^{i} \frac{w_{1}}{A}

$ans=(-1)^t\sum\limits_{i=0}^\infty(1-\frac{S+w_1}{A})^i\frac{w_1}{A}$

设

T = \sum i = 0 \infty (1 - S + w 1 A) i

$T=\sum\limits_{i=0}^\infty(1-\frac{S+w_1}{A})^i$

(1 - S + w 1 A) T = \sum i = 1 \infty (1 - S + w 1 A) i

$(1-\frac{S+w_1}{A})T=\sum\limits_{i=1}^\infty(1-\frac{S+w_1}{A})^i$

S + w 1 A T = (1 - S + w 1 A) 0 = 1

$\frac{S+w_1}{A}T=(1-\frac{S+w_1}{A})^0=1$

T = A S + w 1

$T=\frac{A}{S+w_1}$
所以

a n s = (- 1) t w 1 S + w 1

$ans=(-1)^t\frac{w_1}{S+w_1}$
考虑直接算出每个

S S $S$ 的容斥系数和

f_{S}

$f_S$ ，当做生成函数算，即是

F (x) = \prod i = 2 n (1 - x w i)

$F(x)=\prod\limits_{i=2}^n(1-x^{w_i})$
分治FFT即可。

设 $q=\sum w_i$ ，那么复杂度为 $O(qlog^2q)$

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
int getint()
{
    ll i=0,f=1;char c;
    for(c=getchar();(c!='-')&&(c<'0'||c>'9');c=getchar());
    if(c=='-')c=getchar(),f=-1;
    for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';
    return i*f;
}
const int N=100005,mod=998244353,g=3;
int n,tot,a[N],pos[N<<3];
ll w[65],invw[65],f1[N<<3],f2[N<<3];
ll Pow(ll x,int y)
{
    ll res=1;
    for(;y;y>>=1,x=x*x%mod)
        if(y&1)res=res*x%mod;
    return res;
}
void NTT(ll *f,int len,int on)
{
    for(int i=1;i<len;i++)
        pos[i]=(i&1)?pos[i>>1]>>1|(len>>1):pos[i>>1]>>1;
    for(int i=1;i<len;i++)if(i<pos[i])swap(f[i],f[pos[i]]);
    for(int i=1,num=1;i<len;i<<=1,num++)
    {
        ll wi=on==1?w[num]:invw[num];
        for(int j=0;j<len;j+=(i<<1))
        {
            ll wn=1;
            for(int k=j;k<j+i;k++)
            {
                ll u=f[k],v=wn*f[k+i]%mod;
                f[k]=(u+v)%mod,f[k+i]=(u+mod-v)%mod;
                wn=wn*wi%mod;
            }
        }
    }
    if(on==-1)for(int i=0,inv=Pow(len,mod-2);i<len;i++)
        f[i]=f[i]*inv%mod;
}
vector<ll> solve(int l,int r)
{
    vector<ll>A,B,C;
    if(l==r)
    {
        C.resize(a[l]+1);
        C[0]=1,C[a[l]]=-1;
        return C;
    }
    int mid=l+r>>1;
    A=solve(l,mid),B=solve(mid+1,r);
    int l1=A.size()-1,l2=B.size()-1,len=1;
    while(len<=l1+l2)len<<=1;
    for(int i=0;i<=l1;i++)f1[i]=A[i];
    for(int i=l1+1;i<=len;i++)f1[i]=0;
    for(int i=0;i<=l2;i++)f2[i]=B[i];
    for(int i=l2+1;i<=len;i++)f2[i]=0;
    NTT(f1,len,1),NTT(f2,len,1);
    for(int i=0;i<len;i++)f1[i]=f1[i]*f2[i]%mod;
    NTT(f1,len,-1);
    for(int i=0;i<=l1+l2;i++)C.pb(f1[i]);
    return C;
}
int main()
{
    //freopen("lx.in","r",stdin);
    n=getint();
    for(int i=1;i<=n;i++)a[i]=getint(),tot+=a[i]*(i>1);
    int len=1,num=0;
    while(len<=tot)
    {
        len<<=1;
        w[++num]=Pow(g,(mod-1)/len);
        invw[num]=Pow(w[num],mod-2);
    }
    vector<ll>A=solve(2,n);
    ll ans=0;
    for(int S=0;S<=tot;S++)
        ans=(ans+A[S]*a[1]%mod*Pow(S+a[1],mod-2))%mod;
    cout<<ans<<'\n';
}