test/yosupo/polynomial/multipoint_evaluation.test.cpp

AC · 最終更新 2026-09-07 · GitHub

問題: https://judge.yosupo.jp/problem/multipoint_evaluation

依存するヘッダ（11）

二項係数・階乗・順列・多項係数・重複組合せ lib/combinatorics/combinatorics.hpp
形式的冪級数 (FPS) lib/convolution/formal_power_series.hpp
NTT・畳み込み (convolution) lib/convolution/ntt.hpp
Montgomery + AVX2 による NTT 畳み込み (NTT-friendly な 32bit 素数 mod 専用) lib/convolution/ntt_avx2.hpp
internal/internal_fft.hpp lib/internal/internal_fft.hpp
internal/internal_fft_avx2.hpp lib/internal/internal_fft_avx2.hpp
internal/internal_fps_avx2.hpp lib/internal/internal_fps_avx2.hpp
internal/internal_math.hpp lib/internal/internal_math.hpp
internal/internal_type_traits.hpp lib/internal/internal_type_traits.hpp
modint (static_modint / dynamic_modint) lib/number_theory/modint.hpp
素数法上で `x` の平方根を 1 つ返す lib/number_theory/root_mod.hpp

実装

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/multipoint_evaluation
#include <iostream>
#include <vector>
#include "convolution/formal_power_series.hpp"

using Mint = modint998;

int main(void) {
    int n, m;
    std::cin >> n >> m;
    std::vector<Mint> c(n), p(m);
    for (Mint &e : c) std::cin >> e;
    for (Mint &e : p) std::cin >> e;
    auto ans = fps::multipoint_evaluation(c, p);
    for (int i = 0; i < m; ++i) std::cout << ans[i] << " \n"[i == m - 1];

    return 0;
}