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

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

Depends on

• build/pch/stdc++.hpp
• library/formalpowerseries/Base.hpp
• library/formalpowerseries/Prod.hpp
• library/util/Valarray.hpp

Code

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

#define REP(i, n) for (int i = 0; i < (n); i++)

#include <atcoder/convolution>
#include <atcoder/modint>
using namespace atcoder;
using mint = modint998244353;
std::ostream &operator<<(std::ostream &os, mint a) {
    os << a.val();
    return os;
}
std::istream &operator>>(std::istream &is, mint &a) {
    long long b;
    is >> b;
    a = b;
    return is;
}

#include "library/formalpowerseries/Base.hpp"
using FPS = FormalPowerSeries<mint, 500001>;
#include "library/formalpowerseries/Prod.hpp"

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

    FPSProdDiversity<FPS> P;

    int n;
    std::cin >> n;
    REP (_, n) {
        int d;
        std::cin >> d;
        FPS f(d + 1);
        REP (i, d + 1)
            std::cin >> f[i];
        P.add(f);
    }
    FPS f = P.prod();
    REP (i, f.size())
        std::cout << f[i] << "\n "[i + 1 < f.size()];
}

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

#define REP(i, n) for (int i = 0; i < (n); i++)

#include <atcoder/convolution>
#include <atcoder/modint>
using namespace atcoder;
using mint = modint998244353;
std::ostream &operator<<(std::ostream &os, mint a) {
    os << a.val();
    return os;
}
std::istream &operator>>(std::istream &is, mint &a) {
    long long b;
    is >> b;
    a = b;
    return is;
}

#line 2 "library/util/Valarray.hpp"
#include <ranges>
#line 4 "library/util/Valarray.hpp"

template <typename T> struct Valarray : std::vector<T> {
    using std::vector<T>::vector; // コンストラクタ継承
    Valarray(const std::vector<T> &v) : std::vector<T>(v.begin(), v.end()) {}

  private:
    template <typename Op>
    Valarray &apply_inplace(const Valarray &other, Op op) {
        if (this->size() < other.size())
            this->resize(other.size(), T(0));

        for (auto [a, b] : std::views::zip(*this, other))
            a = op(a, b);

        return *this;
    }

  public:
    Valarray &operator+=(const Valarray &other) {
        return apply_inplace(other, std::plus<>());
    }
    Valarray &operator-=(const Valarray &other) {
        return apply_inplace(other, std::minus<>());
    }
    Valarray &operator*=(const Valarray &other) {
        return apply_inplace(other, std::multiplies<>());
    }
    Valarray &operator/=(const Valarray &other) {
        return apply_inplace(other, std::divides<>());
    }

    friend Valarray operator+(Valarray a, const Valarray &b) { return a += b; }
    friend Valarray operator-(Valarray a, const Valarray &b) { return a -= b; }
    friend Valarray operator*(Valarray a, const Valarray &b) { return a *= b; }
    friend Valarray operator/(Valarray a, const Valarray &b) { return a /= b; }

    Valarray operator-() const {
        Valarray g = *this;
        for (T &a : g)
            a = -a;
        return g;
    }
};
#line 3 "library/formalpowerseries/Base.hpp"

