HGOI div1 E 题解

· · 题解

场上就一个人 AC，怎么回事呢？

样例给的做法提示很明显，就是 有 k 个选手过线概率 乘以 给 k 个选手分配的期望价值 再求和。

有 k 个人过线的概率很简单，就是 [x^k]\prod_i((1-p_i)+p_ix)，分治乘即可。

然后需要计算给 k 个选手分配的价值总和。对于这种经典模型，对每种奖品建立 EGF，然后都乘起来，也就是：

k![x^k]\prod_{i=1}^A(1+a_i(\cosh x-1))\times \prod_{i=1}^B(b_i \sinh x)

后一部分很简单，前一部分有个暴力做法：做换元 u=\text e^x，然后直接分治乘，最后就是求 F(\text e^x) 的系数。

k![x^k]F(\text e^x)=\sum_{i=-A}^Af_i i^k =[x^k]\sum_{k=0}^\infty x^k\sum_{i=-A}^Af_i i^k =[x^k]\sum_{i=-A}^A\frac{f_i}{1-ix}

可以直接维护分子和分母分治求和。

最后把总和变为期望就是除一个方案数，令 a_i,b_i 都为 1 就是答案。

参考代码（没太注意实现细节，跑得比较慢）：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 1048579
#define p 998244353
#define ll long long
using namespace std;

inline void read(int &x){
    x = 0;
    char c = getchar();
    while(c<'0'||c>'9') c = getchar();
    while(c>='0'&&c<='9'){
        x = (x<<3)+(x<<1)+(c^48);
        c = getchar();
    }
}

void print(int x){
    if(x>9) print(x/10);
    putchar(x%10+'0');  
}

inline int power(int a,int t){
    int res = 1;
    while(t){
        if(t&1) res = (ll)res*a%p;
        a = (ll)a*a%p;
        t >>= 1;
    }
    return res;
}

inline int add(const int& x,const int& y){ return x+y>=p?x+y-p:x+y; }
inline int dec(const int& x,const int& y){ return x<y?x-y+p:x-y; }

int rt[N],rev[N],fac[N],ifac[N],inv[N];
int siz;

void init(int n){
    int w,lim = 1;
    while(lim<=n) lim <<= 1,++siz;
    for(int i=1;i!=lim;++i) rev[i] = (rev[i>>1]>>1)|((i&1)<<(siz-1));
    w = power(3,(p-1)>>siz);
    inv[1] = fac[0] = fac[1] = ifac[0] = ifac[1] = rt[lim>>1] = 1;
    for(int i=(lim>>1)+1;i!=lim;++i) rt[i] = (ll)rt[i-1]*w%p;
    for(int i=(lim>>1)-1;i;--i) rt[i] = rt[i<<1];   
    for(int i=2;i<=n;++i) fac[i] = (ll)fac[i-1]*i%p;
    ifac[n] = power(fac[n],p-2);
    for(int i=n-1;i;--i) ifac[i] = (ll)ifac[i+1]*(i+1)%p;
    for(int i=2;i<=n;++i) inv[i] = (ll)fac[i-1]*ifac[i]%p;
}

inline void dft(int *f,int n){
    static unsigned long long a[N];
    int x,shift = siz-__builtin_ctz(n);
    for(int i=0;i!=n;++i) a[rev[i]>>shift] = f[i];
    for(int mid=1;mid!=n;mid<<=1)
    for(int j=0;j!=n;j+=(mid<<1))
    for(int k=0;k!=mid;++k){
        x = a[j|k|mid]*rt[mid|k]%p;
        a[j|k|mid] = a[j|k]+p-x;
        a[j|k] += x;
    }
    for(int i=0;i!=n;++i) f[i] = a[i]%p;
}

inline void idft(int *f,int n){
    reverse(f+1,f+n);
    dft(f,n);
    int x = p-((p-1)>>__builtin_ctz(n));
    for(int i=0;i!=n;++i) f[i] = (ll)f[i]*x%p;
}

inline int getlen(int n){ return 1<<(32-__builtin_clz(n)); }

inline void inverse(const int *f,int n,int *r){
    static int g[N],h[N],st[30];
    memset(g,0,getlen(n<<1)<<2);
    int lim = 1,top = 0;
    while(n){
        st[++top] = n;
        n >>= 1;
    }
    g[0] = 1;
    while(top--){
        n = st[top+1];
        while(lim<=(n<<1)) lim <<= 1;
        memcpy(h,f,(n+1)<<2);
        memset(h+n+1,0,(lim-n)<<2);
        dft(g,lim),dft(h,lim);
        for(int i=0;i!=lim;++i) g[i] = g[i]*(2-(ll)g[i]*h[i]%p+p)%p;
        idft(g,lim);
        memset(g+n+1,0,(lim-n)<<2);
    }
    memcpy(r,g,(n+1)<<2);
}

