[HEOI2016/TJOI2016]求和(第二类斯特林数)

题目

[HEOI2016/TJOI2016]求和

关于斯特林数与反演的更多姿势\(\Longrightarrow\)点这里

做法

\[\begin{aligned}\\
Ans&=\sum\limits_{i=0}^n \sum\limits_{j=0}^i \begin{Bmatrix}i\\j\end{Bmatrix}2^j×j!~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~1\\
&=\sum\limits_{i=0}^n \sum\limits_{j=0}^n \begin{Bmatrix}i\\j\end{Bmatrix}2^j×j!~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~2\\
&=\sum\limits_{j=0}^n 2^j×j!\sum\limits_{i=0}^n \begin{Bmatrix}i\\j\end{Bmatrix}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~3\\
&=\sum\limits_{j=0}^n 2^j×j!\sum\limits_{i=0}^n \sum\limits_{k=0}^j\frac{(-1)^k}{k!}\cdot\frac{(j-k)^i}{(j-k)!}~~~~~~~~~~~~~~~~~~~~4\\
&=\sum\limits_{j=0}^n 2^j×j!\sum\limits_{k=0}^j\frac{(-1)^k}{k!}\cdot\frac{ \sum\limits_{i=0}^n (j-k)^i}{(j-k)!}~~~~~~~~~~~~~~~~~~~~~~5\\
&=\sum\limits_{j=0}^n 2^j×j!\sum\limits_{k=0}^j\frac{(-1)^k}{k!}\cdot \frac{(j-k)^{n+1}-1}{(j-k-1)(j-k)!}~~~~~~~6\\
\end{aligned}\]

\(2：\begin{Bmatrix}i\\j\end{Bmatrix}=0(i>j)\)
\(3：\)移项
\(4：\)第二类斯特林的性质
\(5：\)移项化卷积
\(6：\)等比公式

总结

这题非常有意思，最后一步对于蒟蒻来说还是少见的，推到\(4\)谁都会，然后就无从下手了

以至于会从头考虑\(2^j×j!\)的性质，特别容易想偏

Code

#include<bits/stdc++.h>

typedef int LL;

typedef long long L;

const LL maxn=3e5+9,mod=998244353,g=3,_g=332748118;

inline LL Pow(LL base,LL b){

    LL ret(1);

    while(b){

        if(b&1) ret=(L)ret*base%mod; base=(L)base*base%mod; b>>=1;

    }return ret;

}

LL fac[maxn],fav[maxn],r[maxn],F[maxn],G[maxn],W[maxn];

inline void NTT(LL *a,LL n,LL type){

    for(LL i=0;i<n;++i) if(i<r[i]) std::swap(a[i],a[r[i]]);

    for(LL mid=1;mid<n;mid<<=1){

        LL wn(Pow(type?g:_g,(mod-1)/(mid<<1)));

        W[0]=1; for(LL i=1;i<mid;++i) W[i]=(L)W[i-1]*wn%mod;

        for(LL R=mid<<1,j=0;j<n;j+=R)

            for(LL k=0;k<mid;++k){

            	LL x(a[j+k]),y((L)W[k]*a[j+mid+k]%mod);

            	a[j+k]=x+y; if(a[j+k]>=mod) a[j+k]%=mod;

				a[j+mid+k]=x-y; if(a[j+mid+k]<0) a[j+mid+k]+=mod;

            }

    }

}

inline LL Fir(LL n){

    LL limit(1),len(0);

    while(limit<n){

        limit<<=1; ++len;

    }

    for(LL i=0;i<limit;++i) r[i]=(r[i>>1]>>1)|((i&1)<<len-1);

    return limit;

}

inline LL Solve_fg(LL n){

    for(LL i=0;i<=n;++i) F[i]=(L)(i&1?mod-1:1)*fav[i]%mod;

    for(LL i=0;i<=n;++i) G[i]=(L)(Pow(i,n+1)+mod-1)%mod*Pow(i-1<0?i+mod-1:i-1,mod-2)%mod*fav[i]%mod;

    G[1]=n+1;

    LL limit(Fir(n+1<<1));

    NTT(F,limit,1); NTT(G,limit,1);

    for(LL i=0;i<limit;++i) F[i]=(L)F[i]*G[i]%mod;

    NTT(F,limit,0);

    LL ty(Pow(limit,mod-2)); for(LL i=0;i<=n;++i) F[i]=(L)F[i]*ty%mod;

    LL ret(0);

    for(LL i=0;i<=n;++i) ret=(L)(ret+(L)Pow(2,i)*fac[i]%mod*F[i]%mod)%mod;

    return ret;

}

LL n;

int main(){

    scanf("%d",&n);

    fac[0]=fac[1]=1;

    for(LL i=2;i<=n;++i) fac[i]=(L)fac[i-1]*i%mod;

    fav[n]=Pow(fac[n],mod-2);

    for(LL i=n;i>=1;--i) fav[i-1]=(L)fav[i]*i%mod;

    printf("%d",Solve_fg(n));

    return 0;

}

巴特西

[HEOI2016/TJOI2016]求和(第二类斯特林数)

题目

做法

总结

Code

最新文章

热门文章