cpp_src/math/fps/StirlingSecond.hpp

View this file on GitHub
Last update: 2021-05-01 18:46:49+09:00
Include: #include "cpp_src/math/fps/StirlingSecond.hpp"
Link: https://min-25.hatenablog.com/entry/2015/04/07/160154

Code

// divide n people into k groups
// enumerate S(n, k)
// for 0 \leq k \leq n
// S(n, k) = \sum_{i=1}^k (-1)^(n-k) * \binom{k}{i} * i^n
// We can calculate i^n in O(n loglog n) time
// ref : https://min-25.hatenablog.com/entry/2015/04/07/160154

V<Mint> stirling_second(int n) {
    V<Mint> a(n + 1), b(n + 1);
    for (int i = 0; i <= n; ++i) {
        a[i] = ifact[i] * (i % 2 ? -1 : 1);
        b[i] = Mint(i).pow(n) * ifact[i];
    }
    auto c = ntt.mul(a, b);
    c.resize(n + 1);
    return c;
}

#line 1 "cpp_src/math/fps/StirlingSecond.hpp"
// divide n people into k groups
// enumerate S(n, k)
// for 0 \leq k \leq n
// S(n, k) = \sum_{i=1}^k (-1)^(n-k) * \binom{k}{i} * i^n
// We can calculate i^n in O(n loglog n) time
// ref : https://min-25.hatenablog.com/entry/2015/04/07/160154

V<Mint> stirling_second(int n) {
    V<Mint> a(n + 1), b(n + 1);
    for (int i = 0; i <= n; ++i) {
        a[i] = ifact[i] * (i % 2 ? -1 : 1);
        b[i] = Mint(i).pow(n) * ifact[i];
    }
    auto c = ntt.mul(a, b);
    c.resize(n + 1);
    return c;
}