打表是好文化打表是好文化打表是好文化

· · 题解

我们看到这道题，肯定想打表，那先打个暴力打表程序出来吧。

for(int i=1;i<=n;i++){
    for(int j=1;j<=i;j++){
        if(i!=j){
            s[i%2][j]=j*s[(i-1)%2][j]+s[(i-1)%2][j-1];
            s[i%2][j]%=mod;
            ans+=s[i%2][j]*er[j]%mod*qz[j]%mod;
            ans%=mod;
        }
        else{
            s[i%2][i]=1;
            ans+=er[i]%mod*qz[i]%mod;
            ans%=mod;
        }
    }
    cout<<ans<<",";
}

我们发现，表实在是太大了，根本提交不了，怎么办呢？

这时候我们可以考虑使用“分段打表”大法。

我们发现，我们跑一个数的实际的复杂度最大是 O(n)，那我们一次可以跑 10^3 个数，那我们只需要 10^2 个表就可以了，看起来非常可行！

我们发现，我们不仅要知道前面的答案总和，而且还要知道特定行的斯特林数，才能分段打表，所以我们还是得推一下式子：

第二类斯特林数 S(n,k) 表示将 n 个不同的球放入 k 个相同的盒子中，且每个盒子非空的方案数。

用容斥原理：

S(n,k) \cdot k! = \sum_{i=0}^{k} (-1)^i \binom{k}{i} (k-i)^n

推得：

S(n,k) = \frac{1}{k!} \sum_{i=0}^{k} (-1)^i \binom{k}{i} (k-i)^n

展开组合数 \binom{k}{i} = \frac{k!}{i!(k-i)!}：

S(n,k) = \frac{1}{k!} \sum_{i=0}^{k} (-1)^i \frac{k!}{i!(k-i)!} (k-i)^n

约去 k!：

\boxed{S(n,k) = \sum_{i=0}^{k} \frac{(-1)^i}{i!} \cdot \frac{(k-i)^n}{(k-i)!}}

转化为卷积形式

令：

A_i = \frac{(-1)^i}{i!}, \quad B_i = \frac{i^n}{i!}

则：

S(n,k) = \sum_{i=0}^{k} A_i \cdot B_{k-i}

这恰好是卷积的形式：

S(n,k) = (A * B)_k

由此，我们可以用 FFT 在 O(n \log n) 的时间复杂度下，求出特定行的斯特林数。

接下来就是轻松愉快的打表啦。

有人可能要说，你这不是还是用了 FFT 吗，正解不也是 FFT 吗？有什么区别呢？

