test/FPSprod.test.cpp

• View this file on GitHub
• Last update: 2025-07-04 15:57:54+09:00
• Problem: https://judge.yosupo.jp/problem/product_of_polynomial_sequence

Depends on

• atcoder/convolution.hpp
• atcoder/internal_bit.hpp
• atcoder/internal_math.hpp
• atcoder/internal_type_traits.hpp
• atcoder/modint.hpp
• FormalPowerSeries.cpp
• mod_sqrt.cpp
• template.cpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/product_of_polynomial_sequence
#include "../FormalPowerSeries.cpp"
using mint = atcoder::modint998244353;
int main() {
    int n;
    cin >> n;
    vector<FormalPowerSeries<mint>> f(n);
    for (int i = 0; i < n; i++) {
        int d;
        cin >> d;
        f[i].resize(d + 1);
        for (auto &x : f[i]) {
            int a;
            cin >> a;
            x = a;
        }
    }
    auto g = FPS_Product<mint>(f);
    for (mint x : g) cout << x.val() << " ";
    cout << endl;
}

#line 1 "test/FPSprod.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/product_of_polynomial_sequence
#line 1 "FormalPowerSeries.cpp"
#include <atcoder/convolution>
#line 1 "template.cpp"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
template <class T>
using pbds_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T>
using pbds_mset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
using pbds_trie = trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update>;
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(v) v.begin(), v.end()
template <class T, class U>
inline bool chmax(T &a, U b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T, class U>
inline bool chmin(T &a, U b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
constexpr int INF = 1000000000;
constexpr int64_t llINF = 3000000000000000000;
constexpr double eps = 1e-10;
const double pi = acos(-1);
template <class T>
inline void compress(vector<T> &a) {
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
}
struct linear_sieve {
    vector<int> least_factor, prime_list;
    linear_sieve(int n) : least_factor(n + 1, 0) {
        for (int i = 2; i <= n; i++) {
            if (least_factor[i] == 0) {
                least_factor[i] = i;
                prime_list.push_back(i);
            }
            for (int p : prime_list) {
                if (ll(i) * p > n || p > least_factor[i]) break;
                least_factor[i * p] = p;
            }
        }
    }
};
ll extgcd(ll a, ll b, ll &x, ll &y) {
    // ax+by=gcd(|a|,|b|)
    if (a < 0 || b < 0) {
        ll d = extgcd(abs(a), abs(b), x, y);
        if (a < 0) x = -x;
        if (b < 0) y = -y;
        return d;
    }
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
ll modpow(ll a, ll b, ll m) {
    ll res = 1;
    while (b) {
        if (b & 1) {
            res *= a;
            res %= m;
        }
        a *= a;
        a %= m;
        b >>= 1;
    }
    return res;
}
template <typename T, typename U>
inline istream &operator>>(istream &is, pair<T, U> &rhs) {
    return is >> rhs.first >> rhs.second;
}
template <typename T>
inline istream &operator>>(istream &is, vector<T> &v) {
    for (auto &e : v) is >> e;
    return is;
}
template <typename T, typename U>
inline ostream &operator<<(ostream &os, const pair<T, U> &rhs) {
    return os << rhs.first << " " << rhs.second;
}
template <typename T>
inline ostream &operator<<(ostream &os, const vector<T> &v) {
    for (auto itr = v.begin(), end_itr = v.end(); itr != end_itr;) {
        os << *itr;
        if (++itr != end_itr) os << " ";
    }
    return os;
}
#line 2 "mod_sqrt.cpp"
int64_t mod_sqrt(const int64_t& a, const int64_t& p) {
    assert(0 <= a && a < p);
    if (a < 2) return a;
    if (modpow(a, (p - 1) >> 1, p) != 1) return -1;
    int64_t q = p - 1, m = 0;
    while (!(q & 1)) {
        q >>= 1;
        m++;
    }
    int64_t z = 1;
    while (modpow(z, (p - 1) >> 1, p) == 1) z++;
    int64_t c = modpow(z, q, p);
    int64_t t = modpow(a, q, p);
    int64_t r = modpow(a, (q + 1) >> 1, p);
    if (t == 0) return 0;
    m -= 2;
    while (t != 1) {
        while (modpow(t, int64_t(1) << m, p) == 1) {
            c = c * c % p;
            m--;
        }
        r = r * c % p;
        c = c * c % p;
        t = t * c % p;
        m--;
    }
    return r;
}
#line 3 "FormalPowerSeries.cpp"
template <typename mint>
struct FormalPowerSeries : vector<mint> {
    using vector<mint>::vector;
    using FPS = FormalPowerSeries;
    FPS& operator+=(const FPS& r) {
        if (r.size() > this->size()) this->resize(r.size());
        for (int i = 0; i < (int)r.size(); i++) (*this)[i] += r[i];
        return *this;
    }
    FPS& operator+=(const mint& r) {
        if (this->empty()) this->resize(1);
        (*this)[0] += r;
        return *this;
    }

    FPS& operator-=(const FPS& r) {
        if (r.size() > this->size()) this->resize(r.size());
        for (int i = 0; i < (int)r.size(); i++) (*this)[i] -= r[i];
        return *this;
    }

    FPS& operator-=(const mint& r) {
        if (this->empty()) this->resize(1);
        (*this)[0] -= r;
        return *this;
    }
    FPS& operator*=(const FPS& r) {
        if (this->empty() || r.empty()) {
            this->clear();
            return *this;
        }
        assert(mint::mod() == 998244353);
        vector<mint> prod = atcoder::convolution(*this, r);
        this->resize((int)prod.size());
        for (int i = 0; i < (int)this->size(); i++) (*this)[i] = prod[i];
        return *this;
    }
    FPS& operator*=(const mint& v) {
        for (int i = 0; i < (int)this->size(); i++) (*this)[i] *= v;
        return *this;
    }
    FPS& operator/=(const FPS& r) {
        if (this->size() < r.size()) {
            this->clear();
            return *this;
        }
        int n = this->size() - r.size() + 1;
        return *this = (rev().pre(n) * r.rev().inv(n)).pre(n).rev();
    }
    FPS& operator%=(const FPS& r) {
        *this -= *this / r * r;
        shrink();
        return *this;
    }
    FPS operator+(const FPS& r) const { return FPS(*this) += r; }
    FPS operator+(const mint& v) const { return FPS(*this) += v; }
    FPS operator-(const FPS& r) const { return FPS(*this) -= r; }
    FPS operator-(const mint& v) const { return FPS(*this) -= v; }
    FPS operator*(const FPS& r) const { return FPS(*this) *= r; }
    FPS operator*(const mint& v) const { return FPS(*this) *= v; }
    FPS operator/(const FPS& r) const { return FPS(*this) /= r; }
    FPS operator%(const FPS& r) const { return FPS(*this) %= r; }
    FPS operator-() const {
        FPS ret(this->size());
        for (int i = 0; i < (int)this->size(); i++) ret[i] = -(*this)[i];
        return ret;
    }
    void shrink() {
        while (this->size() && this->back() == mint(0)) this->pop_back();
    }
    FPS operator>>(int sz) const {
        if ((int)this->size() <= sz) return {};
        FPS ret(*this);
        ret.erase(ret.begin(), ret.begin() + sz);
        return ret;
    }
    FPS operator<<(int sz) const {
        FPS ret(*this);
        ret.insert(ret.begin(), sz, mint(0));
        return ret;
    }
    FPS pre(int sz) const { return FPS(begin(*this), begin(*this) + min((int)this->size(), sz)); }
    FPS rev() const {
        FPS ret(*this);
        reverse(begin(ret), end(ret));
        return ret;
    }
    FPS diff() const {
        const int n = this->size();
        FPS ret(max(0, n - 1));
        for (int i = 1; i < n; i++) ret[i - 1] = (*this)[i] * mint(i);
        return ret;
    }
    FPS integral() const {
        const int n = this->size();
        FPS ret(n + 1);
        ret[0] = mint(0);
        if (n > 0) ret[1] = mint(1);
        auto mod = mint::mod();
        for (int i = 2; i <= n; i++) ret[i] = (-ret[mod % i] * (mod / i));
        for (int i = 0; i < n; i++) ret[i + 1] *= (*this)[i];
        return ret;
    }
    FPS inv(int deg = -1) const {
        assert(((*this)[0]) != mint(0));
        const int n = this->size();
        if (deg == -1) deg = n;
        FPS ret({mint(1) / (*this)[0]});
        for (int i = 1; i < deg; i <<= 1) {
            ret = (ret + ret - ret * ret * pre(i << 1)).pre(i << 1);
        }
        return ret.pre(deg);
    }
    FPS log(int deg = -1) {
        assert((*this)[0] == mint(1));
        if (deg == -1) deg = this->size();
        return (this->diff() * this->inv(deg)).pre(deg - 1).integral();
    }
    FPS exp(int deg = -1) const {
        assert((*this)[0] == mint(0));
        const int n = this->size();
        if (deg == -1) deg = n;
        FPS ret({mint(1)});
        for (int i = 1; i < deg; i <<= 1) {
            ret = (ret * (pre(i << 1) + mint(1) - ret.log(i << 1))).pre(i << 1);
        }
        return ret.pre(deg);
    }
    FPS pow(int64_t k, int deg = -1) const {
        const int n = this->size();
        if (deg == -1) deg = n;
        if (k == 0) {
            FPS ret(deg);
            if (deg) ret[0] = 1;
            return ret;
        }
        for (int i = 0; i < n; i++) {
            if ((*this)[i] != mint(0)) {
                mint rev = mint(1) / (*this)[i];
                FPS ret = (((*this * rev) >> i).log(deg) * k).exp(deg);
                ret *= (*this)[i].pow(k);
                ret = (ret << (i * k)).pre(deg);
                if ((int)ret.size() < deg) ret.resize(deg, mint(0));
                return ret;
            }
            if (__int128_t(i + 1) * k >= deg) return FPS(deg, mint(0));
        }
        return FPS(deg, mint(0));
    }
    FPS sqrt(int deg = -1) const {
        const int n = this->size();
        if (deg == -1) deg = n;
        if (n == 0) return FPS(deg, 0);
        if ((*this)[0] == mint(0)) {
            for (int i = 1; i < n; i++) {
                if ((*this)[i] != mint(0)) {
                    if (i & 1) return {};
                    if (deg - i / 2 <= 0) break;
                    auto ret = (*this >> i).sqrt(deg - i / 2);
                    if (ret.empty()) return {};
                    ret = ret << (i / 2);
                    if ((int)ret.size() < deg) ret.resize(deg, mint(0));
                    return ret;
                }
            }
            return FPS(deg, 0);
        }
        int64_t sqr = mod_sqrt((*this)[0].val(), mint::mod());
        if (sqr == -1) return {};
        assert(sqr * sqr % mint::mod() == (*this)[0].val());
        FPS ret({mint(sqr)});
        mint inv2 = mint(2).inv();
        for (int i = 1; i < deg; i <<= 1) {
            ret = (ret + pre(i << 1) * ret.inv(i << 1)) * inv2;
        }
        return ret.pre(deg);
    }
    mint eval(mint x) const {
        mint r = 0, w = 1;
        for (auto& v : *this) r += w * v, w *= x;
        return r;
    }
};
template <typename mint>
FormalPowerSeries<mint> FPS_Product(vector<FormalPowerSeries<mint>> f) {
    int n = (int)f.size();
    if (n == 0) return {1};
    function<FormalPowerSeries<mint>(int, int)> calc = [&](int l, int r) {
        if (r - l == 1) return f[l];
        int m = (l + r) / 2;
        return calc(l, m) * calc(m, r);
    };
    return calc(0, n);
}
#line 3 "test/FPSprod.test.cpp"
using mint = atcoder::modint998244353;
int main() {
    int n;
    cin >> n;
    vector<FormalPowerSeries<mint>> f(n);
    for (int i = 0; i < n; i++) {
        int d;
        cin >> d;
        f[i].resize(d + 1);
        for (auto &x : f[i]) {
            int a;
            cin >> a;
            x = a;
        }
    }
    auto g = FPS_Product<mint>(f);
    for (mint x : g) cout << x.val() << " ";
    cout << endl;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	all_degree_one_00	AC	852 ms	67 MB
g++	all_degree_one_01	AC	849 ms	67 MB
g++	all_degree_one_02	AC	851 ms	67 MB
g++	all_degree_one_03	AC	859 ms	67 MB
g++	all_degree_one_04	AC	847 ms	67 MB
g++	example_00	AC	5 ms	4 MB
g++	example_01	AC	4 ms	4 MB
g++	example_02	AC	4 ms	4 MB
g++	max_and_zero_00	AC	519 ms	70 MB
g++	max_random_00	AC	807 ms	56 MB
g++	max_random_01	AC	852 ms	64 MB
g++	max_random_02	AC	589 ms	22 MB
g++	max_random_03	AC	839 ms	60 MB
g++	max_random_04	AC	743 ms	44 MB
g++	random_00	AC	746 ms	55 MB
g++	random_01	AC	792 ms	63 MB
g++	random_02	AC	511 ms	19 MB
g++	random_03	AC	292 ms	51 MB
g++	random_04	AC	287 ms	36 MB
g++	small_00	AC	5 ms	4 MB
g++	small_01	AC	4 ms	4 MB
g++	small_02	AC	4 ms	4 MB
g++	small_03	AC	4 ms	4 MB
g++	small_04	AC	4 ms	4 MB
g++	unbalanced_00	AC	916 ms	74 MB
g++	unbalanced_01	AC	921 ms	76 MB
g++	unbalanced_02	AC	929 ms	75 MB
clang++	all_degree_one_00	AC	853 ms	68 MB
clang++	all_degree_one_01	AC	842 ms	68 MB
clang++	all_degree_one_02	AC	840 ms	68 MB
clang++	all_degree_one_03	AC	875 ms	68 MB
clang++	all_degree_one_04	AC	839 ms	68 MB
clang++	example_00	AC	5 ms	4 MB
clang++	example_01	AC	4 ms	4 MB
clang++	example_02	AC	4 ms	4 MB
clang++	max_and_zero_00	AC	538 ms	72 MB
clang++	max_random_00	AC	807 ms	56 MB
clang++	max_random_01	AC	865 ms	64 MB
clang++	max_random_02	AC	658 ms	22 MB
clang++	max_random_03	AC	834 ms	60 MB
clang++	max_random_04	AC	737 ms	43 MB
clang++	random_00	AC	748 ms	55 MB
clang++	random_01	AC	794 ms	63 MB
clang++	random_02	AC	512 ms	19 MB
clang++	random_03	AC	296 ms	51 MB
clang++	random_04	AC	286 ms	36 MB
clang++	small_00	AC	5 ms	4 MB
clang++	small_01	AC	4 ms	4 MB
clang++	small_02	AC	4 ms	4 MB
clang++	small_03	AC	4 ms	4 MB
clang++	small_04	AC	4 ms	3 MB
clang++	unbalanced_00	AC	919 ms	75 MB
clang++	unbalanced_01	AC	919 ms	75 MB
clang++	unbalanced_02	AC	908 ms	75 MB

Back to top page