#1176234 (C++23(gcc16)) No.3619 Compositional Power with Schröder Coordinate

• 問題: No.3619 Compositional Power with Schröder Coordinate
• ユーザー: noimi
• 提出日時: 2026-08-11 14:55:26
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 1,668 ms / 10,000 ms
• コード長: 11,340 bytes
• コンパイル時間: 3,192 ms
• コンパイル使用メモリ: 365,000 KB
• 実行使用メモリ: 149,932 KB
• 最終ジャッジ日時: 2026-08-11 14:55:40
• 合計ジャッジ時間: 13,452 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

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

ソースコード

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

Details of AI usage:
- I derived the main formula
      f^{<m>}(x) = h(a_1^m g(x)) mod x^n
  from
      g(f(x)) = a_1 g(x)
  and
      h(g(x)) = x.
- I asked ChatGPT to write the implementation for computing
      h(a_1^m g(x))
  using fast formal power series composition.
- ChatGPT wrote the NTT, formal power series inverse, and
  O(N log^2 N) formal power series composition implementation.
- The implementation strategy for fast FPS composition was also
  checked against a verified competitive-programming implementation.

The final code was tested on the samples and against a naive
implementation on small random cases.
*/

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

static constexpr uint32_t MOD = 998244353;

struct Mint {
    uint32_t v;

    Mint(long long x = 0) {
        long long y = x % (long long)MOD;
        if (y < 0) y += MOD;
        v = (uint32_t)y;
    }

    static Mint raw(uint32_t x) {
        Mint a;
        a.v = x;
        return a;
    }

    Mint& operator+=(const Mint& o) {
        uint32_t x = v + o.v;
        if (x >= MOD) x -= MOD;
        v = x;
        return *this;
    }

    Mint& operator-=(const Mint& o) {
        v = (v >= o.v ? v - o.v : v + MOD - o.v);
        return *this;
    }

    Mint& operator*=(const Mint& o) {
        v = (uint64_t)v * o.v % MOD;
        return *this;
    }

    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 v ? raw(MOD - v) : raw(0);
    }

    Mint pow(long long e) const {
        Mint a = *this, r = 1;
        while (e) {
            if (e & 1) r *= a;
            a *= a;
            e >>= 1;
        }
        return r;
    }

    Mint inv() const { return pow(MOD - 2); }
};

struct NTT {
    Mint dw[24], dy[24];

    NTT() {
        constexpr int level = 23;
        Mint w[24], y[24];

        w[level - 1] = Mint(3).pow((MOD - 1) / (1 << level));
        y[level - 1] = w[level - 1].inv();

        for (int i = level - 2; i > 0; --i) {
            w[i] = w[i + 1] * w[i + 1];
            y[i] = y[i + 1] * y[i + 1];
        }

        dw[1] = w[1];
        dy[1] = y[1];
        dw[2] = w[2];
        dy[2] = y[2];

        for (int i = 3; i < level; ++i) {
            dw[i] = dw[i - 1] * y[i - 2] * w[i];
            dy[i] = dy[i - 1] * w[i - 2] * y[i];
        }
    }

