#pragma GCC optimize("O3") #pragma GCC target("avx,avx2,bmi,bmi2,lzcnt,popcnt") #include #include #include #include // Represents Polynomial on field F template (*conv)(const std::vector &, const std::vector &)> class Polynomial { std::vector p; // Calculate small inverses static F inverse(int v) { static std::vector inv = {F(0)}; for (int i = inv.size(); i <= v; i++) inv.push_back(1 / F(i)); return inv[v]; } public: // Initializes empty polynomial with degree -1 Polynomial() : p() {} // Initializes polynomial using vector. // P is represented as v[i]x^i Polynomial(std::vector v) : p(v) {} // Get degree of Polynomial, zero polynomial has degree -1. int deg() const { return (int)p.size() - 1; } // Resize polynomial to certain degree void set_degree(int deg) { assert(deg >= -1); p.resize(deg + 1); } F &operator[](int idx) { return p[idx]; } const F &operator[](int idx) const { return p[idx]; } // Adds two polynomial, degree is maximum of two operands. Polynomial operator+(const Polynomial &rhs) const { Polynomial ret = *this; if (ret.deg() < rhs.deg()) ret.set_degree(rhs.deg()); for (int i = 0; i <= rhs.deg(); i++) ret[i] += rhs[i]; return ret; } Polynomial &operator+=(const Polynomial &rhs) { if (deg() < rhs.deg()) set_degree(rhs.deg()); for (int i = 0; i <= rhs.deg(); i++) p[i] += rhs[i]; return *this; } // Subtracts two polynomial, degree is maximum of two operands. Polynomial operator-(const Polynomial &rhs) const { Polynomial ret = *this; if (ret.deg() < rhs.deg()) ret.set_degree(rhs.deg()); for (int i = 0; i <= rhs.deg(); i++) ret[i] -= rhs[i]; return ret; } Polynomial &operator-=(const Polynomial &rhs) { if (deg() < rhs.deg()) set_degree(rhs.deg()); for (int i = 0; i <= rhs.deg(); i++) p[i] -= rhs[i]; return *this; } Polynomial operator-() const { Polynomial ret = *this; for (int i = 0; i <= ret.deg(); i++) ret[i] = -ret[i]; return ret; } Polynomial operator>>(int K) const { return floordiv_xK(K); } Polynomial operator<<(int K) const { return mult_xK(K); } // Multiplies two polynomial, degree is sum of two operands. // With exception that deg(f) = -1 or deg(g) = -1 will give deg(f*g) = -1 Polynomial operator*(const Polynomial &rhs) const { return Polynomial(conv(p, rhs.p)); } Polynomial &operator*=(const Polynomial &rhs) { p = std::move(conv(p, rhs.p)); return *this; } // Get inverse of a polynomial, up to specified degree // By default, degree is deg(), P[0] must not be 0. Polynomial inv(int degree = -1) const { if (degree == -1) degree = deg(); assert(deg() >= 0 && degree >= 0 && p[0] != F(0)); Polynomial a({F(1) / p[0]}); for (int l = 1; l <= degree; l *= 2) { Polynomial p0 = std::vector(p.begin(), p.begin() + std::min(l, (int)p.size())); Polynomial p1; if ((int)p.size() >= l) p1 = std::vector(p.begin() + l, p.begin() + std::min(2 * l, (int)p.size())); Polynomial ap0 = a * p0; Polynomial c = std::vector(ap0.p.begin() + l, ap0.p.end()); Polynomial b = a * p1; b.set_degree(l - 1); b += c; b *= a; b.set_degree(l - 1); a.p.resize(2 * l); for (int i = l; i < 2 * l; i++) a.p[i] -= b[i - l]; } a.set_degree(degree); return a; } // Returns int f(x). // Returns polynomial with f(0) = 0, degree increases by 1 Polynomial integ() const { Polynomial ret; ret.set_degree(p.size()); for (int i = 1; i <= ret.deg(); i++) ret[i] = p[i - 1] * inverse(i); return ret; } // Returns f(x)/x^K, truncated. Polynomial floordiv_xK(int K) const { if (deg() < K) return {}; return std::vector(p.begin() + K, p.end()); } // Returns f(x)*x^K Polynomial mult_xK(int K) const { std::vector V(p.size() + K); std::copy(p.begin(), p.end(), V.begin() + K); return V; } // Returns df/dx // degree decreases by 1 Polynomial diff() const { if (deg() <= 0) return Polynomial(); Polynomial ret; ret.set_degree(deg() - 1); for (int i = 0; i <= ret.deg(); i++) ret[i] = (i + 1) * p[i + 1]; return ret; } // Returns ln(f(x)) where f(0) = 1, up to degree // By default, degree is deg(), P[0] must be 1. Polynomial ln(int degree = -1) const { if (degree == -1) degree = deg(); if (degree == 0) return Polynomial({F(0)}); assert(degree >= 0 && deg() >= 0 && p[0] == 1); Polynomial integrand = diff() * inv(degree - 1); integrand.set_degree(degree - 1); return integrand.integ(); } // Returns exp(f(x)) where f(0) = 0, up to degree // By default, degree is deg(), P[0] must not be 0. Polynomial exp(int degree = -1) const { if (degree == -1) degree = deg(); if (degree == 0) return Polynomial({F(1)}); assert(degree >= 0 && deg() >= 0 && p[0] == F(0)); Polynomial h({F(1)}); for (int l = 1; l <= degree; l *= 2) { Polynomial m = std::vector(p.begin(), p.begin() + std::min(2 * l, (int)p.size())); m -= h.ln(2 * l); m[0] += F(1); h *= m; h.set_degree(2 * l); } h.set_degree(degree); return h; } // Returns f(x+a) Polynomial taylor_shift(F a) const { if (deg() <= 0) return *this; std::vector fact(deg() + 1); fact[0] = F(1); for (int i = 1; i <= deg(); i++) fact[i] = F(i) * fact[i - 1]; std::vector f(deg() + 1), g(deg() + 1); F cur = F(1); for (int i = 0; i <= deg(); i++) { f[i] = p[i] * fact[i]; cur *= F(i + 1); } cur = F(1); for (int i = 0; i <= deg(); i++) { g[i] = cur; cur *= a * F(i + 1); } reverse(g.begin(), g.end()); std::vector res = conv(f, g); res.erase(res.begin(), res.begin() + deg()); for (int i = 0; i <= deg(); i++) res[i] /= fact[i]; return Polynomial(res); } }; using Mint = atcoder::modint998244353; using Poly = Polynomial; #include using namespace std; int main() { int N, K; scanf("%d%d", &N, &K); vector ev(N + 1); int f = -1; for (int i = 1; i <= N; i++) { int t; cin >> t; ev[i] = t; if (t != 0 && f == -1) f = i; } Poly E = ev; auto P = (Poly({1}) - E).inv() - Poly({1}); if (K > 0) { Poly E_ = (E.diff() >> (f - 1)).inv() * E; for (int i = 0; i < K; i++) P = (P.diff() >> (f - 1)) * E_; } else if (K < 0) { Poly E_ = E.diff() * (E >> f).inv(); for (int i = 0; i < -K; i++) P = ((P * E_) >> f).integ(); } for (int i = 1; i <= N; i++) cout << P[i].val() << " "; cout << endl; }