Description

定义一个长度为 \(n\) 的序列 \(\{a\}\) 的价值为 \(\prod _{i=1}^n(a_i+i)\)

给定长度为 \(N\) 的正整数序列 \(\{a\}\)，求其所有非空子序列的权值之和

\(N\le 10^5\)

Solution

考虑最基本的 \(\rm f_{i,j}\) 表示前 \(i\) 个数，当前子序列选择了 \(j\) 个数字，转移是容易的

将 \(j\) 变成当前子序列选择了 \(i-j\) 个数字就能得到：

\[f_{i,j}=(a_i+(i-j))f_{i-1,j}+f_{i-1,j-1} \]

由于在求导操作中可以让 \(f_{i-1,j}\) 乘 \(j\) 那么再平移就又贡献给 \(f_{i,j}\) 了，这时候我们就写成 \(\rm OGF\) 形式的转移了

\[F_i(x)=(a_i+x+i)F_{i-1}(x)-xF_{i-1}'(x) \]

让 a[i]+=i，那么 \(F_n(x)=\prod_{i=1}^n (a_i+x-\frac{d}{dx}x)\)，其中的 \(\frac d{dx}\) 表示导函数，这里也就是先求导再平移系数

答案就是这个函数的系数之和，但是现在没法做

设 \(G(x)=\prod_{i=1}^n x+a_i\)，这时将 \(x-\frac{d}{dx}x\) 作为变量带入 \(G(x)\) 发现这系数之和好像还是答案！

因为 \((x-\frac d{dx}x)^i\) 的系数恰好是由 \(n-i\) 个 \(a_i\) 乘起来的，也就是说 \(x+a_i\) 中的 \(x\) 在这里起到了占位的效果

也就是说 \(F_n(x)\) 与多项式 \(\sum_{i=0}[x^i]G(x) \ (x-\frac d{dx}x)^i\) 是等价的，那么系数之和也必然是相同的

这时候答案变成了 \((x-\frac d{dx}x)^i\) 的各项系数之和乘 \([x^i]G(x)\) 再求和减去空集，那么只剩下 \((x-\frac d{dx}x)^i\) 需要考察了，如果 \(\rm DP\) 求系数的话式子还是很好看的：

\[g_{i,j}=g_{i-1,j-1}+g_{i-1,j}\times(-j) \]

这是第二类斯特林数递推式变了一下符号，使用组合意义：原来的组每加一个元素就要将所有贡献取反，所以在 \(\begin{Bmatrix}n\\ m\end{Bmatrix}\) 有 \(n-m\) 个元素拿来进行取反操作了，那么在系数中直接乘 \((-1)^{n-m}\) 就可以得到了 \(g\) 的 \(\rm EGF\)

\[G_k(x)=\sum_{i=0}^k \begin{Bmatrix}k\\i\end{Bmatrix} (-1)^{k-i}\frac{x^i}{i!} \]

这时候需求变成了求对于所有 \(k\in [1,n],G_k(x)\) 的系数和，形式化而言，对于特定的 \(k\) 就是求 \([x^k]H(x)\)，其中

\[H(x)=\sum_{i=0}^{+\infty}\sum_{k=i}^{+\infty} \begin{Bmatrix}k\\i\end{Bmatrix} (-1)^{k-i} \frac{x^k}{k!} \]

注意这里是 \(\frac {x^{k}}{k!}\)，即变成了行和，而不是机械将 \(G_i(x)\) 求和，这就很清晰了：

\[\begin{aligned}H(x)&=\sum_{k=0}^{+\infty}(-1)^{-k}\sum_{i=0}^{+\infty}\begin{Bmatrix}i\\k\end{Bmatrix}\frac{(-x)^i}{i!}\\ &=\sum_{k=0}^{+\infty}(-1)^{k}\frac{1}{k!}\sum_{i=0}^{+\infty}\sum_{j=0}^k(-1)^{k-j}\binom kj j^i\frac{(-x)^i}{i!}\\ &=\sum_{k=0}^{+\infty}(-1)^{k}\frac{1}{k!}\sum_{j=0}^k\binom kj (-1)^{k-j}\sum_{i=0}^{+\infty}j^i\frac{(-x)^i}{i!}\\ &=\sum_{k=0}^{+\infty}(-1)^{k}\frac{1}{k!}\sum_{j=0}^k\binom kj (-1)^{k-j}e^{-jx}\\ &=\sum_{k=0}^{+\infty}(-1)^k\frac{(e^{-x}-1)^k}{k!}\\ &=\sum_{k=0}^{+\infty}\frac{(1-e^{-x})^k}{k!}\\ &=e^{1-e^{-x}} \end{aligned}\]

这都是基础第二类斯特林数的运用和泰勒展开模板，不再赘述，其实这就是一列第二类斯特林数的 \(\rm EGF\) 的变式

这题还可以加强到求解每个特定长度的序列价值之和，回到最初转换下标之后的 \(\rm DP\)，给两边乘 \(e^{-x}\)，根据 \((uv)'=u'v+v'u\) 就可以得到

记得 \((e^{-x})'=-e^{-x}\) 哟

\[F_{i}(x)e^{-x}=x(F_{i-1}(x)e^{-x})'+b_iF_{i-1}e^{-x} \]

后面对着 \(F_i(x)e^{-x}\) 转移，编式子很容易，最后是一个对 \(G(x)=e^x\prod_{i=1}^n(x+b_i)\) 的多点求值，复杂度是大常数 \(\log^2\) 但是简洁得令人难以想象

据说这是 djq 主打的戴项式的入门题，恐怖如斯！

Code

使用了多项式 \(\rm Exp\) 和分治乘法，复杂度 \(\Theta(n\log^2n)\)

const int N=6e5+10;
int r[N],W[N],n,fac[N],ifac[N],inv[N],a[N];
inline void NTT(vector<int> &f,int lim,int opt){
    f.resize(lim);
    for(int i=0;i<lim;++i){
        r[i]=r[i>>1]>>1|((i&1)?(lim>>1):0);
        if(i<r[i]) swap(f[i],f[r[i]]);
    }
    for(int p=2;p<=lim;p<<=1){
        int len=p>>1; W[0]=1;
        W[1]=ksm(3,(mod-1)/p); if(opt==-1) W[1]=ksm(W[1],mod-2);
        rep(i,2,len-1) W[i]=mul(W[i-1],W[1]);
        for(int k=0;k<lim;k+=p){
            for(int l=k;l<k+len;++l){
                int tt=mul(W[l-k],f[l+len]);
                f[l+len]=del(f[l],tt);
                ckadd(f[l],tt);
            }
        }
    }
    if(opt==-1){
        int tmp=ksm(lim,mod-2);
        rep(i,0,lim-1) ckmul(f[i],tmp);
    }
    return ;
}
inline int C(int n,int m){
    if(n<m) return 0;
    return mul(fac[n],mul(ifac[m],ifac[n-m]));
}
inline vector<int> Mul(vector<int> a,vector<int> b){
    int n=a.size(),m=b.size();
    if(!m||!n) return {};
    int lim=1;
    while(lim<=(n+m)) lim<<=1;
    NTT(a,lim,1); NTT(b,lim,1);
    vector<int> F;
    rep(i,0,lim-1) F.pb(mul(a[i],b[i]));
    NTT(F,lim,-1);
    F.resize(n+m-1);
    return F;
}
inline vector<int> Inv(vector<int> F,int len){
    if(!len) return {};
    if(len==1) return {ksm(F[0],mod-2)};
    vector<int> G0=Inv(F,(len+1)>>1),G,H;
    int lim=1; while(lim<=(2*len)) lim<<=1;
    for(int i=0;i<len;++i) H.pb(F[i]);
    NTT(G0,lim,1); NTT(H,lim,1);
    rep(i,0,lim-1) G.pb(del(add(G0[i],G0[i]),mul(G0[i],mul(G0[i],H[i]))));
    NTT(G,lim,-1);
    rep(i,len,lim-1) G[i]=0; G.resize(len);
    return G;
}
inline poly integ(poly F){
    if(!F.size()) return {};
    int siz=F.size(); F.pb(mul(inv[siz],F.back()));
    for(int i=siz-1;i>0;--i) F[i]=mul(inv[i],F[i-1]);
    F[0]=0;
    return F;
}
inline poly deriv(poly F){
    int siz=F.size();
    for(int i=1;i<siz;++i) F[i-1]=mul(i,F[i]);
    F.pop_back();
    return F;
}
inline void output(poly a){
    for(auto t:a) print(t);
    puts("");
}
inline vector<int> Ln(vector<int> F,int len){
    vector<int> tmp1=Inv(F,len),tmp2=deriv(F),G;
    int lim=1; while(lim<=(len<<1)) lim<<=1;
    NTT(tmp1,lim,1); NTT(tmp2,lim,1);
    for(int i=0;i<lim;++i) G.pb(mul(tmp1[i],tmp2[i]));
    NTT(G,lim,-1);
    G=integ(G);
    G.resize(len);
    return G;
}
inline vector<int> Exp(vector<int> F,int len){
    if(len==1) return {1};
    vector<int> G0=Exp(F,(len+1)>>1); G0.resize(len);
    vector<int> ln=Ln(G0,len);
    vector<int> G;
    for(auto &t:ln) t=del(0,t);
    if(!ln.size()) ln.pb(1); else ckadd(ln[0],1);
    ln.resize(len);
    rep(i,0,len-1) ckadd(ln[i],F[i]);
    int lim=1; while(lim<=(len<<1)) lim<<=1;
    NTT(ln,lim,1); NTT(G0,lim,1);
    rep(i,0,lim-1) G.pb(mul(G0[i],ln[i]));
    NTT(G,lim,-1);
    G.resize(len);
    return G;
}
inline poly solve(int l,int r){
    if(l==r) return {a[l]+l,1}; int mid=(l+r)>>1;
    return Mul(solve(l,mid),solve(mid+1,r));
}
signed main(){
    n=6e5; fac[0]=inv[0]=1; rep(i,1,n) fac[i]=mul(fac[i-1],i);
    ifac[n]=ksm(fac[n],mod-2);
    Down(i,n,1) ifac[i-1]=mul(ifac[i],i),inv[i]=mul(ifac[i],fac[i-1]);
    n=read(); 
    rep(i,1,n) a[i]=read();
    poly r1=solve(1,n);
    poly ee; ee.resize(n+1);
    for(int i=0;i<=n;++i){
        if(i&1) ee[i]=ifac[i];
        else ee[i]=mod-ifac[i];
    }
    ckadd(ee[0],1);
    ee=Exp(ee,n+1);
    int ans=0;
    rep(i,0,n) ckadd(ans,mul(fac[i],mul(r1[i],ee[i])));
    print(del(ans,1));
    return 0;
}