Stirling number of 2nd kind

Stirling number of 2nd kind

The Stirling numbers of the second kind counts the number of ways to partition a set of n objects into k non-empty subsets.

Code - O(K*log(N)^2)

const ll MOD = 998244353;
const int MX = 2e5 + 5;
ll n, k, f[MX];

ll fpow(ll a, ll p) {
    ll res = 1LL;
    while (p) {
        if (p & 1LL) res = res * a % MOD;
        a = a * a % MOD;
        p >>= 1LL;
    }
    return res;
}

ll nCk(ll N, ll K) {
    ll res = f[N];
    res = res * fpow(f[N - K], MOD - 2LL) % MOD;
    res = res * fpow(f[K], MOD - 2LL) % MOD;
    return res % MOD;
}

ll stirling(ll N, ll K) { // O(K * log(N)^2) 
    ll res = 0 LL;
    for (int j = 0; j <= K; ++j) {
        ll tmp = nCk(K, j) * fpow(j, N) % MOD;
        if ((K - j) & 1) tmp = -tmp;
        res += tmp;
        if (res >= MOD) res -= MOD;
        if (res < 0) res += MOD;
    }
    res = res * fpow(f[K], MOD - 2LL) % MOD;
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    f[0] = 1LL;
    for (int i = 1; i < MX; ++i) f[i] = f[i - 1] * i * 1LL % MOD;
}