#line 1 "main.cpp" #include #line 2 "/home/user/Library/utils/macros.hpp" #define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i)) #define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i)) #define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i)) #define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i)) #define ALL(x) std::begin(x), std::end(x) #line 4 "/home/user/Library/modulus/modpow.hpp" inline int32_t modpow(uint_fast64_t x, uint64_t k, int32_t MOD) { assert (/* 0 <= x and */ x < (uint_fast64_t)MOD); uint_fast64_t y = 1; for (; k; k >>= 1) { if (k & 1) (y *= x) %= MOD; (x *= x) %= MOD; } assert (/* 0 <= y and */ y < (uint_fast64_t)MOD); return y; } #line 5 "/home/user/Library/modulus/modinv.hpp" inline int32_t modinv_nocheck(int32_t value, int32_t MOD) { assert (0 <= value and value < MOD); if (value == 0) return -1; int64_t a = value, b = MOD; int64_t x = 0, y = 1; for (int64_t u = 1, v = 0; a; ) { int64_t q = b / a; x -= q * u; std::swap(x, u); y -= q * v; std::swap(y, v); b -= q * a; std::swap(b, a); } if (not (value * x + MOD * y == b and b == 1)) return -1; if (x < 0) x += MOD; assert (0 <= x and x < MOD); return x; } inline int32_t modinv(int32_t x, int32_t MOD) { int32_t y = modinv_nocheck(x, MOD); assert (y != -1); return y; } #line 6 "/home/user/Library/modulus/mint.hpp" /** * @brief quotient ring / 剰余環 $\mathbb{Z}/n\mathbb{Z}$ */ template struct mint { int32_t value; mint() : value() {} mint(int64_t value_) : value(value_ < 0 ? value_ % MOD + MOD : value_ >= MOD ? value_ % MOD : value_) {} mint(int32_t value_, std::nullptr_t) : value(value_) {} explicit operator bool() const { return value; } inline mint operator + (mint other) const { return mint(*this) += other; } inline mint operator - (mint other) const { return mint(*this) -= other; } inline mint operator * (mint other) const { return mint(*this) *= other; } inline mint & operator += (mint other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; } inline mint & operator -= (mint other) { this->value -= other.value; if (this->value < 0) this->value += MOD; return *this; } inline mint & operator *= (mint other) { this->value = (uint_fast64_t)this->value * other.value % MOD; return *this; } inline mint operator - () const { return mint(this->value ? MOD - this->value : 0, nullptr); } inline bool operator == (mint other) const { return value == other.value; } inline bool operator != (mint other) const { return value != other.value; } inline mint pow(uint64_t k) const { return mint(modpow(value, k, MOD), nullptr); } inline mint inv() const { return mint(modinv(value, MOD), nullptr); } inline mint operator / (mint other) const { return *this * other.inv(); } inline mint & operator /= (mint other) { return *this *= other.inv(); } }; template mint operator + (int64_t value, mint n) { return mint(value) + n; } template mint operator - (int64_t value, mint n) { return mint(value) - n; } template mint operator * (int64_t value, mint n) { return mint(value) * n; } template mint operator / (int64_t value, mint n) { return mint(value) / n; } template std::istream & operator >> (std::istream & in, mint & n) { int64_t value; in >> value; n = value; return in; } template std::ostream & operator << (std::ostream & out, mint n) { return out << n.value; } #line 9 "/home/user/Library/modulus/number_theoretic_transformation.hpp" template struct proth_prime {}; template <> struct proth_prime<1224736769> { static constexpr int a = 73, b = 24, g = 3; }; template <> struct proth_prime<1053818881> { static constexpr int a = 3 * 5 * 67, b = 20, g = 7; }; template <> struct proth_prime<1051721729> { static constexpr int a = 17 * 59, b = 20, g = 6; }; template <> struct proth_prime<1045430273> { static constexpr int a = 997, b = 20, g = 3; }; template <> struct proth_prime<1012924417> { static constexpr int a = 3 * 7 * 23, b = 21, g = 5; }; template <> struct proth_prime<1007681537> { static constexpr int a = 31 * 31, b = 20, g = 3; }; template <> struct proth_prime<1004535809> { static constexpr int a = 479, b = 21, g = 3; }; template <> struct proth_prime< 998244353> { static constexpr int a = 7 * 17, b = 23, g = 3; }; template <> struct proth_prime< 985661441> { static constexpr int a = 5 * 47, b = 22, g = 3; }; template <> struct proth_prime< 976224257> { static constexpr int a = 7 * 7 * 19, b = 20, g = 3; }; template <> struct proth_prime< 975175681> { static constexpr int a = 3 * 5 * 31, b = 21, g = 17; }; template <> struct proth_prime< 962592769> { static constexpr int a = 3 * 3 * 3 * 17, b = 21, g = 7; }; template <> struct proth_prime< 950009857> { static constexpr int a = 4 * 151, b = 21, g = 7; }; template <> struct proth_prime< 943718401> { static constexpr int a = 3 * 3 * 5 * 5, b = 22, g = 7; }; template <> struct proth_prime< 935329793> { static constexpr int a = 223, b = 22, g = 3; }; template <> struct proth_prime< 924844033> { static constexpr int a = 3 * 3 * 7 * 7, b = 21, g = 5; }; template <> struct proth_prime< 469762049> { static constexpr int a = 7, b = 26, g = 3; }; template <> struct proth_prime< 167772161> { static constexpr int a = 5, b = 25, g = 3; }; struct is_proth_prime_impl { template static auto check(T *) -> decltype(proth_prime::g, std::true_type()); template static auto check(...) -> std::false_type; }; template struct is_proth_prime : decltype(is_proth_prime_impl::check(nullptr)) { }; /** * @brief Number Theoretic Transformation (NTT) for Proth primes * @note O(N log N) * @note radix-2, decimation-in-frequency, Cooley-Tukey * @note cache std::polar (~ 2x faster) */ template void ntt_inplace(std::vector > & a, bool inverse) { const int n = a.size(); const int log2_n = __builtin_ctz(n); assert (n == 1 << log2_n); assert (log2_n <= proth_prime::b); // prepare rotors std::vector > ep, iep; while ((int)ep.size() <= log2_n) { ep.push_back(mint(proth_prime::g).pow(mint(-1).value / (1 << ep.size()))); iep.push_back(ep.back().inv()); } // divide and conquer std::vector > b(n); REP3 (i, 1, log2_n + 1) { int w = 1 << (log2_n - i); mint base = (inverse ? iep : ep)[i]; mint now = 1; for (int y = 0; y < n / 2; y += w) { REP (x, w) { auto l = a[y << 1 | x]; auto r = now * a[y << 1 | x | w]; b[y | x] = l + r; b[y | x | n >> 1] = l - r; } now *= base; } std::swap(a, b); } // div by n if inverse if (inverse) { auto n_inv = mint(n).inv(); REP (i, n) { a[i] *= n_inv; } } } /** * @brief multiprecation on $\mathbb{F}_p[x]$ for Proth primes * @note O(N log N) * @note (f \ast g)(i) = \sum_{0 \le j \lt i + 1} f(j) g(i - j) */ template typename std::enable_if::value, std::vector > >::type ntt_convolution(const std::vector > & a_, const std::vector > & b_) { if (a_.size() <= 32 or b_.size() <= 32) { std::vector > c(a_.size() + b_.size() - 1); REP (i, a_.size()) REP (j, b_.size()) c[i + j] += a_[i] * b_[j]; return c; } int m = a_.size() + b_.size() - 1; int n = (m == 1 ? 1 : 1 << (32 - __builtin_clz(m - 1))); auto a = a_; auto b = b_; a.resize(n); b.resize(n); ntt_inplace(a, false); ntt_inplace(b, false); REP (i, n) { a[i] *= b[i]; } ntt_inplace(a, true); a.resize(m); return a; } #line 11 "/home/user/Library/modulus/formal_power_series.hpp" /** * @brief formal power series / 形式的羃級数環 $\mathbb{Z}/n\mathbb{Z}\lbrack\lbrack x\rbrack\rbrack$ */ template struct formal_power_series { std::vector a; inline size_t size() const { return a.size(); } inline bool empty() const { return a.empty(); } inline T at(int i) const { return (i < size() ? a[i] : T(0)); } inline const std::vector & data() const { return a; } formal_power_series() = default; formal_power_series(const std::vector & a_) : a(a_) { shrink(); } formal_power_series(const std::initializer_list & init) : a(init) { shrink(); } template formal_power_series(Iterator first, Iterator last) : a(first, last) { shrink(); } void shrink() { while (not a.empty() and a.back().value == 0) a.pop_back(); } inline formal_power_series operator + (const formal_power_series & other) const { return formal_power_series(a) += other; } inline formal_power_series operator - (const formal_power_series & other) const { return formal_power_series(a) -= other; } inline formal_power_series & operator += (const formal_power_series & other) { if (a.size() < other.a.size()) a.resize(other.a.size(), T(0)); REP (i, other.a.size()) a[i] += other.a[i]; return *this; } inline formal_power_series & operator -= (const formal_power_series & other) { if (a.size() < other.a.size()) a.resize(other.a.size(), T(0)); REP (i, other.a.size()) a[i] -= other.a[i]; return *this; } inline formal_power_series operator * (const formal_power_series & other) const { return formal_power_series(ntt_convolution(a, other.a)); } inline formal_power_series operator * (T b) { return formal_power_series(a) *= b; } inline formal_power_series & operator *= (T b) { REP (i, size()) a[i] *= b; return *this; } inline formal_power_series operator / (T b) { return formal_power_series(a) /= b; } inline formal_power_series & operator /= (T b) { REP (i, size()) a[i] /= b; return *this; } inline formal_power_series integral() const { std::vector b(size() + 1); REP (i, size()) { b[i + 1] = a[i] / (i + 1); } return b; } inline formal_power_series differential() const { if (empty()) return *this; std::vector b(size() - 1); REP (i, size() - 1) { b[i] = a[i + 1] * (i + 1); } return b; } inline formal_power_series modulo_x_to(int k) const { return formal_power_series(a.begin(), a.begin() + std::min(size(), k)); } formal_power_series inv(int n) const { assert (at(0) != 0); formal_power_series res { at(0).inv() }; for (int i = 1; i < n; i *= 2) { res = (res * T(2) - res * res * modulo_x_to(2 * i)).modulo_x_to(2 * i); } return res.modulo_x_to(n); } formal_power_series exp(int n) const { formal_power_series f{ 1 }; formal_power_series g{ 1 }; for (int i = 1; i < n; i *= 2) { g = (g * 2 - f * g * g).modulo_x_to(i); formal_power_series q = differential().modulo_x_to(i - 1); formal_power_series w = (q + g * (f.differential() - f * q)).modulo_x_to(2 * i - 1); f = (f + f * (*this - w.integral()).modulo_x_to(2 * i)).modulo_x_to(2 * i); } return f.modulo_x_to(n); } inline formal_power_series log(int n) const { assert (at(0) != 0); if (at(0) != 1) return (formal_power_series(a) / at(0)).log(n) * at(0); if (size() == 1) return formal_power_series(); return (this->differential() * this->inv(n - 1)).modulo_x_to(n - 1).integral(); } inline formal_power_series pow(int k, int n) const { return (this->log(n) * k).exp(n); } }; template inline formal_power_series operator - (const formal_power_series & f) { return formal_power_series(f) *= -1; } template std::ostream & operator << (std::ostream & out, const formal_power_series & f) { bool is_zero = true; REP (i, f.size()) { if (f.at(i)) { if (not is_zero) out << '+'; out << f.at(i); if (i) out << "x^" << i; is_zero = false; } } if (is_zero) { out << "0"; } return out; } #line 4 "main.cpp" using namespace std; constexpr int MOD = 998244353; vector > solve(int n, int m, const vector > & a) { auto go = [&](auto && go, int l, int r) { if (r - l == 0) return formal_power_series >{ 1 }; if (r - l == 1) return formal_power_series >{ 1, - a[l] }; int m_ = (l + r) / 2; return (go(go, l, m_) * go(go, m_, r)).modulo_x_to(m + 2); }; vector > ans = (- go(go, 0, n).log(m + 2)).data(); ans.resize(m + 1); REP3 (k, 1, m + 1) { ans[k] *= k; } return ans; } int main() { int n, m; scanf("%d%d", &n, &m); vector > a(n); REP (i, n) { scanf("%d", &a[i].value); } auto ans = solve(n, m, a); assert (ans[0] == 0); REP (i, m) { printf("%d%c", ans[i + 1].value, i + 1 < m ? ' ' : '\n'); } return 0; }