    void forward(vector<Mint>& a) {
        const int n = (int)a.size();
        if (n <= 1) return;

        const int k = __builtin_ctz((unsigned)n);

        if (k == 1) {
            Mint z = a[1];
            a[1] = a[0] - z;
            a[0] += z;
            return;
        }

        if (k & 1) {
            int half = 1 << (k - 1);
            for (int i = 0; i < half; ++i) {
                Mint z = a[i + half];
                a[i + half] = a[i] - z;
                a[i] += z;
            }
        }

        int blocks = 1 << (2 + (k & 1));
        int len = 1 << (k - 2 - (k & 1));
        const Mint imag = dw[1];

        while (len) {
            {
                int p0 = 0, p1 = len, p2 = 2 * len, p3 = 3 * len;
                for (; p0 < len; ++p0, ++p1, ++p2, ++p3) {
                    Mint a0 = a[p0], a1 = a[p1], a2 = a[p2], a3 = a[p3];
                    Mint s02 = a0 + a2, s13 = a1 + a3;
                    Mint d02 = a0 - a2, d13 = (a1 - a3) * imag;
                    a[p0] = s02 + s13;
                    a[p1] = s02 - s13;
                    a[p2] = d02 + d13;
                    a[p3] = d02 - d13;
                }
            }

            Mint x = dw[2];

            for (int b = 4; b < blocks;) {
                Mint x2 = x * x, x3 = x2 * x;
                int p0 = b * len, e = p0 + len, p2 = e + len;

                for (; p0 < e; ++p0, ++p2) {
                    Mint a0 = a[p0];
                    Mint a1 = a[p0 + len] * x;
                    Mint a2 = a[p2] * x2;
                    Mint a3 = a[p2 + len] * x3;

                    Mint s02 = a0 + a2, s13 = a1 + a3;
                    Mint d02 = a0 - a2, d13 = (a1 - a3) * imag;

                    a[p0] = s02 + s13;
                    a[p0 + len] = s02 - s13;
                    a[p2] = d02 + d13;
                    a[p2 + len] = d02 - d13;
                }

                b += 4;
                if (b < blocks) x *= dw[__builtin_ctz((unsigned)b)];
            }

            blocks <<= 2;
            len >>= 2;
        }
    }

    void inverse_unscaled(vector<Mint>& a) {
        const int n = (int)a.size();
        if (n <= 1) return;

        const int k = __builtin_ctz((unsigned)n);

        if (k == 1) {
            Mint z = a[1];
            a[1] = a[0] - z;
            a[0] += z;
            return;
        }

        int blocks = 1 << (k - 2);
        int len = 1;
        const Mint imag = dy[1];

        while (blocks) {
            {
                int p0 = 0, p1 = len, p2 = 2 * len, p3 = 3 * len;

                for (; p0 < len; ++p0, ++p1, ++p2, ++p3) {
                    Mint a0 = a[p0], a1 = a[p1], a2 = a[p2], a3 = a[p3];
                    Mint s01 = a0 + a1, s23 = a2 + a3;
                    Mint d01 = a0 - a1, d23 = (a2 - a3) * imag;

                    a[p0] = s01 + s23;
                    a[p2] = s01 - s23;
                    a[p1] = d01 + d23;
                    a[p3] = d01 - d23;
                }
            }

            Mint x = dy[2];
            int lim = blocks << 2;

            for (int b = 4; b < lim;) {
                Mint x2 = x * x, xi = x * imag;
                int p0 = b * len, e = p0 + len, p2 = e + len;

                for (; p0 < e; ++p0, ++p2) {
                    Mint a0 = a[p0], a1 = a[p0 + len];
                    Mint a2 = a[p2], a3 = a[p2 + len];

                    Mint s01 = a0 + a1, s23 = a2 + a3;
                    Mint d01 = (a0 - a1) * x;
                    Mint d23 = (a2 - a3) * xi;

                    a[p0] = s01 + s23;
                    a[p2] = (s01 - s23) * x2;
                    a[p0 + len] = d01 + d23;
                    a[p2 + len] = (d01 - d23) * x2;
                }

                b += 4;
                if (b < lim) x *= dy[__builtin_ctz((unsigned)b)];
            }

            blocks >>= 2;
            len <<= 2;
        }

        if (k & 1) {
            int half = 1 << (k - 1);
            for (int i = 0; i < half; ++i) {
                Mint d = a[i] - a[i + half];
                a[i] += a[i + half];
                a[i + half] = d;
            }
        }
    }

    void inverse(vector<Mint>& a) {
        inverse_unscaled(a);
        Mint inv_n = Mint((int)a.size()).inv();
        for (Mint& x : a) x *= inv_n;
    }
};

static NTT ntt_engine;
using Poly = vector<Mint>;

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

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

    if (min(a.size(), b.size()) <= 32) {
        Poly c(need);
        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 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_engine.forward(A);
    ntt_engine.forward(B);

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

    ntt_engine.inverse(A);
    A.resize(need);
    return A;
}

Poly prefix(const Poly& a, int n) {
    Poly r(n);
    for (int i = 0; i < min(n, (int)a.size()); ++i) r[i] = a[i];
    return r;
}

