Submit Info #34845

Problem Lang User Status Time Memory
Stirling Number of the First Kind cpp pikelrik AC 1277 ms 129.28 MiB

ケース詳細
Name Status Time Memory
0_00 AC 2 ms 0.67 MiB
1_00 AC 0 ms 0.61 MiB
262143_00 AC 674 ms 69.74 MiB
262144_00 AC 669 ms 69.74 MiB
2_00 AC 1 ms 0.67 MiB
491519_00 AC 1264 ms 127.65 MiB
499999_00 AC 1277 ms 129.16 MiB
500000_00 AC 1274 ms 129.28 MiB
5000_00 AC 10 ms 1.80 MiB
example_00 AC 1 ms 0.62 MiB

#include <bits/stdc++.h> using namespace std; namespace modular { template <typename> struct is_modular : std::false_type { }; template<int M> struct static_mint { static_assert(0 < M, "Module must be positive"); using mint = static_mint; constexpr static int get_mod() { return M; } int val; static_mint(): val() {} static_mint(long long x) : val(x % M) { if (val < 0) val += M; } mint pow(long long n) const { mint ans = 1, x(*this); while (n) { if (n & 1) ans *= x; x *= x; n /= 2; } return ans; } mint inv() const { return pow(M - 2); } friend mint pow(const mint &m, long long n) { return m.pow(n); } friend mint inv(const mint &m) { return m.inv(); } mint operator+() const { mint m; m.val = val; return m; } mint operator-() const { mint m; m.val = M - val; return m; } mint &operator+=(const mint &m) { if ((val += m.val) >= M) val -= M; return *this; } mint &operator-=(const mint &m) { if ((val -= m.val) < 0) val += M; return *this; } mint &operator*=(const mint &m) { val = (long long) val * m.val % M; return *this; } mint &operator/=(const mint &m) { val = (long long) val * m.inv().val % M; return *this; } friend mint operator+ (const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; } friend mint operator- (const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; } friend mint operator* (const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; } friend mint operator/ (const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; } friend bool operator==(const mint &lhs, const mint &rhs) { return lhs.val == rhs.val; } friend bool operator!=(const mint &lhs, const mint &rhs) { return lhs.val != rhs.val; } mint &operator++() { return *this += 1; } mint &operator--() { return *this -= 1; } mint operator++(int) { mint result(*this); *this += 1; return result; } mint operator--(int) { mint result(*this); *this -= 1; return result; } template <typename T> explicit operator T() const { return T(val); } friend std::ostream &operator<<(std::ostream &os, const mint &m) { return os << m.val; } friend std::istream &operator>>(std::istream &is, mint &m) { long long x; is >> x; m = x; return is; } }; template <int M> struct is_modular<static_mint<M>> : std::true_type { }; struct dynamic_mint { static int M; static void set_mod(int m) { assert(0 < m); M = m; } static int get_mod() { return M; } using mint = dynamic_mint; int val; dynamic_mint(): val() {} dynamic_mint(long long x) : val(x % M) { if (val < 0) { val += M; } } mint pow(long long n) const { mint ans = 1, x(*this); while (n) { if (n & 1) ans *= x; x *= x; n /= 2; } return ans; } mint inv() const { return pow(M - 2); } friend mint pow(const mint &m, long long n) { return m.pow(n); } friend mint inv(const mint &m) { return m.inv(); } mint operator+() const { mint m; m.val = val; return m; } mint operator-() const { mint m; m.val = M - val; return m; } mint &operator+=(const mint &m) { if ((val += m.val) >= M) val -= M; return *this; } mint &operator-=(const mint &m) { if ((val -= m.val) < 0) val += M; return *this; } mint &operator*=(const mint &m) { val = (long long) val * m.val % M; return *this; } mint &operator/=(const mint &m) { val = (long long) val * m.inv().val % M; return *this; } friend mint operator+ (const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; } friend mint operator- (const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; } friend mint operator* (const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; } friend mint operator/ (const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; } friend bool operator==(const mint &lhs, const mint &rhs) { return lhs.val == rhs.val; } friend bool operator!=(const mint &lhs, const mint &rhs) { return lhs.val != rhs.val; } mint &operator++() { return *this += 1; } mint &operator--() { return *this -= 1; } mint operator++(int) { mint result(*this); *this += 1; return result; } mint operator--(int) { mint result(*this); *this -= 1; return result; } template <typename T> explicit operator T() const { return T(val); } friend std::ostream &operator<<(std::ostream &os, const mint &m) { return os << m.val; } friend std::istream &operator>>(std::istream &is, mint &m) { long long x; is >> x; m = x; return is; } }; int dynamic_mint::M; template <> struct is_modular<dynamic_mint> : std::true_type { }; } namespace ntt { template <int M> using mint = modular::static_mint<M>; //default mint template <int P> struct prime_info { constexpr static int root = 0, root_pw = 0; }; template <> struct prime_info<7340033> { constexpr static int root = 5, root_pw = 1 << 20; }; template <> struct prime_info<998244353> { constexpr static int root = 15311432, root_pw = 1 << 23; }; template <> struct prime_info<754974721> { constexpr static int root = 739831874, root_pw = 1 << 24; }; template <> struct prime_info<167772161> { constexpr static int root = 243, root_pw = 1 << 25; }; template <> struct prime_info<469762049> { constexpr static int root = 2187, root_pw = 1 << 26; }; std::vector<int> rev = {0}; void compute_bit_reverse(int lg) { static int computed = 0; if (lg <= computed) return; rev.resize(1 << lg); for (int i = (1 << computed); i < (1 << lg); i++) { rev[i] = (rev[i >> 1] >> 1) ^ ((i & 1) << 30); } computed = lg; } template <int M> std::vector<mint<M>> root = {0, 1}; template <int M> void compute_roots(int lg) { static int computed = 1; if (lg <= computed) return; root<M>.resize(1 << lg); for (int k = computed; k < lg; k++) { mint<M> z(prime_info<M>::root); for (int i = (1 << (k + 1)); i < prime_info<M>::root_pw; i <<= 1) { z *= z; } for (int i = (1 << (k - 1)); i < (1 << k); i++) { root<M>[i << 1] = root<M>[i]; root<M>[i << 1 | 1] = root<M>[i] * z; } } } template<int M> void ntt(std::vector<mint<M>> &a) { int n = int(a.size()), lg = 32 - __builtin_clz(n) - 1; compute_bit_reverse(lg); compute_roots<M>(lg); int shift = 31 - lg; for (int i = 0; i < n; i++) { if (i < (rev[i] >> shift)) { std::swap(a[i], a[rev[i] >> shift]); } } for (int k = 1; k < n; k <<= 1) { mint<M> wl = prime_info<M>::root; for (int i = 2 * k; i < prime_info<M>::root_pw; i <<= 1) { wl *= wl; } for (int i = 0; i < n; i += 2 * k) { for (int j = 0; j < k; j++) { mint<M> z = root<M>[j + k] * a[i + j + k]; a[i + j + k] = a[i + j] - z; a[i + j] = a[i + j] + z; } } } } template <int M> std::enable_if_t<prime_info<M>::root != 0, std::vector<mint<M>>> convolution(std::vector<mint<M>> a, std::vector<mint<M>> b) { int n = 1; while (n < a.size() + b.size()) { n <<= 1; } a.resize(n); b.resize(n); ntt(a), ntt(b); mint<M> n_inv = mint<M>(n).inv(); for (int i = 0; i < n; i++) { a[i] *= b[i] * n_inv; } reverse(a.begin() + 1, a.end()); ntt(a); return a; } template <int M> mint<M> garner(int a1, int a2, int a3) { constexpr static int M1 = 754974721, M2 = 167772161, M3 = 469762049; const static int R12 = mint<M2>(M1).inv().val; const static int R13 = mint<M3>(M1).inv().val; const static int R23 = mint<M3>(M2).inv().val; int x1 = a1; int x2 = (long long)(a2 - x1) * R12 % M2; if (x2 < 0) x2 += M2; int x3 = ((long long)(a3 - x1) * R13 % M3 - x2) * R23 % M3; if (x3 < 0) x3 += M3; return mint<M>(x1) + mint<M>(x2) * M1 + mint<M>(x3) * M1 * M2; } template <int M> std::enable_if_t<prime_info<M>::root == 0, std::vector<mint<M>>> convolution(std::vector<mint<M>> a, const std::vector<mint<M>> &b) { constexpr static int M1 = 754974721, M2 = 167772161, M3 = 469762049; auto c1 = convolution(vector<mint<M1>>(a.begin(), a.end()), vector<mint<M1>>(b.begin(), b.end())); auto c2 = convolution(vector<mint<M2>>(a.begin(), a.end()), vector<mint<M2>>(b.begin(), b.end())); auto c3 = convolution(vector<mint<M3>>(a.begin(), a.end()), vector<mint<M3>>(b.begin(), b.end())); int n = int(c1.size()); a.resize(n); for (int i = 0; i < n; i++) { a[i] = garner<M>(c1[i].val, c2[i].val, c3[i].val); } return a; } template <int M, typename T> std::enable_if_t<!modular::is_modular<T>::value, std::vector<T>> convolution(const std::vector<T> &a, const std::vector<T> &b) { auto f = convolution(std::vector<mint<M>>(a.begin(), a.end()), std::vector<mint<M>>(b.begin(), b.end())); return vector<T>(f.begin(), f.end()); } template <typename T> void normalize(std::vector<T> &a) { for (int i = int(a.size()) - 1; i >= 0; i--) { if (a[i]) { a.resize(i + 1); return; } } a.clear(); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); using namespace ntt; int n; cin >> n; if (n == 0) { cout << 1 << '\n'; return 0; } vector<vector<int>> t(2 * n); for (int i = 0; i < n; i++) { t[i + n] = {-i, 1}; } for (int i = n - 1; i > 0; i--) { t[i] = convolution<998244353>(t[i << 1], t[i << 1 | 1]); normalize(t[i]); } for (int i = 0; i <= n; i++) { cout << t[1][i] << ' '; } cout << '\n'; return 0; }