#1176237 (C++23(gcc16)) No.3620 Compositional Power with Schröder Coordinate 2

• 問題: No.3620 Compositional Power with Schröder Coordinate 2
• ユーザー: noimi
• 提出日時: 2026-08-11 15:34:45
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 1,743 ms / 10,000 ms
• コード長: 8,685 bytes
• コンパイル時間: 3,197 ms
• コンパイル使用メモリ: 364,400 KB
• 実行使用メモリ: 29,772 KB
• 最終ジャッジ日時: 2026-08-11 15:35:00
• 合計ジャッジ時間: 14,318 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 2
other	AC * 7

ソースコード

/*
AI (ChatGPT) was used to assist in writing this code.

Details of AI usage:
- I provided the derivation
      [x^(n-1)] f^{<k>}(x)
        = sum_{t=1}^{n-1} d_t (a_1^t)^k,
  where
      d_t = c_t * t/(n-1) * [x^(n-1-t)] phi(x)^(n-1),
      phi(x) = x / h(x).
- I asked ChatGPT to write a full self-contained implementation.
- ChatGPT implemented:
    * NTT convolution modulo 998244353
    * FPS inverse / derivative / integral / log / exp / integer power
    * construction of phi(x)^(n-1)
    * geometric-point evaluation using one convolution
- No external library is required.

Assumed input format for Problem 2:
    n m
    a_0 a_1 ... a_{n-1}
    b_0 b_1 ... b_{n-1}
    c_0 c_1 ... c_{n-1}

Output:
    [x^(n-1)] f^{<k>}(x) for k = 0,1,...,m-1

Note:
- Since m values are output, m must be small enough for O(m) output itself.
*/

#include <bits/stdc++.h>
#include <cassert>
using namespace std;

static const int MOD = 998244353;
static const int G = 3;

struct Mint {
    int v;
    Mint(long long x = 0) {
        x %= MOD;
        if (x < 0) x += MOD;
        v = (int)x;
    }
    Mint& operator+=(const Mint& o) {
        v += o.v;
        if (v >= MOD) v -= MOD;
        return *this;
    }
    Mint& operator-=(const Mint& o) {
        v -= o.v;
        if (v < 0) v += MOD;
        return *this;
    }
    Mint& operator*=(const Mint& o) {
        v = (int)((long long)v * o.v % MOD);
        return *this;
    }
    Mint& operator/=(const Mint& o) {
        return *this *= o.inv();
    }
    friend Mint operator+(Mint a, const Mint& b) { return a += b; }
    friend Mint operator-(Mint a, const Mint& b) { return a -= b; }
    friend Mint operator*(Mint a, const Mint& b) { return a *= b; }
    friend Mint operator/(Mint a, const Mint& b) { return a /= b; }
    Mint operator-() const { return Mint(v ? MOD - v : 0); }

    Mint pow(long long e) const {
        Mint a = *this, r = 1;
        while (e > 0) {
            if (e & 1) r *= a;
            a *= a;
            e >>= 1;
        }
        return r;
    }
    Mint inv() const {
        assert(v != 0);
        return pow(MOD - 2);
    }
};

using Poly = vector<Mint>;

void ntt(Poly& a, bool invert) {
    int n = (int)a.size();

    for (int i = 1, j = 0; i < n; ++i) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        Mint wlen = Mint(G).pow((MOD - 1) / len);
        if (invert) wlen = wlen.inv();

        for (int i = 0; i < n; i += len) {
            Mint w = 1;
            int half = len >> 1;

            for (int j = 0; j < half; ++j) {
                Mint u = a[i + j];
                Mint v = a[i + j + half] * w;

                a[i + j] = u + v;
                a[i + j + half] = u - v;

                w *= wlen;
            }
        }
    }

    if (invert) {
        Mint inv_n = Mint(n).inv();
        for (auto& x : a) x *= inv_n;
    }
}

Poly convolution(const Poly& a, const Poly& b) {
    if (a.empty() || b.empty()) return {};

    if (min(a.size(), b.size()) <= 32) {
        Poly c(a.size() + b.size() - 1);
        for (int i = 0; i < (int)a.size(); ++i) {
            for (int j = 0; j < (int)b.size(); ++j) {
                c[i + j] += a[i] * b[j];
            }
        }
        return c;
    }

    int need = (int)a.size() + (int)b.size() - 1;
    int z = 1;
    while (z < need) z <<= 1;

    Poly A(z), B(z);
    copy(a.begin(), a.end(), A.begin());
    copy(b.begin(), b.end(), B.begin());

    ntt(A, false);
    ntt(B, false);

    for (int i = 0; i < z; ++i) A[i] *= B[i];

    ntt(A, true);
    A.resize(need);
    return A;
}

Poly cut(const Poly& a, int n) {
    Poly r(min(n, (int)a.size()));
    copy(a.begin(), a.begin() + r.size(), r.begin());
    r.resize(n);
    return r;
}

Poly fps_inv(const Poly& f, int n) {
    assert(!f.empty() && f[0].v != 0);

    Poly g(1, f[0].inv());

    for (int m = 1; m < n; m <<= 1) {
        int sz = min(2 * m, n);

        Poly fcut(sz);
        for (int i = 0; i < sz && i < (int)f.size(); ++i)
            fcut[i] = f[i];

        Poly fg = convolution(fcut, g);
        fg.resize(sz);

        for (int i = 0; i < sz; ++i) fg[i] = -fg[i];
        fg[0] += Mint(2);

        g = convolution(g, fg);
        g.resize(sz);
    }

    g.resize(n);
    return g;
}