Poly reversed(Poly a) {
    reverse(a.begin(), a.end());
    return a;
}

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

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

    while ((int)r.size() < deg) {
        int m = min(deg, (int)r.size() * 2);
        Poly fc = prefix(f, m);

        Poly t = convolution(fc, r);
        t.resize(m);

        for (int i = 0; i < m; ++i) t[i] = -t[i];
        t[0] += Mint(2);

        r = convolution(r, t);
        r.resize(m);
    }

    return r;
}

// composition(f, g, deg) = g(f(x)) mod x^deg
Poly composition(Poly f, Poly g, int deg) {
    f.resize(deg);
    g.resize(deg);

    int n = deg - 1;
    int H = 1;
    while (H < deg) H <<= 1;

    Poly Q(H);
    for (int i = 0; i < deg; ++i) Q[i] = -f[i];

    function<Poly(Poly, int, int, int)> dfs =
        [&](Poly Q, int n, int h, int k) -> Poly {

        if (n == 0) {
            Poly T(Q.begin(), Q.begin() + k);
            T.push_back(Mint(1));

            Poly R = reversed(T);
            Poly I = fps_inverse(R, (int)R.size());
            I = reversed(I);

            Poly u = convolution(g, I);
            Poly P(h * k);

            for (int i = 0; i < (int)g.size(); ++i)
                P[k - 1 - i] = u[i + k];

            return P;
        }

        const int L = 4 * h * k;

        Poly nQ(L);
        Poly nR(2 * h * k);

        for (int i = 0; i < k; ++i) {
            copy(
                Q.begin() + i * h,
                Q.begin() + i * h + n + 1,
                nQ.begin() + i * 2 * h
            );
        }

        nQ[k * 2 * h] += Mint(1);
        ntt_engine.forward(nQ);

        for (int i = 0; i < L; i += 2)
            swap(nQ[i], nQ[i + 1]);

        for (int i = 0; i < L / 2; ++i)
            nR[i] = nQ[2 * i] * nQ[2 * i + 1];

        ntt_engine.inverse(nR);
        nR[0] -= Mint(1);

        Poly nextQ(h * k);

        for (int i = 0; i < 2 * k; ++i)
            for (int j = 0; j <= n / 2; ++j)
                nextQ[i * h / 2 + j] = nR[i * h + j];

        Poly P = dfs(move(nextQ), n / 2, h / 2, k * 2);

        Poly nP(L);

        for (int i = 0; i < 2 * k; ++i)
            for (int j = 0; j <= n / 2; ++j)
                nP[i * 2 * h + j * 2 + n % 2] =
                    P[i * h / 2 + j];

        ntt_engine.forward(nP);

        for (int i = 1; i < L; i <<= 1)
            reverse(nQ.begin() + i, nQ.begin() + 2 * i);

        for (int i = 0; i < L; ++i)
            nP[i] *= nQ[i];

        ntt_engine.inverse(nP);

        Poly out(h * k);

        for (int i = 0; i < k; ++i) {
            copy(
                nP.begin() + i * 2 * h,
                nP.begin() + i * 2 * h + n + 1,
                out.begin() + i * h
            );
        }

        return out;
    };

    Poly P = dfs(move(Q), n, H, 1);
    P.resize(deg);
    reverse(P.begin(), P.end());

    return P;
}

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

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

    Poly f(n), g(n), h(n);

    long long x;

    for (Mint& z : f) {
        cin >> x;
        z = Mint(x);
    }

    for (Mint& z : g) {
        cin >> x;
        z = Mint(x);
    }

    for (Mint& z : h) {
        cin >> x;
        z = Mint(x);
    }

    /*
        g(f(x)) = a_1 g(x)

        => g(f^{<m>}(x)) = a_1^m g(x)

        Since h = g^{-1},

        f^{<m>}(x) = h(a_1^m g(x)).
    */

    Mint lambda = f[1].pow(m);

    for (Mint& z : g)
        z *= lambda;

    Poly ans = composition(g, h, n);

    for (int i = 0; i < n; ++i) {
        if (i) cout << ' ';
        cout << ans[i].v;
    }

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