【LOJ2541】【PKUWC2018】猎人杀（容斥，FFT）

100 阅读 0 评论 66 点赞

我是靠谱客的博主紧张绿茶，最近开发中收集的这篇文章主要介绍【LOJ2541】【PKUWC2018】猎人杀（容斥，FFT），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题面

LOJ

题解

这题好神仙啊。
直接考虑概率很麻烦，因为分母总是在变化。
但是，如果一个人死亡之后，我们不让他离场，假装给他打一个标记（猎人印记？？？）
如果在一次选择的时候选中了一个已经被打过标记的人，那么我们就重新做一次选择。
这样显然没有任何影响。
现在考虑如何求第一个人最后一个被打上标记的概率。
我们容斥一下，枚举一下哪些人会在 $1$ 之后被选择，那么容斥系数就是 $(-1)$ 的人数次方。
那么对于钦定的在 $1$ 之后被选择的集合 $S$ ，假设他们的 $w$ 的和为 $S$ ，所有人 $w$ 的和为 $A$ 。这个集合贡献的值就是 $(-1)^{|S|}sum_{i=1}^{infty}(1-frac{S+W_1}{A})^ifrac{W_1}{A}$ 。后面的部分可以化简，结果就是 $frac{W_1}{S+W_1}$ 。
现在的问题就是求 $S$ 了。
我们发现因为是一个分数的形式，如果直接计算显然是不能够直接 $dp$ 。
换种思路，如果我们计算每一种分母分别出现了多少次，这个就非常好算了。
这样就可以通过 $dp$ 计算，同时发现事实上这个 $dp$ 就是一个 $01$ 背包，所以可以用分治+ $NTT$ 来优化计算。
时间复杂度 $O(nlogn^2)$

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define MAX 250000
#define ll long long
#define MOD 998244353
inline int read()
{
    int x=0;bool t=false;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}
int fpow(int a,int b)
{
    int s=1;
    while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}
    return s;
}
int n,w[MAX],ans;
int W[MAX],r[MAX];
void NTT(int *P,int len,int opt)
{
    int N,l=0;for(N=1;N<len;N<<=1)++l;
    for(int i=0;i<N;++i)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    for(int i=0;i<N;++i)if(i<r[i])swap(P[i],P[r[i]]);
    for(int i=1;i<N;i<<=1)
    {
        int w=fpow(3,(MOD-1)/(i<<1));W[0]=1;
        for(int k=1;k<i;++k)W[k]=1ll*W[k-1]*w%MOD;
        for(int p=i<<1,j=0;j<N;j+=p)
            for(int k=0;k<i;++k)
            {
                int X=P[j+k],Y=1ll*P[i+j+k]*W[k]%MOD;
                P[j+k]=(X+Y)%MOD;P[i+j+k]=(X+MOD-Y)%MOD;
            }
    }
    if(opt==-1)
    {
        reverse(&P[1],&P[N]);
        for(int i=0,inv=fpow(N,MOD-2);i<N;++i)P[i]=1ll*P[i]*inv%MOD;
    }
}
int tmp[50][MAX];
int S[MAX],top,P[MAX];
int Solve(int l,int r,int *P)
{
    if(l==r){P[0]=1;P[w[l]]=MOD-1;return w[l];}
    int mid=(l+r)>>1,l1,l2,ls,rs,N;
    ls=S[top--];l1=Solve(l,mid,tmp[ls]);
    rs=S[top--];l2=Solve(mid+1,r,tmp[rs]);
    for(N=1;N<=l1+l2;N<<=1);
    NTT(tmp[ls],N,1);NTT(tmp[rs],N,1);
    for(int i=0;i<N;++i)P[i]=1ll*tmp[ls][i]*tmp[rs][i]%MOD;
    NTT(P,N,-1);S[++top]=ls;S[++top]=rs;
    for(int i=0;i<N;++i)tmp[ls][i]=tmp[rs][i]=0;
    return l1+l2;
}
int main()
{
    n=read();
    for(int i=1;i<=n;++i)w[i]=read();
    for(int i=0;i<50;++i)S[++top]=i;
    int len=Solve(2,n,P);
    for(int i=0;i<=len;++i)ans=(ans+1ll*P[i]*fpow(w[1]+i,MOD-2))%MOD;
    ans=1ll*ans*w[1]%MOD;
    printf("%dn",ans);
    return 0;
}