#include #include #define fast std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr) #define eb emplace_back #define all(x) (x).begin(), (x).end() using namespace std; using namespace atcoder; using ll = long long; using mint = atcoder::modint998244353; constexpr ll inf = 2e18; constexpr ll mod = 998244353; static void judge(bool c) { std::cout << (c ? "Yes" : "No") << '\n'; } static vector trim(vector& a){ while(!a.empty() && a.back()==mint(0)) a.pop_back(); return a; } vector operator*(const vector& a,const vector& b){ if(a.empty()||b.empty()) return {}; auto c = convolution(a,b); return c; } vector prod(const vector &f,const vector &g){ return f*g; } static vector mul_trunc(const vector& a,const vector& b,int n){ if(a.empty()||b.empty()) return vector(); int need = min(n+1,(int)a.size()+(int)b.size()-1); auto c=convolution(a,b); c.resize(need); return c; } static vector poly_inv(const vector& a,int n){ if(a.empty() || a[0]==mint(0)) throw runtime_error("poly_inv: bad input"); vector r(1, a[0].inv()); int m = 1; vector two_minus_t,as; while(m <= n){ int cur = m<<1; as.assign(min((int)a.size(), cur),mint(0)); for(int i=0;i<(int)as.size();++i) as[i]=a[i]; auto t = mul_trunc(r, as, cur-1); two_minus_t.assign(cur, mint(0)); two_minus_t[0] = mint(2) - (t.size()>0? t[0] : mint(0)); for(int i=1;i div(const vector &f,const vector &g,int n){ if(g.empty()) throw runtime_error("div: g is zero"); if(g[0]==mint(0)) throw runtime_error("div: g[0]==0"); int need = n+1; vector ig = poly_inv(g, n); auto res = mul_trunc(f, ig, n); res.resize(need); return res; } static vector derivative(const vector& a){ if(a.size()<=1) return vector(); vector r(a.size()-1); for(size_t i=1;i integral(const vector& a){ vector r(a.size()+1); r[0]=mint(0); for(size_t i=0;i log(const vector &f,int n){ if(f.empty()||f[0]!=mint(1)) throw runtime_error("log: constant term must be 1"); auto df = derivative(f); auto invf = poly_inv(f, n); auto mul = mul_trunc(df, invf, max(0,n-1)); auto res = ::integral(mul); res.resize(n+1); return res; } vector exp(const vector &f,int n){ if(f.empty()||f[0]!=mint(0)) throw runtime_error("exp: constant term must be 0"); vector g(1,mint(1)); int m=1; while(m<=n){ int cur = m<<1; int need = min(cur, n+1); vector ln = log(g, need-1); vector diff(need); for(int i=0;i composition(const vector &f,const vector &g,int n){ if(g.empty() || g[0]!=mint(0)) throw runtime_error("composition: g[0] must be 0"); int degf = (int)f.size(); vector res(1,mint(0)); for(int i=degf-1;i>=0;--i){ res = mul_trunc(res, g, n); if((int)res.size()>n+1) res.resize(n+1); if((int)res.size() inv(const vector &f,int n){ if(f.empty()) throw runtime_error("inv composition: empty"); if(f[0]!=mint(0)) throw runtime_error("inv composition: constant term must be 0"); if(f.size()<=1 || f[1]==mint(0)) throw runtime_error("inv composition: linear coeff must be nonzero"); vector g(1,mint(0)); int m=1; while(m<=n){ int cur = m<<1; int need = min(cur, n+1); auto fg = composition(f, g, need-1); vector delta(need); for(int i=0;i poly_mod(vector f, vector g){ f = trim(f); g = trim(g); if(g.empty()) throw runtime_error("poly_mod: g empty"); if(f.size() < g.size()) return f; int n = (int)f.size() - 1; int m = (int)g.size() - 1; int qdeg = n - m; vector f_rev = f; reverse(all(f_rev)); vector g_rev = g; reverse(all(g_rev)); int need = qdeg + 1; f_rev.resize(need); g_rev.resize(need); auto inv_g_rev = poly_inv(g_rev, qdeg); auto q_rev = mul_trunc(f_rev, inv_g_rev, qdeg); q_rev.resize(need); vector q = q_rev; reverse(all(q)); q = trim(q); auto qg = prod(q, g); int rem_size = (int)g.size() - 1; if (rem_size < 0) rem_size = 0; vector r(rem_size); for(int i = 0; i < rem_size; i++) { mint fi = (i < (int)f.size() ? f[i] : mint(0)); mint qgi = (i < (int)qg.size() ? qg[i] : mint(0)); r[i] = fi - qgi; } return trim(r); } vector multipoint_eval(const vector &a, const vector &point){ size_t m = point.size(); if(m == 0) return vector(); size_t m2 = ceil2(m); vector> g(m2 + m2, vector(1, mint(1))); for(size_t i=0;i{-xi, mint(1)}; } for(size_t i = m2; i-- > 1; ){ g[i] = prod(g[i<<1], g[i<<1|1]); } g[1] = poly_mod(a, g[1]); for(size_t i = 2; i < m2 + m; ++i){ g[i] = poly_mod(g[i>>1], g[i]); } vector ys(m); for(size_t i=0;i fact; std::vector inv_fact; long long power(long long base, long long exp) { long long res = 1; base %= mod; while (exp > 0) { if (exp % 2 == 1) res = (res * base) % mod; base = (base * base) % mod; exp /= 2; } return res; } public: BinomialCoefficient(int n_max, long long m) : mod(m) { fact.resize(n_max + 1); inv_fact.resize(n_max + 1); fact[0] = 1; inv_fact[0] = 1; for (int i = 1; i <= n_max; ++i) { fact[i] = (fact[i - 1] * i) % mod; } inv_fact[n_max] = power(fact[n_max], mod - 2); for (int i = n_max; i > 0; --i) { inv_fact[i - 1] = (inv_fact[i] * i) % mod; } } long long com(int n, int r) { if (r < 0 || n < r) { return 0; } if (static_cast(n) >= fact.size()) { return -1; } long long result = fact[n]; result = (result * inv_fact[r]) % mod; result = (result * inv_fact[n - r]) % mod; return result; } }; vector power(const vector &f, long long e, int n) { if (f.empty()) return vector(n + 1, 0); if (e == 0) { vector res(n + 1, 0); res[0] = 1; return res; } int shift = 0; while (shift < (int)f.size() && f[shift] == mint(0)) shift++; if (shift == (int)f.size()) return vector(n + 1, 0); if (e > 0 && shift > (n / e)) return vector(n + 1, 0); vector g; g.reserve(f.size() - shift); for (int i = shift; i < (int)f.size(); ++i) g.push_back(f[i]); mint c = g[0]; mint inv_c = c.inv(); for (auto& x : g) x *= inv_c; auto logg = log(g, n); for (auto& x : logg) x *= mint(e); auto expg = exp(logg, n); mint c_pow = c.pow(e); for (auto& x : expg) x *= c_pow; vector res(n + 1, 0); int total_shift = (int)(e * shift); for (int i = 0; i < (int)expg.size(); ++i) { if (total_shift + i <= n) res[total_shift + i] = expg[i]; } return res; } vector get_power_sums(const vector& arr, int k_max) { int n = arr.size(); if (n == 0) { return vector(k_max + 1, 0); } function(int, int)> dc_prod = [&](int l, int r) -> vector { if (l == r) { return {1, -mint(arr[l])}; } int mid = (l + r) / 2; auto left = dc_prod(l, mid); auto right = dc_prod(mid + 1, r); return prod(left, right); }; vector Q = dc_prod(0, n - 1); vector dQ = derivative(Q); vector invQ = poly_inv(Q, k_max); vector R = mul_trunc(dQ, invQ, k_max); R.resize(k_max + 1, 0); vector P_sum(k_max + 1); P_sum[0] = n; for (int i = 1; i <= k_max; ++i) { P_sum[i] = -R[i - 1]; } return P_sum; } mint bostan_mori(vector f, vector g, ll n) { f = trim(f); g = trim(g); if (g.empty() || g[0] == mint(0)) throw runtime_error("bostan_mori: bad denominator"); while (n > 0) { auto g_neg = g; for (size_t i = 1; i < g_neg.size(); i += 2) g_neg[i] = -g_neg[i]; auto g_sq = convolution(g, g_neg); auto f_gneg = convolution(f, g_neg); size_t g_sz = (g_sq.size() + 1) >> 1; g.resize(g_sz); for (size_t i = 0; i < g_sz; ++i) { g[i] = (2 * i < g_sq.size() ? g_sq[2 * i] : mint(0)); } size_t f_sz = (f_gneg.size() + (n & 1) + 1) >> 1; f.resize(f_sz); int parity = (n & 1); for (size_t i = 0; i < f_sz; ++i) { size_t idx = 2 * i + parity; f[i] = (idx < f_gneg.size() ? f_gneg[idx] : mint(0)); } n >>= 1; } return f.empty() ? mint(0) : f[0] * g[0].inv(); } namespace fps_internal { vector> precompute_powers(const vector& g, int n, int k) { vector> powers; powers.reserve(32); powers.push_back(g); int deg = 1; while (deg < k) { auto next_g = mul_trunc(powers.back(), powers.back(), n); powers.push_back(next_g); deg <<= 1; } return powers; } vector compose_dc(const vector& f, int l, int r, const vector>& g_powers, int level, int n) { if (l + 1 == r) { if (l < (int)f.size()) return {f[l]}; return {mint(0)}; } int mid = (l + r) >> 1; auto h_left = compose_dc(f, l, mid, g_powers, level - 1, n); auto h_right = compose_dc(f, mid, r, g_powers, level - 1, n); auto rhs = mul_trunc(h_right, g_powers[level - 1], n); if (h_left.size() < rhs.size()) h_left.resize(rhs.size(), mint(0)); for (size_t i = 0; i < rhs.size(); ++i) h_left[i] += rhs[i]; return h_left; } } vector compose(const vector& f, const vector& g, int n) { if (f.empty()) return {}; if (g.empty()) return {f[0]}; int deg_f = (int)f.size() - 1; if (deg_f == 0) return {f[0]}; int k = 1; int level = 0; while (k <= deg_f) { k <<= 1; level++; } auto g_powers = fps_internal::precompute_powers(g, n, k); return fps_internal::compose_dc(f, 0, k, g_powers, level, n); } vector inverse(const vector& f, int n) { if (f.empty() || f[0] != mint(0)) throw runtime_error("inverse: constant term must be 0"); if (f.size() <= 1 || f[1] == mint(0)) throw runtime_error("inverse: linear coeff must be nonzero"); vector g = {mint(0)}; g = {mint(0), f[1].inv()}; int m = 1; while (m <= n) { int cur = m << 1; int need = min(cur, n + 1); auto fg = compose(f, g, need - 1); if (fg.size() > 1) fg[1] -= mint(1); auto f_prime = derivative(f); auto fpg = compose(f_prime, g, need - 1); auto inv_fpg = poly_inv(fpg, need - 1); auto correction = mul_trunc(fg, inv_fpg, need - 1); g.resize(need); for (int i = 0; i < need; ++i) { if (i < (int)correction.size()) g[i] -= correction[i]; } m = cur; } g.resize(n + 1); return g; } vector power_projection(const vector& f, const vector& g) { using fps = vector; int n = (int)f.size() - 1; if (n < 0) return {}; auto pack = [](const vector& V, int n_x, int width) -> fps { int size = n_x * width; if (V.empty()) return {}; int real_size = (int)V.size() * width + (int)V.back().size(); fps res(real_size, mint(0)); for (int i = 0; i < (int)V.size(); ++i) { for (int j = 0; j < (int)V[i].size(); ++j) { res[i * width + j] = V[i][j]; } } return res; }; auto unpack = [](const fps& flat, int n_x, int width, int deg_y_limit) -> vector { vector res(n_x); for (int i = 0; i < n_x; ++i) { int start = i * width; int end = min((int)flat.size(), start + width); if (start >= (int)flat.size()) continue; int len = min(end - start, deg_y_limit + 1); res[i].resize(len); for (int j = 0; j < len; ++j) { res[i][j] = flat[start + j]; } } return res; }; int k = 1; vector P(n + 1, fps(1)); vector Q(n + 1, fps(2)); for (int i = 0; i <= n; ++i) P[i][0] = (i < (int)g.size() ? g[i] : mint(0)); Q[0][0] = 1; for (int i = 1; i <= n; ++i) { if (i < (int)f.size()) { Q[i] = {mint(0), -f[i]}; } else { Q[i] = {mint(0)}; } } int cur_n = n; while (cur_n > 0) { auto R = Q; for (int i = 1; i <= cur_n; i += 2) { for (auto& val : R[i]) val = -val; } int width = 1; while(width < 2 * k + 2) width <<= 1; auto flat_P = pack(P, cur_n + 1, width); auto flat_Q = pack(Q, cur_n + 1, width); auto flat_R = pack(R, cur_n + 1, width); auto flat_S = convolution(flat_P, flat_R); auto flat_T = convolution(flat_Q, flat_R); int next_n = cur_n / 2; int next_k = k * 2; int parity = cur_n % 2; vector next_P(next_n + 1); for(int i = 0; i <= next_n; ++i) { int target_idx = 2 * i + parity; int start = target_idx * width; if(start >= (int)flat_S.size()) continue; int len = min((int)flat_S.size() - start, width); len = min(len, next_k + 1); next_P[i].resize(len); for(int j=0; j next_Q(next_n + 1); for(int i = 0; i <= next_n; ++i) { int target_idx = 2 * i; int start = target_idx * width; if(start >= (int)flat_T.size()) continue; int len = min((int)flat_T.size() - start, width); len = min(len, next_k + 1); next_Q[i].resize(len); for(int j=0; j> n >> a >> b; ll ans = a; for(int i = 0; i < n; i++){ cout << ans << endl; ans = (ans * b); } }