math_mod/stirling_number.hpp

• View this file on GitHub
• Last update: 2025-04-05 12:46:42+09:00
• Include: #include "math_mod/stirling_number.hpp"

Depends on

• fps/product.hpp

Verified with

• verify/yosupo_math/enumerate_stirling_number_of_the_first_kind.test.cpp

Code

#ifndef KK2_MATH_MOD_STIRLING_NUMBER_HPP
#define KK2_MATH_MOD_STIRLING_NUMBER_HPP 1

#include <vector>

#include "../fps/product.hpp"

namespace kk2 {

template <class FPS, class mint = typename FPS::value_type>
std::vector<mint> enumerate_stirling_number_of_the_first_kind(int n) {
    std::vector<FPS> a(n);
    for (int i = 0; i < n; ++i) { a[i] = FPS{-i, 1}; }
    return all_prod(a);
}

} // namespace kk2

#endif // KK2_MATH_MOD_STIRLING_NUMBER_HPP

#line 1 "math_mod/stirling_number.hpp"



#include <vector>

#line 1 "fps/product.hpp"



#line 5 "fps/product.hpp"

namespace kk2 {

template <class FPS, class mint = typename FPS::value_type>
FPS all_prod(const std::vector<FPS> &a) {
    return inner_all_prod(a, 0, (int)a.size());
}

template <class FPS, class mint = typename FPS::value_type>
FPS inner_all_prod(const std::vector<FPS> &a, int l, int r) {
    if (l == r) return FPS{1};
    if (l + 1 == r) return a[l];
    int m = (l + r) >> 1;
    return inner_all_prod(a, l, m) * inner_all_prod(a, m, r);
}

} // namespace kk2


#line 7 "math_mod/stirling_number.hpp"

namespace kk2 {

template <class FPS, class mint = typename FPS::value_type>
std::vector<mint> enumerate_stirling_number_of_the_first_kind(int n) {
    std::vector<FPS> a(n);
    for (int i = 0; i < n; ++i) { a[i] = FPS{-i, 1}; }
    return all_prod(a);
}

} // namespace kk2

Back to top page