Poly derivative(const Poly& f) {
    if (f.size() <= 1) return {};
    Poly g(f.size() - 1);
    for (int i = 1; i < (int)f.size(); ++i)
        g[i - 1] = f[i] * Mint(i);
    return g;
}

Poly fps_integral(const Poly& f) {
    Poly g(f.size() + 1);
    static vector<Mint> invs{Mint(0), Mint(1)};

    int need = (int)f.size();
    if ((int)invs.size() <= need) {
        int old = invs.size();
        invs.resize(need + 1);
        for (int i = max(2, old); i <= need; ++i) {
            invs[i] = Mint(MOD - MOD / i) * invs[MOD % i];
        }
    }

    for (int i = 0; i < (int)f.size(); ++i)
        g[i + 1] = f[i] * invs[i + 1];

    return g;
}

Poly fps_log(const Poly& f, int n) {
    assert(!f.empty() && f[0].v == 1);

    Poly df = derivative(f);
    Poly invf = fps_inv(f, n);

    Poly q = convolution(df, invf);
    if ((int)q.size() > n - 1) q.resize(n - 1);

    Poly r = fps_integral(q);
    r.resize(n);
    return r;
}

Poly fps_exp(const Poly& f, int n) {
    assert(f.empty() || f[0].v == 0);

    Poly g(1, Mint(1));

    for (int m = 1; m < n; m <<= 1) {
        int sz = min(2 * m, n);

        Poly gg = g;
        gg.resize(sz);

        Poly lg = fps_log(gg, sz);

        Poly q(sz);
        for (int i = 0; i < sz; ++i) {
            Mint fi = (i < (int)f.size() ? f[i] : Mint(0));
            q[i] = fi - lg[i];
        }
        q[0] += Mint(1);

        g = convolution(g, q);
        g.resize(sz);
    }

    g.resize(n);
    return g;
}

Poly fps_pow_unit(const Poly& f, long long e, int n) {
    // This version is for f[0] = 1.
    assert(!f.empty() && f[0].v == 1);

    Poly lg = fps_log(f, n);
    Mint E = Mint(e % MOD);

    for (auto& x : lg) x *= E;

    return fps_exp(lg, n);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long m;
    cin >> n >> m;

    Poly a(n), b(n), c(n);

    long long x;
    for (auto& z : a) {
        cin >> x;
        z = Mint(x);
    }
    for (auto& z : b) {
        cin >> x;
        z = Mint(x);
    }
    for (auto& z : c) {
        cin >> x;
        z = Mint(x);
    }

    const int N = n - 1;

    /*
        h(x) = x + c_2 x^2 + ...

        phi(x) = x / h(x)
               = 1 / (h(x)/x).

        Let
            s(x) = h(x)/x
                 = c_1 + c_2 x + ... .
        Since c_1 = 1,
            phi(x) = 1 / s(x).
    */

    Poly s(N);
    for (int i = 0; i < N; ++i) {
        s[i] = c[i + 1];
    }

    // phi(x) mod x^N
    Poly phi = fps_inv(s, N);

    // P(x) = phi(x)^N mod x^N
    Poly P = fps_pow_unit(phi, N, N);

    /*
        Lagrange inversion:

        [x^N] g(x)^t
          = t/N * [x^(N-t)] phi(x)^N.

        Hence
        d_t = c_t * t/N * P[N-t].
    */

    Mint invN = Mint(N).inv();

    Poly d(N + 1);
    for (int t = 1; t <= N; ++t) {
        d[t] = c[t] * Mint(t) * invN * P[N - t];
    }

    /*
        ans_k = sum_{t=1}^N d_t q^(tk),
        q = a_1.

        Use
            tk = C(t+k,2) - C(t,2) - C(k,2).

        Therefore
            ans_k
              = q^(-C(k,2))
                sum_t (d_t q^(-C(t,2))) q^(C(t+k,2)).

        This is a cross-correlation, reducible to one convolution.
    */

    Mint q = a[1];
    Mint iq = q.inv();

    Poly RA(N + 1);

    Mint q_neg_choose_t2 = 1;   // q^{-C(t,2)}
    Mint iq_pow = 1;            // q^{-t}

    // Easier recurrence:
    // q^{-C(t+1,2)} = q^{-C(t,2)} * q^{-t}
    for (int t = 0; t <= N; ++t) {
        if (t >= 1) {
            // value already updated at end of previous t
        }

        RA[N - t] = d[t] * q_neg_choose_t2;

        q_neg_choose_t2 *= iq_pow;
        iq_pow *= iq;
    }

    // B[j] = q^{C(j,2)}, j = 0..N+m-1
    size_t M = (size_t)m;
    size_t Bsz = (size_t)N + M;

    Poly B(Bsz);

    Mint q_choose_j2 = 1;
    Mint q_pow = 1;  // q^j

    for (size_t j = 0; j < Bsz; ++j) {
        B[j] = q_choose_j2;

        q_choose_j2 *= q_pow;
        q_pow *= q;
    }

    Poly C = convolution(RA, B);

    // q^{-C(k,2)}
    Mint q_neg_choose_k2 = 1;
    Mint iq_pow_k = 1;  // q^{-k}

    for (long long k = 0; k < m; ++k) {
        Mint ans = C[(size_t)N + (size_t)k] * q_neg_choose_k2;

        if (k) cout << ' ';
        cout << ans.v;

        q_neg_choose_k2 *= iq_pow_k;
        iq_pow_k *= iq;
    }

    cout << '\n';
    return 0;
}