正题

题目链接:https://www.luogu.com.cn/problem/P4091

题目大意

给出\(n\)，求

\[\sum_{i=0}^n\sum_{j=0}^i\begin{Bmatrix}i\\j\end{Bmatrix}2^jj!
\]

解题思路

看题解才知道\(2^jj!\)对这\(n\log n\)做法没有任何意义，卡了好久。

首先斯特林数的通项公式是

\[\begin{Bmatrix}n\\m\end{Bmatrix}=\frac{1}{m!}\sum_{k=0}^m(-1)^k\binom{m}{k}(m-k)^n
\]

\[\Rightarrow \sum_{k=0}^m\frac{(-1)^k(m-k)^n}{k!(m-k)!}
\]

提到这个式子来（因为如果\(j>i\)就是\(0\)所以直接不管这个限制）

\[\sum_{i=0}^n\sum_{j=0}^n2^jj!\sum_{k=0}^j\frac{(-1)^k(j-k)^n}{k!(j-k)!}
\]

然后把枚举\(i\)的那层丢到分数那里

\[\sum_{j=0}^n2^jj!\sum_{k=0}^j\frac{(-1)^k\sum_{i=0}^{n}(j-k)^i}{k!(j-k)!}
\]

然后这个后面式子就可以卷积了，定义\(F(x)=\frac{(-1)^x}{x!},G(x)=\frac{\sum_{i=0}^nx^n}{x!}\)

然后\(G\)通项公式一下就是\(G(x)=\frac{x^{n+1}-1}{(x-1)x!}\)

时间复杂度\(O(n\log n)\)

\(code\)

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const ll N=6e5+10,P=998244353;

struct poly{

    ll a[N],n;

}G,F;

ll n,ans,fac[N],inv[N],fnv[N],r[N];

ll power(ll x,ll b){

    ll ans=1;

    while(b){

        if(b&1)ans=ans*x%P;

        x=x*x%P;b>>=1;

    }

    return ans;

}

void NTT(ll *f,ll n,ll op){

    for(ll i=0;i<n;i++)

        if(r[i]<i)swap(f[i],f[r[i]]);

    for(ll p=2;p<=n;p<<=1){

        ll len=p>>1,tmp=power(3,(P-1)/p);

        if(op==-1)tmp=power(tmp,P-2);

        for(ll k=0;k<n;k+=p){

            ll buf=1;

            for(ll i=k;i<k+len;i++){

                ll tt=buf*f[i+len]%P;

                f[i+len]=(f[i]-tt+P)%P;

                f[i]=(f[i]+tt)%P;

                buf=buf*tmp%P;

            }

        }

    }

    if(op==-1){

        ll invn=power(n,P-2);

        for(ll i=0;i<n;i++)

            f[i]=f[i]*invn%P;

    }

    return;

}

void mul(poly &a,poly &b){

    ll n=1;

    while(n<=a.n+b.n)n<<=1;

    for(ll i=0;i<n;i++)

        r[i]=(r[i>>1]>>1)^((i&1)?(n>>1):0);

    NTT(a.a,n,1);NTT(b.a,n,1);

    for(ll i=0;i<n;i++)

        a.a[i]=a.a[i]*b.a[i]%P;

    NTT(a.a,n,-1);return;

}

int main()

{

    scanf("%lld",&n);

    fac[1]=fac[0]=fnv[0]=inv[1]=1;

    for(ll i=2;i<=n;i++)

        inv[i]=P-(P/i)*inv[P%i]%P;

    for(ll i=1;i<=n;i++)

        fac[i]=fac[i-1]*i%P,

        fnv[i]=inv[i]*fnv[i-1]%P;

    F.a[0]=G.a[0]=1;F.a[1]=P-1;G.a[1]=n+1;fnv[0]=0;

    for(ll i=2;i<=n;i++){

        F.a[i]=(i&1)?(P-fnv[i]):fnv[i];

        G.a[i]=(power(i,n+1)-1)*inv[i-1]%P*fnv[i]%P;

    }

    G.n=F.n=n;mul(G,F);

    for(ll i=0,pw=1;i<=n;i++){

        (ans+=G.a[i]*pw%P*fac[i]%P)%=P;

        pw=pw*2%P;

    }

    printf("%lld\n",ans);

    return 0;

}

巴特西

P4091-[HEOI2016/TJOI2016]求和【斯特林数,NTT】

正题

题目大意

解题思路

\(code\)

最新文章

热门文章