int n,A,B;
int pr[N],a[N],C[N];

void product(int l,int r,int *R){
    if(l==r){
        R[0] = p+1-pr[l],R[1] = pr[l];
        return;
    }
    int lim = getlen(r-l+1),mid = (l+r)>>1;
    int fl = mid-l+1,gl = r-mid;
    int f[lim+2],g[lim+2];
    product(l,mid,f),product(mid+1,r,g);
    memset(f+fl+1,0,(lim-fl)<<2);
    memset(g+gl+1,0,(lim-gl)<<2);
    dft(f,lim),dft(g,lim);
    for(int i=0;i!=lim;++i) R[i] = (ll)f[i]*g[i]%p;
    idft(R,lim);
}

void prod2(int l,int r,int *R){
    if(l==r){
        R[0] = R[2] = a[l],R[1] = ((p+1-a[l])<<1)%p;
        return;
    }
    int lim = getlen((r-l+1)<<1),mid = (l+r)>>1;
    int fl = (mid-l+1)<<1,gl = (r-mid)<<1;
    int f[lim+2],g[lim+2];
    prod2(l,mid,f),prod2(mid+1,r,g);
    memset(f+fl+1,0,(lim-fl)<<2);
    memset(g+gl+1,0,(lim-gl)<<2);
    dft(f,lim),dft(g,lim);
    for(int i=0;i!=lim;++i) R[i] = (ll)f[i]*g[i]%p;
    idft(R,lim);
}

void solve(int l,int r,const int *sc,int *fz,int *fm){ // 多项式复合 F(e^x)
    if(l==r){
        fz[0] = sc[l+A],fm[0] = 1,fm[1] = (p-l)%p;
        return;
    }
    int lim = getlen(r-l+1),mid = (l+r)>>1;
    int fl = mid-l+1,gl = r-mid;
    int lfz[lim+2],lfm[lim+2],rfz[lim+2],rfm[lim+2];
    solve(l,mid,sc,lfz,lfm),solve(mid+1,r,sc,rfz,rfm);
    memset(lfz+fl,0,(lim-fl+1)<<2),memset(lfm+fl+1,0,(lim-fl)<<2);
    memset(rfz+gl,0,(lim-gl+1)<<2),memset(rfm+gl+1,0,(lim-gl)<<2);
    dft(lfz,lim),dft(lfm,lim),dft(rfz,lim),dft(rfm,lim);
    for(int i=0;i!=lim;++i){
        fz[i] = ((ll)lfz[i]*rfm[i]+(ll)lfm[i]*rfz[i])%p;
        fm[i] = (ll)lfm[i]*rfm[i]%p;
    }
    idft(fz,lim),idft(fm,lim);
}

inline void deriv(const int *f,int n,int *R){
    for(int i=1;i!=n;++i) R[i-1] = (ll)i*f[i]%p;
    R[n-1] = 0;
}

inline void integ(const int *f,int n,int *R){
    for(int i=n-1;i;--i) R[i] = (ll)f[i-1]*inv[i]%p;
    R[0] = 0;
}

inline void log(const int *f,int n,int *r){
    static int g[N],h[N];
    inverse(f,n,g);
    deriv(f,n+1,h);
    int lim = getlen(n<<1);
    memset(g+n+1,0,(lim-n)<<2);
    memset(h+n+1,0,(lim-n)<<2);
    dft(g,lim),dft(h,lim);
    for(int i=0;i!=lim;++i) g[i] = (ll)g[i]*h[i]%p;
    idft(g,lim);
    integ(g,n+1,r);
}

