Submit Info #53623

Problem Lang User Status Time Memory
Partition Function cpp-acl suisen AC 393 ms 23.37 MiB

ケース詳細
Name Status Time Memory
0_00 AC 1 ms 0.61 MiB
100000_00 AC 89 ms 6.02 MiB
10000_00 AC 10 ms 1.30 MiB
1000_00 AC 1 ms 0.71 MiB
100_00 AC 1 ms 0.61 MiB
1_00 AC 1 ms 0.61 MiB
200000_00 AC 188 ms 11.46 MiB
300000_00 AC 378 ms 20.00 MiB
400000_00 AC 386 ms 22.24 MiB
500000_00 AC 393 ms 23.37 MiB
example_00 AC 1 ms 0.61 MiB

#define PROBLEM "https://judge.yosupo.jp/problem/partition_function" #include <iostream> #include <atcoder/modint> #include <atcoder/convolution> #include <algorithm> #include <cassert> #include <iostream> #include <vector> namespace suisen { template <typename mint> class inv_mods { public: inv_mods() {} inv_mods(int n) { ensure(n); } const mint& operator[](int i) const { ensure(i); return invs[i]; } static void ensure(int n) { int sz = invs.size(); if (sz < 2) invs = {0, 1}, sz = 2; if (sz < n + 1) { invs.resize(n + 1); for (int i = sz; i <= n; ++i) invs[i] = mint(mod - mod / i) * invs[mod % i]; } } private: static std::vector<mint> invs; static constexpr int mod = mint::mod(); }; template <typename mint> std::vector<mint> inv_mods<mint>::invs{}; } namespace suisen { template <typename mint> using convolution_t = std::vector<mint> (*)(const std::vector<mint> &, const std::vector<mint> &); template <typename mint> class FPS : public std::vector<mint> { public: using std::vector<mint>::vector; FPS(const std::initializer_list<mint> l) : std::vector<mint>::vector(l) {} static void set_multiplication(convolution_t<mint> multiplication) { FPS<mint>::mult = multiplication; } inline FPS& operator=(const std::vector<mint> &&f) & noexcept { std::vector<mint>::operator=(std::move(f)); return *this; } inline FPS& operator=(const std::vector<mint> &f) & { std::vector<mint>::operator=(f); return *this; } inline const mint operator[](int n) const noexcept { return n <= deg() ? unsafe_get(n) : 0; } inline mint& operator[](int n) noexcept { ensure_deg(n); return unsafe_get(n); } inline int size() const noexcept { return std::vector<mint>::size(); } inline int deg() const noexcept { return size() - 1; } inline int normalize() { while (this->size() and this->back() == 0) this->pop_back(); return deg(); } inline FPS& pre_inplace(int max_deg) noexcept { if (deg() > max_deg) this->resize(std::max(0, max_deg + 1)); return *this; } inline FPS pre(int max_deg) const noexcept { return FPS(*this).pre_inplace(max_deg); } inline FPS operator+() const { return FPS(*this); } FPS operator-() const { FPS f(*this); for (auto &e : f) e = mint::mod() - e; return f; } inline FPS& operator++() { ++(*this)[0]; return *this; } inline FPS& operator--() { --(*this)[0]; return *this; } inline FPS& operator+=(const mint x) { (*this)[0] += x; return *this; } inline FPS& operator-=(const mint x) { (*this)[0] -= x; return *this; } FPS& operator+=(const FPS &g) { ensure_deg(g.deg()); for (int i = 0; i <= g.deg(); ++i) unsafe_get(i) += g.unsafe_get(i); return *this; } FPS& operator-=(const FPS &g) { ensure_deg(g.deg()); for (int i = 0; i <= g.deg(); ++i) unsafe_get(i) -= g.unsafe_get(i); return *this; } inline FPS& operator*=(const FPS &g) { return *this = FPS<mint>::mult(*this, g); } inline FPS& operator*=( FPS &&g) { return *this = FPS<mint>::mult(*this, g); } inline FPS& operator*=(const mint x) { for (auto &e : *this) e *= x; return *this; } FPS& operator/=(FPS &&g) { const int fd = normalize(), gd = g.normalize(); assert(gd >= 0); if (fd < gd) { this->clear(); return *this; } if (gd == 0) return *this *= g.unsafe_get(0).inv(); static constexpr int THRESHOLD_NAIVE_POLY_QUOTIENT = 256; if (gd <= THRESHOLD_NAIVE_POLY_QUOTIENT) { *this = std::move(naive_div_inplace(std::move(g), gd).first); return *this; } std::reverse(this->begin(), this->end()), std::reverse(g.begin(), g.end()); const int k = fd - gd; *this *= g.inv_inplace(k), this->resize(k + 1); std::reverse(this->begin(), this->end()); return *this; } FPS& operator%=(FPS &&g) { int fd = normalize(), gd = g.normalize(); assert(gd >= 0); if (fd < gd) return *this; if (gd == 0) { this->clear(); return *this; } static constexpr int THRESHOLD_NAIVE_REMAINDER = 256; if (gd <= THRESHOLD_NAIVE_REMAINDER) return naive_div_inplace(std::move(g), gd).second; *this -= g * (*this / g); return pre_inplace(gd - 1); } inline FPS& operator/=(const FPS &g) { return *this /= FPS(g); } inline FPS& operator%=(const FPS &g) { return *this %= FPS(g); } FPS& operator<<=(const int shamt) { this->insert(this->begin(), shamt, 0); return *this; } FPS& operator>>=(const int shamt) { if (shamt > size()) this->clear(); else this->erase(this->begin(), this->begin() + shamt); return *this; } inline FPS operator+(FPS &&g) const { return FPS(*this) += std::move(g); } inline FPS operator-(FPS &&g) const { return FPS(*this) -= std::move(g); } inline FPS operator*(FPS &&g) const { return FPS(*this) *= std::move(g); } inline FPS operator/(FPS &&g) const { return FPS(*this) /= std::move(g); } inline FPS operator%(FPS &&g) const { return FPS(*this) %= std::move(g); } inline FPS operator+(const FPS &g) const { return FPS(*this) += g; } inline FPS operator+(const mint x) const { return FPS(*this) += x; } inline FPS operator-(const FPS &g) const { return FPS(*this) -= g; } inline FPS operator-(const mint x) const { return FPS(*this) -= x; } inline FPS operator*(const FPS &g) const { return FPS(*this) *= g; } inline FPS operator*(const mint x) const { return FPS(*this) *= x; } inline FPS operator/(const FPS &g) const { return FPS(*this) /= g; } inline FPS operator%(const FPS &g) const { return FPS(*this) %= g; } inline friend FPS operator*(const mint x, const FPS &f) { return f * x; } inline friend FPS operator*(const mint x, FPS &&f) { return f *= x; } inline FPS operator<<(const int shamt) { return FPS(*this) <<= shamt; } inline FPS operator>>(const int shamt) { return FPS(*this) >>= shamt; } FPS& diff_inplace() { if (this->size() == 0) return *this; for (int i = 1; i <= deg(); ++i) unsafe_get(i - 1) = unsafe_get(i) * i; this->pop_back(); return *this; } FPS& intg_inplace() { int d = deg(); ensure_deg(d + 1); for (int i = d; i >= 0; --i) unsafe_get(i + 1) = unsafe_get(i) * invs[i + 1]; unsafe_get(0) = 0; return *this; } FPS& inv_inplace(const int max_deg) { FPS res { unsafe_get(0).inv() }; for (int k = 1; k <= max_deg; k *= 2) { FPS tmp(this->pre(k * 2) * (res * res)); res *= 2, res -= tmp.pre_inplace(2 * k); } return *this = std::move(res), pre_inplace(max_deg); } FPS& log_inplace(const int max_deg) { FPS f_inv = inv(max_deg); diff_inplace(), *this *= f_inv, pre_inplace(max_deg - 1), intg_inplace(); return *this; } FPS& exp_inplace(const int max_deg) { FPS res {1}; for (int k = 1; k <= max_deg; k *= 2) res *= ++(pre(k * 2) - res.log(k * 2)), res.pre_inplace(k * 2); return *this = std::move(res), pre_inplace(max_deg); } FPS& pow_inplace(const long long k, const int max_deg) { int tlz = 0; while (tlz <= deg() and unsafe_get(tlz) == 0) ++tlz; if (tlz * k > max_deg) { this->clear(); return *this; } *this >>= tlz; mint base = (*this)[0]; *this *= base.inv(), log_inplace(max_deg), *this *= k, exp_inplace(max_deg), *this *= base.pow(k); return *this <<= tlz * k, pre_inplace(max_deg); } inline FPS diff() const { return FPS(*this).diff_inplace(); } inline FPS intg() const { return FPS(*this).intg_inplace(); } inline FPS inv(const int max_deg) const { return FPS(*this).inv_inplace(max_deg); } inline FPS log(const int max_deg) const { return FPS(*this).log_inplace(max_deg); } inline FPS exp(const int max_deg) const { return FPS(*this).exp_inplace(max_deg); } inline FPS pow(const long long k, const int max_deg) const { return FPS(*this).pow_inplace(k, max_deg); } private: static inv_mods<mint> invs; static convolution_t<mint> mult; inline void ensure_deg(int d) { if (deg() < d) this->resize(d + 1, 0); } inline const mint& unsafe_get(int i) const { return std::vector<mint>::operator[](i); } inline mint& unsafe_get(int i) { return std::vector<mint>::operator[](i); } std::pair<FPS, FPS&> naive_div_inplace(FPS &&g, const int gd) { const int k = deg() - gd; mint head_inv = g.unsafe_get(gd).inv(); FPS q(k + 1); for (int i = k; i >= 0; --i) { mint div = this->unsafe_get(i + gd) * head_inv; q.unsafe_get(i) = div; for (int j = 0; j <= gd; ++j) this->unsafe_get(i + j) -= div * g.unsafe_get(j); } return {q, pre_inplace(gd - 1)}; } }; template <typename mint> convolution_t<mint> FPS<mint>::mult = [](const auto &, const auto &) { std::cerr << "convolution function is not available." << std::endl; assert(false); return std::vector<mint>{}; }; } // namespace suisen #include <cassert> #include <vector> namespace suisen { template <typename T, typename U = T> class factorial { public: factorial() {} factorial(int n) { ensure(n); } inline const T& fac(const int i) { ensure(i); return _fac[i]; } inline const U& fac_inv(const int i) { ensure(i); return _fac_inv[i]; } inline U binom(const int n, const int r) { if (n < 0 or r < 0 or n < r) return 0; ensure(n); return _fac[n] * _fac_inv[r] * _fac_inv[n - r]; } inline U perm(const int n, const int r) { if (n < 0 or r < 0 or n < r) return 0; ensure(n); return _fac[n] * _fac_inv[n - r]; } private: static std::vector<T> _fac; static std::vector<U> _fac_inv; static void ensure(const int n) { int sz = _fac.size(); if (n + 1 <= sz) return; int new_size = std::max(n + 1, sz * 2); _fac.resize(new_size), _fac_inv.resize(new_size); for (int i = sz; i < new_size; ++i) _fac[i] = _fac[i - 1] * i; _fac_inv[new_size - 1] = U(1) / _fac[new_size - 1]; for (int i = new_size - 1; i > sz; --i) _fac_inv[i - 1] = _fac_inv[i] * i; } }; template <typename T, typename U> std::vector<T> factorial<T, U>::_fac {1}; template <typename T, typename U> std::vector<U> factorial<T, U>::_fac_inv {1}; } // namespace suisen namespace suisen { /** * return: * vector<mint> v s.t. v[i] = S1[n,n-i] for i=0,...,k (unsigned) * constraints: * 0 <= n <= 10^6 */ template <typename mint> std::vector<mint> stirling_number1_reversed(int n) { factorial<mint> fac(n); int l = 0; while ((n >> l) != 0) ++l; FPS<mint> a {1}; int m = 0; while (l --> 0) { FPS<mint> f(m + 1), g(m + 1); mint powm = 1; for (int i = 0; i <= m; ++i, powm *= m) { f[i] = powm * fac.fac_inv(i); g[i] = a[i] * fac.fac(m - i); } f *= g, f.pre_inplace(m); for (int i = 0; i <= m; ++i) f[i] *= fac.fac_inv(m - i); a *= f, m *= 2, a.pre_inplace(m); if ((n >> l) & 1) { a.push_back(0); for (int i = m; i > 0; --i) a[i] += m * a[i - 1]; ++m; } } return a; } template <typename mint> std::vector<mint> stirling_number1(int n) { auto a(stirling_number1_reversed<mint>(n)); std::reverse(a.begin(), a.end()); return a; } /** * return: * vector<mint> v s.t. v[i] = S1[n,n-i] for i=0,...,k, where S1 is the stirling number of the first kind (unsigned). * constraints: * - 0 <= n <= 10^18 * - 0 <= k <= 5000 * - k < mod */ template <typename mint> std::vector<mint> stirling_number1_reversed(const long long n, const int k) { inv_mods<mint> invs(k + 1); std::vector<mint> a(k + 1, 0); a[0] = 1; int l = 0; while (n >> l) ++l; mint m = 0; while (l --> 0) { std::vector<mint> b(k + 1, 0); for (int j = 0; j <= k; ++j) { mint tmp = 1; for (int i = j; i <= k; ++i) { b[i] += a[j] * tmp; tmp *= (m - i) * invs[i - j + 1] * m; } } for (int i = k + 1; i --> 0;) { mint sum = 0; for (int j = 0; j <= i; ++j) sum += a[j] * b[i - j]; a[i] = sum; } m *= 2; if ((n >> l) & 1) { for (int i = k; i > 0; --i) a[i] += m * a[i - 1]; ++m; } } return a; } /** * return: * vector<mint> v s.t. v[i] = S2[n,i] for i=0,...,k * constraints: * 0 <= n <= 10^6 */ template <typename mint> std::vector<mint> stirling_number2(int n) { factorial<mint> fac(n); FPS<mint> a(n + 1), b(n + 1); for (int i = 0; i <= n; ++i) { a[i] = mint(i).pow(n) * fac.fac_inv(i); b[i] = i & 1 ? -fac.fac_inv(i) : fac.fac_inv(i); } a *= b, a.pre_inplace(n); return a; } template <typename mint> std::vector<mint> bernoulli_number(int n) { factorial<mint> fac(n); FPS<mint> a(n + 1); for (int i = 0; i <= n; ++i) a[i] = fac.fac_inv(i + 1); a.inv_inplace(n), a.resize(n + 1); for (int i = 2; i <= n; ++i) a[i] *= fac.fac(i); return a; } template <typename mint> std::vector<mint> partition_number(int n) { FPS<mint> inv(n + 1); inv[0] = 1; for (int i = 1, k = 1; k <= n; k += 3 * i + 1, i++) { if (i & 1) --inv[k]; else ++inv[k]; } for (int i = 1, k = 2; k <= n; k += 3 * i + 2, i++) { if (i & 1) --inv[k]; else ++inv[k]; } inv.inv_inplace(n), inv.resize(n + 1); return inv; } } // namespace suisen using mint = atcoder::modint998244353; int main() { suisen::FPS<mint>::set_multiplication([](const auto &a, const auto &b) { return atcoder::convolution(a, b); }); int n; std::cin >> n; auto f = suisen::partition_number<mint>(n); for (int i = 0; i <= n; ++i) { std::cout << f[i].val() << " \n"[i == n]; } return 0; }