bernoulli_number<ft>(int n) -> [T]
#pragma once #include <cstdint> #include <vector> #include "Mylib/Combinatorics/factorial_table.cpp" namespace haar_lib { template < const auto &ft, typename T = typename std::remove_reference_t<decltype(ft)>::value_type> std::vector<T> bernoulli_number(int n) { std::vector<T> ret(n + 1); ret[0] = 1; for (int64_t i = 1; i <= n; ++i) { for (int k = 0; k <= i - 1; ++k) { ret[i] += ft.C(i + 1, k) * ret[k]; } ret[i] /= i + 1; ret[i] = -ret[i]; } return ret; } } // namespace haar_lib
#line 2 "Mylib/Combinatorics/bernoulli_number.cpp" #include <cstdint> #include <vector> #line 2 "Mylib/Combinatorics/factorial_table.cpp" #include <cassert> #line 5 "Mylib/Combinatorics/factorial_table.cpp" namespace haar_lib { template <typename T> class factorial_table { public: using value_type = T; private: int N_; std::vector<T> f_table_, if_table_; public: factorial_table() {} factorial_table(int N) : N_(N) { f_table_.assign(N + 1, 1); if_table_.assign(N + 1, 1); for (int i = 1; i <= N; ++i) { f_table_[i] = f_table_[i - 1] * i; } if_table_[N] = f_table_[N].inv(); for (int i = N; --i >= 0;) { if_table_[i] = if_table_[i + 1] * (i + 1); } } T factorial(int64_t i) const { assert(0 <= i and i <= N_); return f_table_[i]; } T inv_factorial(int64_t i) const { assert(0 <= i and i <= N_); return if_table_[i]; } T P(int64_t n, int64_t k) const { if (n < k or n < 0 or k < 0) return 0; return factorial(n) * inv_factorial(n - k); } T C(int64_t n, int64_t k) const { if (n < k or n < 0 or k < 0) return 0; return P(n, k) * inv_factorial(k); } T H(int64_t n, int64_t k) const { if (n == 0 and k == 0) return 1; return C(n + k - 1, k); } }; } // namespace haar_lib #line 5 "Mylib/Combinatorics/bernoulli_number.cpp" namespace haar_lib { template < const auto &ft, typename T = typename std::remove_reference_t<decltype(ft)>::value_type> std::vector<T> bernoulli_number(int n) { std::vector<T> ret(n + 1); ret[0] = 1; for (int64_t i = 1; i <= n; ++i) { for (int k = 0; k <= i - 1; ++k) { ret[i] += ft.C(i + 1, k) * ret[k]; } ret[i] /= i + 1; ret[i] = -ret[i]; } return ret; } } // namespace haar_lib