inline void exp(const int *a,int n,int *R){
    int m = n+1;
    n = 1;
    while(n<m) n <<= 1;
    static int der[N],b[N],c[N],dfta[N],dftb[N],dftb2[N],dftc[N];
    for(int i=0;i!=n;++i) b[i] = c[i] = dfta[i] = dftb[i] = dftb2[i] = dftc[i] = 0;
    dftb2[0] = b[0] = c[0] = 1;
    dft(dftb2,2);
    deriv(a,n,der);
    for(int d=1;d!=n;d<<=1){
        memcpy(dftc,c,d<<2);
        dft(dftc,d<<1);
        for(int i=0;i!=d;++i) dftb[i] = (ll)dftb2[i<<1]*dftc[i<<1]%p;
        idft(dftb,d);
        dftb[0] = dec(dftb[0],1);
        for(int i=0;i!=d;++i) dftb[d+i] = dftb[i];
        memset(dftb,0,d<<2);
        dft(dftb,d<<1);
        memcpy(dfta,der,(d-1)<<2);
        dfta[d-1] = 0;
        dft(dfta,d<<1);
        for(int i=0;i!=(d<<1);++i) dfta[i] = (ll)dfta[i]*dftb[i]%p;
        idft(dfta,d<<1);
        deriv(b,d,dftb);
        dft(dftb,d);
        for(int i=0;i!=d;++i) dftb[i] = (ll)dftb[i]*dftc[i<<1]%p;
        idft(dftb,d);
        for(int i=0;i!=d-1;++i) dftb[d+i] = dec(dftb[i],der[i]);
        memset(dftb,0,(d-1)<<2);
        for(int i=d-1;i!=(d<<1);++i) dftb[i] = dec(dftb[i],add(der[i],dfta[i]));
        integ(dftb,d<<1,dftb);
        dft(dftb,d<<1);
        for(int i=0;i!=(d<<1);++i) dftb[i] = (ll)dftb[i]*dftb2[i]%p;
        idft(dftb,d<<1);
        for(int i=d;i!=(d<<1);++i) b[i] = p-dftb[i];
        if((d<<1)==n) continue;
        memcpy(dftb2,b,d<<3);
        dft(dftb2,d<<2);
        for(int i=0;i!=(d<<1);++i) dftb[i] = (ll)dftb2[i<<1]*dftc[i]%p;
        idft(dftb,d<<1);
        memset(dftb,0,d<<2);
        dft(dftb,d<<1);
        for(int i=0;i!=(d<<1);++i) dftb[i] = (ll)dftb[i]*dftc[i]%p;
        idft(dftb,d<<1);
        for(int i=d;i!=(d<<1);++i) c[i] = p-dftb[i];
    }
    memcpy(R,b,m<<2);
}

int f[N],g[N],fz[N],fm[N],suf[N];
int pw,ans;

int main(){
    read(n),read(A),read(B);
    if(n<B){
        puts("0");
        return 0;
    }
    init(800000);
    for(int i=1;i<=n;++i) read(pr[i]);
    for(int i=1;i<=A;++i) read(a[i]);
    product(1,n,C),prod2(1,A,f);
    solve(-A,A,f,fz,fm); 
    for(int i=n+1;i<=(A<<1);++i) fz[i] = fm[i] = 0;
    inverse(fm,n,fm);
    int lim = getlen(n<<1);
    dft(fz,lim),dft(fm,lim);
    for(int i=0;i!=lim;++i) fz[i] = (ll)fz[i]*fm[i]%p;
    idft(fz,lim);
    memset(fz+n+1,0,(lim-n)<<2),memset(f,0,lim<<2);
    for(int i=0;i<=n;++i) fz[i] = (ll)fz[i]*ifac[i]%p;
    int tn = max((n-B)>>1,4);
    for(int i=0;i<=tn;++i) f[i] = ifac[i<<1|1];
    log(f,tn,f);
    for(int i=0;i<=tn;++i) f[i] = (ll)f[i]*B%p;
    exp(f,tn,f);
    for(int i=tn;i;--i) f[i<<1] = f[i],f[i] = 0;
    for(int i=n;i>=B;--i) f[i] = f[i-B];
    memset(f,0,B<<2),memset(f+n+1,0,(lim-n)<<2);
    for(int i=0;(i<<1)<=n;++i) g[i] = ifac[i<<1];
    log(g,n>>1,g);
    for(int i=0;(i<<1)<=n;++i) g[i] = (ll)g[i]*A%p;
    exp(g,n>>1,g);
    for(int i=(n>>1);i;--i) g[i<<1] = g[i],g[i] = 0;
    dft(fz,lim),dft(f,lim),dft(g,lim);
    for(int i=0;i!=lim;++i){
        fz[i] = (ll)fz[i]*f[i]%p;
        g[i] = (ll)g[i]*f[i]%p;
    }
    idft(fz,lim),idft(g,lim);
    suf[n+1] = 1;
    for(int i=n;i;--i) suf[i] = (ll)suf[i+1]*(g[i]==0?1:g[i])%p;
    int pre = power(suf[1],p-2);
    for(int i=1;i<=n;++i){
        ans = (ans+(ll)fz[i]*C[i]%p*pre%p*suf[i+1])%p;
        pre = (ll)pre*(g[i]==0?1:g[i])%p;
    }
    for(int i=1;i<=B;++i){
        read(pw);
        ans = (ll)ans*pw%p;
    }
    ans = (ll)ans*power(2,p-A-1)%p;
    print(ans);
    return 0;
}