zcmimi's blog
avatar
zc
2020-07-25 19:14:00
  • 本文总阅读量
查看原题

点击跳转

f(n)=\sum_{i=0}^n \sum_{j=0}^i \begin{Bmatrix}i\\j\end{Bmatrix} 2^j j!

考虑到i<j\begin{Bmatrix}i\\j\end{Bmatrix}=0 :

f(n)=\sum_{j=0}^n 2^j j! \sum_{i=0}^n \begin{Bmatrix}i\\j\end{Bmatrix}\\ =\sum_{j=0}^n 2^j j! \sum_{i=0}^n \sum_{k=0}^j \frac{(-1)^k}{k!} \frac{(j-k)^i}{(j-k)!}\\ =\sum_{j=0}^n 2^j j! \sum_{k=0}^j \frac{(-1)^k}{k!} \frac{\sum_{i=0}^n (j-k)^i}{(j-k)!}

\displaystyle g(k)=\frac{(-1)^k}{k!}, h(k)=\frac{\sum_{i=0}^n k^i}{k!}=\frac{k^{n+1}-1}{(k-1)k!} ,

特别的: h(0)=1,h(1)=n+1

那么

f(n)=\sum_{j=0}^n 2^j j! (g\times h)(j)

卷积后即可计算

#include<bits/stdc++.h>
const int N=262144,P=998244353,G=3,Gi=332748118;
int fac[N],ifac[N],inv[N],L,r[N],h[N],g[N];
int pw(int x,int b){
    int res=1;
    while(b){
        if(b&1)res=1ll*res*x%P;
        b>>=1;x=1ll*x*x%P;
    }
    return res;
}
void getL(int n){
    for(L=1;L<n;L<<=1);
    for(int i=0;i<L;++i)
        r[i]=(r[i>>1]>>1)|((i&1)?(L>>1):0);
}
void swap(int&x,int&y){x^=y,y^=x,x^=y;}
void ntt(int*A,int typ){
    for(int i=0;i<L;++i)
        if(i<r[i])swap(A[i],A[r[i]]);
    for(int len=1;len<L;len<<=1){
        int Wn=pw(~typ?G:Gi,(P-1)/(len<<1));
        for(int i=0;i<L;i+=len<<1){
            int w=1;
            for(int k=0;k<len;++k){
                int t=1ll*A[i+k+len]*w%P;
                A[i+k+len]=(A[i+k]-t+P)%P;
                A[i+k]=(A[i+k]+t)%P;
                w=1ll*w*Wn%P;
            }
        }
    }
    if(~typ)return;
    int iL=pw(L,P-2);
    for(int i=0;i<L;++i)A[i]=1ll*A[i]*iL%P;
}
int main(){
    int n;scanf("%d",&n);

    inv[1]=1;
    for(int i=2;i<=n;++i)inv[i]=1ll*(P-P/i)*inv[P%i]%P;

    fac[0]=1;
    for(int i=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%P;
    ifac[n]=pw(fac[n],P-2);
    for(int i=n;i;--i)ifac[i-1]=1ll*ifac[i]*i%P;

    g[0]=1,g[1]=P-1;
    h[0]=1,h[1]=n+1;
    for(int i=2;i<=n;++i)
        g[i]=(i&1)?P-ifac[i]:ifac[i],
        h[i]=1ll*(pw(i,n+1)-1)*ifac[i]%P*inv[i-1]%P;

    getL(n<<1);
    ntt(g,1),ntt(h,1);
    for(int i=0;i<L;++i)
        g[i]=1ll*g[i]*h[i]%P;
    ntt(g,-1);

    int ans=0;
    for(int i=0,p2=1;i<=n;++i,p2=(p2+p2)%P)
        (ans+=1ll*p2*fac[i]%P*g[i]%P)%=P;
    printf("%d\n",ans);
}
LG 4091[TJOI2016]求和
comment评论
Search
search