template <typename T, int MX> struct FormalPowerSeries : Valarray<T> {
    using FPS = FormalPowerSeries;
    static constexpr int max_size = MX;
    using Valarray<T>::Valarray;
    using Valarray<T>::size;
    using Valarray<T>::resize;
    using Valarray<T>::at;
    using Valarray<T>::begin;
    using Valarray<T>::end;
    using Valarray<T>::back;
    using Valarray<T>::pop_back;
    using value_type = T;

    void strict(int n) {
        if (size() > n)
            resize(n);
        shrink();
    }
    void shrink() {
        while (size() and back() == 0)
            pop_back();
    }

    FormalPowerSeries() = default;

    FormalPowerSeries(const std::vector<T> &f) : Valarray<T>(f) {
        strict(MX);
        shrink();
    }

    static FPS unit() { return {1}; }
    static FPS x() { return {0, 1}; }
#pragma region operator
    FPS operator-() const { return FPS(Valarray<T>::operator-()); }

    FPS &operator+=(const FPS &g) {
        Valarray<T>::operator+=(g);
        shrink();
        return *this;
    }
    FPS operator+(const FPS &g) const { return FPS(*this) += g; }

    FPS &operator-=(const FPS &g) {
        Valarray<T>::operator-=(g);
        shrink();
        return *this;
    }
    FPS operator-(const FPS &g) const { return FPS(*this) -= g; }

    FPS &operator+=(const T &a) {
        if (!size())
            resize(1);
        at(0) += a;
        return *this;
    }
    FPS operator+(const T &a) const { return FPS(*this) += a; }
    friend FPS operator+(const T &a, const FPS &f) { return f + a; }

    FPS &operator-=(const T &a) {
        if (!size())
            resize(1);
        at(0) -= a;
        return *this;
    }
    FPS operator-(const T &a) { return FPS(*this) -= a; }
    friend FPS operator-(const T &a, const FPS &f) { return a + (-f); }

    FPS operator*(const FPS &g) const { return FPS(convolution(*this, g)); }
    FPS &operator*=(const FPS &g) { return (*this) = (*this) * g; }

    FPS &operator*=(const T &a) {
        for (size_t i = 0; i < size(); i++)
            at(i) *= a;
        return *this;
    }
    FPS operator*(const T &a) const { return FPS(*this) *= a; }
    friend FPS operator*(const T &a, const FPS &f) { return f * a; }

    FPS operator/(const FPS &g) const { return (*this) * g.inv(); }
    FPS &operator/=(const FPS &g) { return (*this) = (*this) / g; }

    FPS &operator/=(const T &a) { return *this *= a.inv(); }
    FPS operator/(const T &a) { return FPS(*this) /= a; }

    FPS &operator<<=(const int d) {
        if (d >= MX)
            return *this = FPS(0);
        resize(std::min(MX, int(size()) + d));
        for (int i = int(size()) - 1 - d; i >= 0; i--)
            at(i + d) = at(i);
        for (int i = d - 1; i >= 0; i--)
            at(i) = 0;
        return *this;
    }
    FPS operator<<(const int d) const { return FPS(*this) <<= d; }
    FPS &operator>>=(const int d) {
        if (d >= size())
            return *this = FPS(0);
        for (size_t i = d; i < size(); i++)
            at(i - d) = at(i);
        strict(int(size()) - d);
        return *this;
    }
    FPS operator>>(const int d) const { return FPS(*this) >>= d; }
#pragma endregion operator

    FPS pre(int n) const {
        if (size() <= n)
            return *this;
        return FPS(Valarray<T>(this->begin(), this->begin() + n));
    }

    // 最小の非ゼロ次数（すべて 0 のときは size()）を返す
    int order() const {
        for (int i = 0; i < int(size()); i++) {
            if (at(i) != 0)
                return i;
        }
        return int(size());
    }

    FPS inv(int SZ = MX) const {
        assert(size() and at(0) != 0);
        FPS res = {at(0).inv()};
        for (int n = 1; n < SZ; n <<= 1) {
            res *= (2 - this->pre(n << 1) * res);
            res.strict(n << 1);
        }
        res.strict(SZ);
        return res;
    }

    // *this = f_1 + f_2 x^n ⇒ [*this←f_1, return f_2]
    FPS separate(int n) {
        if (size() <= n)
            return FPS(0);
        FPS f_2(size() - n);
        for (size_t i = n; i < size(); i++)
            f_2[i - n] = at(i);
        strict(n);
        return f_2;
    }

    T operator()(T a) const {
        T res = 0, b = 1;
        for (size_t i = 0; i < size(); i++, b *= a)
            res += at(i) * b;
        return res;
    }
};
#line 22 "test/library-checker/Polynomial/ProductOfPolynomialSequence.test.cpp"
using FPS = FormalPowerSeries<mint, 500001>;
#line 3 "library/formalpowerseries/Prod.hpp"
template <typename FPS> class FPSProd {
    std::queue<FPS> que;

  public:
    void add(const FPS &f) { que.push(f); }
    FPS prod() {
        if (!que.size())
            return FPS::unit();
        while (que.size() > 1) {
            FPS f = que.front();
            que.pop();
            FPS g = que.front();
            que.pop();
            que.push(f * g);
        }
        FPS res = que.front();
        que.pop();
        return res;
    }
};

template <typename FPS> class FPSProdDiversity {
    static constexpr auto cmp = [](const FPS &f, const FPS &g) {
        return f.size() > g.size();
    };
    std::priority_queue<FPS, std::vector<FPS>, decltype(cmp)> que{cmp};

  public:
    void add(const FPS &f) { que.push(f); }
    FPS prod() {
        if (!que.size())
            return FPS::unit();
        while (que.size() > 1) {
            FPS f = que.top();
            que.pop();
            FPS g = que.top();
            que.pop();
            que.push(f * g);
        }
        FPS res = que.top();
        que.pop();
        return res;
    }
};
#line 24 "test/library-checker/Polynomial/ProductOfPolynomialSequence.test.cpp"

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

    FPSProdDiversity<FPS> P;

    int n;
    std::cin >> n;
    REP (_, n) {
        int d;
        std::cin >> d;
        FPS f(d + 1);
        REP (i, d + 1)
            std::cin >> f[i];
        P.add(f);
    }
    FPS f = P.prod();
    REP (i, f.size())
        std::cout << f[i] << "\n "[i + 1 < f.size()];
}

Back to top page