0608

· · 个人记录

AT_abc409_g

卷积的部分没啥好说的，主要是前面推式子部分

朴素计算期望，需要做一个 DP g_{i,j} 表示从后往前考虑到 i，选了 j 个的概率，进行转移。这个 j 是省不掉的，因为系数与其相关，似乎也提不出来

最后我们需要的只是 G_i=\sum_jjg_{i,j}，即枚举出现次数后累加期望

但这个期望是可以直接计算的！发现 g_{i,j} 的系数关于 j 是线性的，期望可以穿透线性的函数

G_i=E[前 i 个选的数量]=E[前i-1个选的数量+第i个选没选]\\ =E[前i-1个选的数量]+E[第i个选没选]\\ =G_{i-1}+E[f(i,前i个选的数量)]\\

然后 f(i,X) 确为线性，于是可以把这个期望拆进去，直接转移 G_i 得到期望

后面还有个部分，计算了这样的式子

\sum_{i=0}^{n-k}F_{i+k}G_i

这样滑动的积的形式。事实上，直接翻转 F，即令 F_i=F_{n-i}，可以变成

\sum_{i=0}^{n-k}F_{n-k-i}G_i

变成卷积的形式。

因为没怎么推过卷积式子所以卡了有一会，问了GPT才知道是卷积，记录一下

用了 ATCoder Library 的 convolution 和 modint

#include <atcoder/modint>
#include <atcoder/convolution>

int n,p;

int ans[MAXN];

int fac[MAXN];
int ifac[MAXN];
int inv[MAXN];

void solve(bool SPE){
    n=RIN,p=RIN;

    if(p==100){
        foru(i,1,n){
            cout<<1<<endl;
        }
        return ;
    }

    p=mul(p,qpow(100,mod-2));

    int q=rmv(1,p);
    int _q=qpow(q,mod-2);

    foru(i,1,n){
        inv[i]=qpow(i,mod-2);
    }
    fac[0]=1;
    foru(i,1,n){
        fac[i]=mul(fac[i-1],i);
    }
    ifac[n]=qpow(fac[n],mod-2);
    ford(i,n-1,0){
        ifac[i]=mul(ifac[i+1],i+1);
    }
    // cout<<mul(fac[3],ifac[2],ifac[1])<<endl;

    static int G[MAXN];
    G[n]=1;
    ford(i,n-1,1){
        G[i]=add(G[i+1],mul(q,G[i+1],inv[i]));
    }

    ans[1]=G[1];

    foru(i,2,n){
        mll(G[i],fac[i-2],qpow(q,i));
    }

    static int H[MAXN];
    foru(i,2,n){
        H[i]=mul(ifac[i-2],qpow(p,i-1),qpow(_q,i));
    }

    // cout<<g[n][0]<<endl;

    typedef atcoder::static_modint<998244353> mint;
    // static int F[MAXN];
    vector<mint> ff(n+1,0);
    vector<mint> ii(n+1,0);

    foru(i,0,n){
        // cout<<G[n-i]<<endl;
        ff[i]=G[n-i];
        ii[i]=ifac[i];
        // F[i]=G[n-i];
    }
    // return ;

    // static int CV[MAXN];
//  
    // foru(k,0,n){
        // foru(i,0,k){
            // mdd(CV[k],mul(F[i],ifac[k-i]));
        // }
    // }
    vector<mint> CV=atcoder::convolution(ff,ii);

    foru(k,1,n){
        int x=CV[n-k].val();
        ans[k]+=mul(x,H[k]);
    }

    foru(i,1,n){
        printf("%d\n",ans[i]);
    }

    return ;
}

NTT

半学半背板地把 NTT 学了

FFT 还是记得的，核心是单位根具有性质，因此后半部分的点值可以用前半部分的递归结果计算。迭代版就是把二进制位翻转后重排数组，使得可以从底向上计算

换到模意义下就变成了原根。998244353=119\times2^{23}+1，所以可以做不超过 2^{23} 。应付一些简单的卷积足够了。它的原根是 3。

namespace NTT{
    constexpr int g=3;
    constexpr int _g=qpow(3,mod-2);
    typedef vector<int> v;
    v r;
    void NTT(v& a,bool inv){
        int n=a.size();
        foru(i,0,n-1)   if(i<r[i])  swap(a[i],a[r[i]]);
        for(int len=2;len<=n;len<<=1){
            int W=qpow(inv?_g:g,(mod-1)/len);
            for(int i=0;i<n;i+=len){
                for(int j=0,w=1;j*2<len;j++,mll(w,W)){
                    int x=a[i+j],y=mul(a[i+j+len/2],w);
                    a[i+j]=add(x,y);
                    a[i+j+len/2]=rmv(x,y);
                }
            }
        }
        if(inv){
            int _n=qpow(n,mod-2);
            foru(i,0,n-1)   mll(a[i],_n);
        }
    }
    v convolution(const v& x,const v& y){
        v A=x,B=y;
        int N=1,L=0,n=x.size(),m=y.size();
        while(N<n+m-1)  N<<=1,L++;
        A.resize(N,0),B.resize(N,0),r.resize(N,0);
        foru(i,0,N-1)   r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));
        NTT(A,0);
        NTT(B,0);
        v ret(N,0);
        foru(i,0,N-1)   ret[i]=mul(A[i],B[i]);
        NTT(ret,1);
        return ret;
    } 
}

还是很好记的

会写错的几个地方