一个简单的求Bell数的方法

前言

贝尔数大概大家都不陌生，但是怎么求却有许多种方式，有根据定义O(n2)求的，有用NTT或者多项式求逆O(nlogn)的求法。这些做法都太垃圾了 这里给大家介绍一种O(nlogn)的做法。

正文

首先根据贝尔数的定义，有

Bn=∑m=0nS(n,m)

其中S(n,m)是第二类斯特林数。
那么再由第二类斯特林数的展开式可得

原式=∑m=0n1m!∑k=0m(−1)kC(m,k)(m−k)n=∑m=0n∑k=0m(−1)kk!(m−k)n(m−k)!

这样子，设Ai=(−1)ii!，Bi=ini!，这样子就是

原式=∑m=0n∑k=0mAkBm−k

可以NTT，但是太麻烦，我们注意到对于Ai这一项，它只会与B0，B1，B2...Bn−i相乘，就是一个前缀和的形式，所以Ai这一项的贡献就算了出来，这样子的话，预处理A,B以及其前缀和，然后for一遍，把每一项Ai的贡献算出来加上去就可以了，这样子是O(nlogn)的（要算快速幂）。
代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll p = 998244353;
const ll N = 1e5+10;
ll fac[N] , facinv[N] , n , a[N] , b[N] , sum[N] , ans;
ll qpow(ll a, ll b, ll p) {
    ll res = 1;
    for(; b; b >>= 1, a = (a * a) % p) {
        if(b & 1) res = (res * a) % p;
    }
    return res;
}
void pre() {
    fac[0]=1;
    facinv[0] = 1;
    for(int i = 1; i <= n; i ++ ) {
        fac[i] = ( fac[i-1] * i ) % p ;
        facinv[i] = qpow( fac[i] , p - 2 , p ) ;
    }
}

int main() {
    scanf("%lld", &n);
    pre();
    for (int i = 0 ; i <= n ; i++) {
        a[i] = facinv[i];
        if ( i % 2 ) a[i] = p - a[i] ;
        b[i] = qpow( i , n , p ) * facinv[i] % p;
        sum[i] = ( sum[i-1] + b[i] ) % p;
    }
    for (int i = 0 ; i <= n ; i++ ) ans = ( ans + a[i] * sum[n-i] ) % p;
    cout<<ans;
    return 0;
}