但是，我的推导仅需要推出与斯特林数相关的式子即可，累加那些东西可以完全不必考虑，减少了一定的思维量呢，岂不美哉？

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 201207125211314
#define Tianyi return
#define Cute ty
const ll ty=0;
const ll mod=998244353;
const ll G=3;
const ll N=1000005;
ll s[2][500005],qz[500005],er[1000005];
ll biao[]={0,703170002,639553441,926604797,270441139,74705594,577572077,184306221,7654192,58215490,329036069,838658017,882274871,327276720,473579420,317414559,864813747,252762320,123873715,25548933,736285347,881438759,29628220,945205768,112459420,58118326,782876635,417350850,131834739,741809781,138312420,996733793,712927564,840906180,663390557,312494948,807258784,927891659,657816542,297884940,972530053,825516605,580696318,792551497,688942328,647055446,211118288,427285230,203371582,665764757,292086126,349531600,52668283,595079046,78343258,310587150,223925082,422325490,943152137,456293881,513257520,951808228,403193980,470525511,9030128,328643922,391748516,55885048,154596902,163570220,362557548,884339321,219042023,205394724,78736895,660275598,87489116,832740451,599244896,905086573,125489341,565352761,180855696,769077047,530510985,501320508,146999534,822877551,978083956,46664402,653042248,991572136,765993180,177392066,737430559,829717593,50603555,272345627,609254804,502111346,996460248};
ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1){
            res=res*a%mod;
        }
        a=a*a%mod;
        b>>=1;
    }
    Tianyi res;
}
ll A[N],B[N],fac[N],ifac[N];
void ntt(ll a[],ll n,bool inv){
    for(ll i=1,j=0;i<n;i++){
        ll bit=n>>1;
        while(j&bit){
            j^=bit;
            bit>>=1;
        }
        j^=bit;
        if(i<j){
            swap(a[i],a[j]);
        }
    }
    for(ll len=2;len<=n;len<<=1){
        ll ls=qpow(G,(mod-1)/len);
        if(inv){
            ls=qpow(ls,mod-2);
        }
        for(ll i=0;i<n;i+=len){
            ll w=1;
            for(ll j=0;j<len/2;j++){
                ll u=a[i+j],v=a[i+j+len/2]*w%mod;
                a[i+j]=(u+v)%mod;
                a[i+j+len/2]=(u-v+mod)%mod;
                w=w*ls%mod;
            }
        }
    }
    if(inv){
        ll inv_n=qpow(n,mod-2);
        for(ll i=0;i<n;i++){
            a[i]=a[i]*inv_n%mod;
        }
    }
    Tianyi;
}
void doo(ll n,ll S[]){
    fac[0]=1;
    for(ll i=1;i<=n;i++){
        fac[i]=fac[i-1]*i%mod;
    }
    ifac[n]=qpow(fac[n],mod-2);
    for(ll i=n-1;i>=0;i--){
        ifac[i]=ifac[i+1]*(i+1)%mod;
    }
    for(ll i=0;i<=n;i++){
        A[i]=ifac[i];
        if(i&1){
            A[i]=(mod-A[i])%mod;
        }
        B[i]=qpow(i,n)*ifac[i]%mod;
    }
    ll len=1;
    while(len<=2*n){
        len<<=1;
    }
    for(ll i=n+1;i<len;i++){
        A[i]=0;
        B[i]=0;
    }
    ntt(A,len,0);
    ntt(B,len,0);
    for(ll i=0;i<len;i++){
        A[i]=A[i]*B[i]%mod;
    }
    ntt(A,len,1);
    for(ll i=0;i<=n;i++){
        S[i]=A[i];
    }
    Tianyi;
}
ll S[N];
int main(){
    ll n;
    cin>>n;
    qz[1]=1;
    er[0]=1,er[1]=2;
    for(int i=2;i<=100005;i++){
        er[i]=er[i-1]*2;
        er[i]%=mod;
        qz[i]=qz[i-1]*i;
        qz[i]%=mod;
    }
    ll ls=n/1000;
    ll rep=ls*1000;
    doo(rep,S);
    if(ls){
        for(int i=0;i<=rep;i++){
            s[rep%2][i]=S[i];
        }
    }
    ll ans=biao[ls]; 
    if(n<=1000){
        ans=1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                if(i!=j){
                    s[i%2][j]=j*s[(i-1)%2][j]+s[(i-1)%2][j-1];
                    s[i%2][j]%=mod;
                    ans+=s[i%2][j]*er[j]%mod*qz[j]%mod;
                    ans%=mod;
                }
                else{
                    s[i%2][i]=1;
                    ans+=er[i]%mod*qz[i]%mod;
                    ans%=mod;
                }
            }
        }
        cout<<ans;
        return 0;
    }
    for(int i=rep+1;i<=n;i++){
        for(int j=1;j<=i;j++){
            if(i!=j){
                s[i%2][j]=j*s[(i-1)%2][j]+s[(i-1)%2][j-1];
                s[i%2][j]%=mod;
                ans+=s[i%2][j]*er[j]%mod*qz[j]%mod;
                ans%=mod;
            }
            else{
                s[i%2][i]=1;
                ans+=er[i]%mod*qz[i]%mod;
                ans%=mod;
            }
        }
    }
    cout<<ans;
    Tianyi Cute;
}