test/library-checker/Polynomial/Convolution.test.cpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Problem: https://judge.yosupo.jp/problem/convolution_mod

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/convolution_mod"
#include <bits/stdc++.h>

#include "library/convolution/NTT.hpp"
#include "library/mod/Modint.hpp"

using mint = Mint<long long, 998244353>;

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

    int n, m;
    std::cin >> n >> m;
    std::vector<mint> f(n), g(m);
    for (mint &p : f)
        std::cin >> p;
    for (mint &p : g)
        std::cin >> p;
    auto h = convolution(f, g);
    for (mint &p : h)
        std::cout << p << " ";
    std::cout << std::endl;
}

#line 1 "test/library-checker/Polynomial/Convolution.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/convolution_mod"
#include <bits/stdc++.h>

#line 2 "library/convolution/NTT.hpp"
#define REP_(i, n) for (int i = 0; i < (n); i++)
#define RREP_(i, n) for (int i = (n)-1; i >= 0; i--)

template <typename MINT>
std::vector<MINT> convolution(std::vector<MINT> f, std::vector<MINT> g) {
    int nf = f.size(), ng = g.size();
    if (!nf or !ng)
        return std::vector<MINT>{};
    int M = nf + ng - 1;

    if (nf <= 60 or ng <= 60) {
        std::vector<MINT> res(M, 0);
        REP_(i, nf) REP_(j, ng) res[i + j] += f[i] * g[j];
        return res;
    }

    int lg;
    for (lg = 0; (1 << lg) < M; lg++) {
    }
    const int N = 1 << lg;
    f.resize(N, 0);
    g.resize(N, 0);

    static_assert(MINT::mod == 998244353);
    MINT c = MINT(3).pow((MINT::mod - 1) >> lg);
    std::vector<MINT> cs(N);
    REP_(i, N) cs[i] = (i ? cs[i - 1] * c : 1);

    std::vector<int> x(N, 0);
    REP_(h, lg)
    REP_(S, 1 << h)
    REP_(T, 1 << (lg - h - 1)) {
        int l = (S << (lg - h)) | T;
        int r = l | (1 << (lg - h - 1));

        x[l] >>= 1;
        (x[r] >>= 1) |= 1 << (lg - 1);

        MINT a = f[l];
        f[l] += f[r] * cs[x[l]];
        (f[r] *= cs[x[r]]) += a;

        a = g[l];
        g[l] += g[r] * cs[x[l]];
        (g[r] *= cs[x[r]]) += a;
    }
    REP_(i, N) f[i] *= g[i];

    std::ranges::fill(x, 0);
    c = c.inv();
    REP_(i, N) cs[i] = (i ? cs[i - 1] * c : 1);
    RREP_(h, lg)
    REP_(S, 1 << h)
    REP_(T, 1 << (lg - h - 1)) {
        int l = (S << (lg - h)) | T;
        int r = l | (1 << (lg - h - 1));

        x[l] >>= 1;
        (x[r] >>= 1) |= 1 << (lg - 1);

        MINT a = f[l];
        f[l] += f[r] * cs[x[l]];
        (f[r] *= cs[x[r]]) += a;
    }
    f.resize(M);
    MINT Ninv = MINT(N).inv();
    REP_(i, M) f[i] *= Ninv;
    return f;
}
#undef REP_
#undef RREP_
#line 2 "library/math/ExtraGCD.hpp"
using ll = long long;
std::pair<ll, ll> ext_gcd(ll a, ll b) {
    if (b == 0)
        return {1, 0};
    auto [X, Y] = ext_gcd(b, a % b);
    // bX + (a%b)Y = gcd(a,b)
    // a%b = a - b(a/b)
    // ∴ aY + b(X-(a/b)Y) = gcd(a,b)
    ll x = Y, y = X - (a / b) * Y;
    return {x, y};
}
#line 3 "library/mod/Modint.hpp"
template <typename T, T MOD = 998244353> struct Mint {
    inline static constexpr T mod = MOD;
    T v;
    Mint() : v(0) {}
    Mint(signed v) : v(v) {}
    Mint(long long t) {
        v = t % MOD;
        if (v < 0)
            v += MOD;
    }

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

    Mint pow(long long k) const {
        Mint res(1), tmp(v);
        while (k) {
            if (k & 1)
                res *= tmp;
            tmp *= tmp;
            k >>= 1;
        }
        return res;
    }

    static Mint add_identity() { return Mint(0); }
    static Mint mul_identity() { return Mint(1); }

    // Mint inv()const{return pow(MOD-2);}
    Mint inv() const { return Mint(ext_gcd(v, mod).first); }

    Mint &operator+=(Mint a) {
        v += a.v;
        if (v >= MOD)
            v -= MOD;
        return *this;
    }
    Mint &operator-=(Mint a) {
        v += MOD - a.v;
        if (v >= MOD)
            v -= MOD;
        return *this;
    }
    Mint &operator*=(Mint a) {
        v = 1LL * v * a.v % MOD;
        return *this;
    }
    Mint &operator/=(Mint a) { return (*this) *= a.inv(); }

    Mint operator+(Mint a) const { return Mint(v) += a; }
    Mint operator-(Mint a) const { return Mint(v) -= a; }
    Mint operator*(Mint a) const { return Mint(v) *= a; }
    Mint operator/(Mint a) const { return Mint(v) /= a; }
#define FRIEND(op)                                                             \
    friend Mint operator op(int a, Mint b) { return Mint(a) op b; }
    FRIEND(+);
    FRIEND(-);
    FRIEND(*);
    FRIEND(/);
#undef FRIEND
    Mint operator+() const { return *this; }
    Mint operator-() const { return v ? Mint(MOD - v) : Mint(v); }

    bool operator==(const Mint a) const { return v == a.v; }
    bool operator!=(const Mint a) const { return v != a.v; }

    static Mint comb(long long n, int k) {
        Mint num(1), dom(1);
        for (int i = 0; i < k; i++) {
            num *= Mint(n - i);
            dom *= Mint(i + 1);
        }
        return num / dom;
    }

    friend std::ostream &operator<<(std::ostream &os, const Mint &m) {
        os << m.v;
        return os;
    }
    friend std::istream &operator>>(std::istream &is, Mint &m) {
        is >> m.v;
        m.v %= MOD;
        if (m.v < 0)
            m.v += MOD;
        return is;
    }
};
#line 6 "test/library-checker/Polynomial/Convolution.test.cpp"

using mint = Mint<long long, 998244353>;

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

    int n, m;
    std::cin >> n >> m;
    std::vector<mint> f(n), g(m);
    for (mint &p : f)
        std::cin >> p;
    for (mint &p : g)
        std::cin >> p;
    auto h = convolution(f, g);
    for (mint &p : h)
        std::cout << p << " ";
    std::cout << std::endl;
}