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

给你斯特林数就换成通项公式，给你k次方就换成斯特林数

考虑换成通项公式之后，组合数没有什么好的处理方法

直接拆开，消一消阶乘

然后就发现了(j-k)和k！

往NTT方向靠拢

然后大功告成

其实只要想到把斯特林公式换成通项公式，考虑用NTT优化掉(j-k)^i

后面都是套路了。

#include<bits/stdc++.h>

#define reg register int

#define il inline

#define numb (ch^'0')

#define int long long

using namespace std;

typedef long long ll;

il void rd(int &x){

    char ch;x=;bool fl=false;

    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);

    (fl==true)&&(x=-x);

}

namespace Miracle{

const int N=+;

const int mod=;

const int G=;

const int GI=;

ll qm(ll x,ll y){

    ll ret=;

    while(y){

        if(y&) ret=ret*x%mod;

        x=x*x%mod;

        y>>=;

    }return ret;

}

int rev[*N];

ll a[*N],b[*N];

int n;

void NTT(ll *f,int c){

    for(reg i=;i<n;++i){

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

    }

    for(reg p=;p<=n;p<<=){

        ll gen;

        if(c==) gen=qm(G,(mod-)/p);

        else gen=qm(GI,(mod-)/p);

        int len=p/;

        for(reg l=;l<n;l+=p){

            ll buf=;

            for(reg k=l;k<l+len;++k){

                ll tmp=f[k+len]*buf%mod;

                f[k+len]=(f[k]-tmp+mod)%mod;

                f[k]=(f[k]+tmp)%mod;

                buf=buf*gen%mod;

            }

        }

    }

}

ll jie[N],inv[N],ni[N];

int main(){

    rd(n);jie[]=;

    for(reg i=;i<=n;++i) jie[i]=jie[i-]*i%mod;

    inv[n]=qm(jie[n],mod-);inv[]=;

    for(reg i=n-;i>=;--i) inv[i]=inv[i+]*(i+)%mod;

    for(reg i=;i<=n;++i) ni[i]=((mod-mod/i)*ni[mod%i]+mod)%mod;

    for(reg i=;i<=n;++i){

        if(i&) a[i]=mod-inv[i];

        else a[i]=inv[i];

        if(i==) b[i]=n+;

        else if(i==) b[i]=;

        else b[i]=(qm(i,n+)-+mod)%mod*qm(i-,mod-)%mod*inv[i]%mod;

    }

    int m;

    int lp=n;

    for(m=n+n,n=;n<=m;n<<=);

    for(reg i=;i<n;++i){

        rev[i]=(rev[i>>]>>)|((i&)?n>>:);

    }

//    for(reg i=0;i<n;++i){

//        cout<<a[i]<<" ";

//    }cout<<endl;

//    for(reg i=0;i<n;++i){

//        cout<<b[i]<<" ";

//    }cout<<endl;

    NTT(a,);NTT(b,);

    for(reg i=;i<n;++i) b[i]=(ll)b[i]*a[i]%mod;

    NTT(b,-);ll yuan=qm(n,mod-);

    for(reg i=;i<n;++i) b[i]=b[i]*yuan%mod;

    ll ans=;

    for(reg j=;j<=lp;++j){

       // cout<<" bj "<<j<<" : "<<b[j]<<endl;

        ans=(ans+qm(,j)*jie[j]%mod*b[j]%mod)%mod;

        //cout<<" ans "<<ans<<endl;

    }

    printf("%lld",ans);

    return ;

}

}

signed main(){

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

   Date: 2018/12/28 21:51:13

*/