[PKUWC2018]猎人杀解题报告

有 (n) 个猎人，第 (i) 个猎人有一个仇恨度 (w_i) ，被打中的概率是 (frac{w_i}{sum}) ， (sum) 是活着的猎人的仇恨度总和。

一开始由第一个猎人开出一枪，问第一个猎人是最后死的概率。

(nle 10^5 , sumle 10^5)

其实我以前在搞约翰夫抽杀时想过和这个一模一样的题，当时感觉十分不可做，现在看来是我太菜了，没想到真的有这道题。

每次打中一个猎人总的仇恨度会发生变化，感觉十分不可做，所以要考虑转化一下问题。

假设总的仇恨度为 (s_0) ，目前活着的人的仇恨度总和为 (s_1) ，则第 (i) 个人被打中的概率为 (p_i=frac{w_i}{s_1}) ，为了更好的做题，考虑把分母转化为 (s_0) ，那么有 (p_i=frac{w_i+(s_0-s_1)p_i}{s_0}) ，再把 (p_i=frac{w_i}{s_1}) 代到前面变成 (frac{w_i}{s_1}=frac{w_i+(s_0-s_1)p_i}{s_0}) ，化简可得 (p_i=frac{w_i}{s_0}) 。

所以题目可以转化成每个人被打中的概率是 (frac{w_i}{s_0}) ，可以打中死人，问第一个猎人是最后死的概率。

这种反直觉的概率果然不是给我这种粗人玩的Orz

但是最后死的概率并不好求，考虑运用套路，通过容斥将限制放宽，假设 (S) 是一个以猎人为元素的集合， (F(x)) 是第一个猎人死后剩下猎人集合包含 (S) 的概率，那么有 (Ans=sumlimits (-1)^{|S|} F(S)) 。

考虑枚举第一个猎人是第几个死的，可以得到 (F(S)=sumlimits_{i=0}^{infty} (frac{s_0-w_1-sum(S)}{s_0})^ifrac{w_1}{s_0}) ，通过等比数列求和公式和对极限的运用，能化简成 (F(S)=frac{w_1}{w_1+sum(S)}) ，所以有 (Ans=sumlimits (-1)^{|S|} frac{w_1}{w_1+sum(S)}) 。

直接枚举集合再考虑优化不太可能，所以要另寻蹊径，发现数据范围中有 (s_0le 10^5) 这一条，而且 (F(S)) 也只有 (sum(S)) 这一变量，考虑枚举 (sum(S)) 来求答案。

假设 (G(x)=sumlimits_{sum(S)=x} (-1)^{|S|}) ，那么有 (Ans=sumlimits_{i=1}^{s_0} frac{w_1G(i)}{w_1+i}) 。

这个 (G(x)) 的限制条件显然可以用生成函数来求解，由于每个猎人最多选一个，所以对于第 (i) 个猎人，他的生成函数就只有第 (0) 项是 (1) 和第 (w_i) 项是 (-1) ，将所有的生成函数乘起来的第 (x) 项正是 (G(x)) 。

这个东西可以用堆+NTT或者分治+NTT做到 (mathcal{O(nlog^2 n)}) 。

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int M=2e5+5,JYY=998244353;

int n,Sum=0,Ans=0,w[M];
int read(){
    int x=0,y=1;char ch=getchar();
    while(ch<'0'||ch>'9') y=(ch=='-'?-1:1),ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*y;
}

int qpow(int x,int y){
    int res=1;x%=JYY,y%=(JYY-1);
    for(;y;x=x*x%JYY,y>>=1) if(y&1) res=res*x%JYY;
    return res;
}

namespace Poly{
    int rev[M],wn[35];
    void getwn(){ for(int i=0;i<=25;i++) wn[i]=qpow(3,(JYY-1)/(1<<i));}
    void NTT(int f[],int L,int inv){
        for(int i=0;i<L;i++) if(i<rev[i]) swap(f[i],f[rev[i]]);
        for(int mid=1,id=1;mid<L;mid<<=1,id++)
            for(int R=(mid<<1),j=0;j<L;j+=R)
                for(int k=0,w=1;k<mid;k++,w=w*wn[id]%JYY){
                    int u=f[j+k],v=w*f[j+k+mid]%JYY;
                    f[j+k]=(u+v)%JYY;
                    f[j+k+mid]=(u-v+JYY)%JYY;
                }
        if(inv==-1){
            reverse(f+1,f+L);int ny=qpow(L,JYY-2);
            for(int i=0;i<L;i++) f[i]=f[i]*ny%JYY;
        }
    }
    void poly_mul(int f[],int g[],int h[],int L1,int L2){
        int len=1,L=0;static int a[M],b[M];
        for(;len<L1+L2;len<<=1) L++;
        for(int i=0;i<len;i++){
            rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));
            a[i]=(i<L1?f[i]:0),b[i]=(i<L2?g[i]:0);
        }
        NTT(a,len,1),NTT(b,len,1);
        for(int i=0;i<len;i++) h[i]=a[i]*b[i];
        NTT(h,len,-1);
        for(int i=L1+L2-1;i<len;i++) h[i]=0;
    }
}using namespace Poly;

vector<int> cun[M];
void work(int u,int l,int r){
    if(l==r){
        cun[u].push_back(1);
        for(int i=1;i<w[l];i++) cun[u].push_back(0);
        cun[u].push_back(JYY-1);
        return ;
    }
    static int f[M],g[M],h[M];
    int mid=(l+r)>>1;
    work(u<<1,l,mid),work(u<<1|1,mid+1,r);
    int szl=cun[u<<1].size(),szr=cun[u<<1|1].size();
    for(int i=0;i<szl;i++) f[i]=cun[u<<1][i];
    for(int i=0;i<szr;i++) g[i]=cun[u<<1|1][i];
    poly_mul(f,g,h,szl,szr);
    for(int i=0;i<szl+szr-1;i++) cun[u].push_back(h[i]);
}

void solve(){
    n=read();
    for(int i=1;i<=n;i++) Sum+=w[i]=read();
    getwn();work(1,2,n);
    for(int i=0;i<=Sum-w[1];i++) Ans=(Ans+cun[1][i]*w[1]%JYY*qpow(w[1]+i,JYY-2)%JYY)%JYY;
    printf("%lld
",Ans);
}

signed main(){
    // freopen("shuju.in","r",stdin);
    solve();
}

[PKUWC2018]猎人杀 解题报告

[PKUWC2018]猎人杀解题报告