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

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

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/multipoint_evaluation"
#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, (1 << 17) + 1>;
#include "library/formalpowerseries/MultipointEvaluation.hpp"

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

    int n, m;
    std::cin >> n >> m;
    FPS f(n);
    REP (i, n)
        std::cin >> f[i];
    std::vector<mint> p(m);
    REP (j, m)
        std::cin >> p[j];

    std::vector<mint> ans = multipoint_evaluation(f, p);
    REP (j, m)
        std::cout << ans[j] << "\n "[j + 1 < m];
}

#line 1 "test/library-checker/Polynomial/MultipointEvaluation.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/multipoint_evaluation"
#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 21 "test/library-checker/Polynomial/MultipointEvaluation.test.cpp"
using FPS = FormalPowerSeries<mint, (1 << 17) + 1>;
#line 3 "library/formalpowerseries/DivMod.hpp"
template <typename FPS> std::pair<FPS, FPS> div_mod(FPS f, FPS g) {
    f.shrink();
    g.shrink();
    assert(g.size());
    if (f.size() < g.size())
        return {FPS(0), f};
    std::ranges::reverse(f);
    std::ranges::reverse(g);
    int d = f.size() - g.size() + 1;
    FPS q = (f.pre(d) * g.inv(d)).pre(d);
    if (q.size() < d)
        q.resize(d, 0);
    std::ranges::reverse(q);
    std::ranges::reverse(f);
    std::ranges::reverse(g);
    return {q, f - q * g};
}
#undef REVERSE_
#line 4 "library/formalpowerseries/MultipointEvaluation.hpp"
template <typename FPS, typename T = typename FPS::value_type>
std::vector<T> multipoint_evaluation(const FPS &f, std::vector<T> v) {
    int m = v.size();
    int sz;
    for (sz = 1; sz < m; sz *= 2) {
    }
    std::vector<FPS> t(sz * 2);
    for (int i = 0; i < sz; i++)
        t[sz + i] = {(i < m ? -v[i] : 0), 1};
    for (int i = sz - 1; i > 0; i--)
        t[i] = t[2 * i] * t[2 * i + 1];

    t[0] = f;
    for (int i = 1; i < sz + m; i++)
        t[i] = div_mod(t[i >> 1], t[i]).second;

    for (int i = 0; i < m; i++)
        v[i] = t[sz + i][0];
    return v;
}
#line 23 "test/library-checker/Polynomial/MultipointEvaluation.test.cpp"

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

    int n, m;
    std::cin >> n >> m;
    FPS f(n);
    REP (i, n)
        std::cin >> f[i];
    std::vector<mint> p(m);
    REP (j, m)
        std::cin >> p[j];

    std::vector<mint> ans = multipoint_evaluation(f, p);
    REP (j, m)
        std::cout << ans[j] << "\n "[j + 1 < m];
}