/// GPT6-Astra #include #include #include using namespace std; using mint = atcoder::modint998244353; using Poly = vector; struct Block { Poly p; Poly q; }; // 半開区間 [l, r) に対応する P, Q を構築する。 Block build(int l, int r, const Poly& t) { if (r - l == 1) { return { Poly{t[l]}, Poly{mint(1), -mint(l)} }; } int m = (l + r) / 2; Block left = build(l, m, t); Block right = build(m, r, t); // P = P_left * Q_right + x^(m-l) * P_right Poly p = atcoder::convolution(left.p, right.q); int shift = m - l; for (int i = 0; i < static_cast(right.p.size()); ++i) { p[shift + i] += right.p[i]; } // Q = Q_left * Q_right Poly q = atcoder::convolution(left.q, right.q); return {move(p), move(q)}; } // f^(-1) mod x^n を求める。f[0] != 0 が必要。 Poly inverse_series(const Poly& f, int n) { Poly g{f[0].inv()}; while (static_cast(g.size()) < n) { int len = min(n, 2 * static_cast(g.size())); int take = min(len, static_cast(f.size())); Poly h(f.begin(), f.begin() + take); h = atcoder::convolution(h, g); h.resize(len); // h = 2 - f * g for (mint& value : h) { value = -value; } h[0] += 2; // g <- g * (2 - f * g) g = atcoder::convolution(g, h); g.resize(len); } return g; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long N, M; int K; cin >> N >> M >> K; int L = static_cast( min({N, M, static_cast(K)}) ); Poly fact(L + 1), inv_fact(L + 1); fact[0] = 1; for (int i = 1; i <= L; ++i) { fact[i] = fact[i - 1] * i; } inv_fact[L] = fact[L].inv(); for (int i = L; i >= 1; --i) { inv_fact[i - 1] = inv_fact[i] * i; } // a[i] = (-1)^i * (M-i)^N / i! // b[i] = 1 / i! Poly a(L + 1); Poly b = inv_fact; for (int i = 0; i <= L; ++i) { a[i] = mint(M - i).pow(N) * inv_fact[i]; if (i & 1) { a[i] = -a[i]; } } Poly c = atcoder::convolution(a, b); // t[j] = (M)_j * j! * c[j] Poly t(L + 1); mint falling = 1; for (int j = 0; j <= L; ++j) { if (j > 0) { falling *= mint(M - j + 1); } t[j] = falling * fact[j] * c[j]; } Block all = build(1, L + 1, t); Poly inv_q = inverse_series(all.q, K); Poly answer = atcoder::convolution(all.p, inv_q); answer.resize(K); for (int k = 0; k < K; ++k) { cout << answer[k].val() << '\n'; } }