This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/shift_of_sampling_points_of_polynomial" #include <iostream> #include <atcoder/modint> #include "library/polynomial/shift_of_sampling_points.hpp" int main() { using mint = atcoder::modint998244353; std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m, c; std::cin >> n >> m >> c; std::vector<mint> ys(n); for (int i = 0, v; i < n; ++i) std::cin >> v, ys[i] = v; std::vector<mint> ans = suisen::shift_of_sampling_points<mint>(ys, c, m); for (int i = 0; i < m; ++i) { std::cout << ans[i].val(); if (i + 1 != m) std::cout << ' '; } std::cout << '\n'; return 0; }
#line 1 "test/src/polynomial/shift_of_sampling_points/shift_of_sampling_points_of_polynomial.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/shift_of_sampling_points_of_polynomial" #include <iostream> #include <atcoder/modint> #line 1 "library/polynomial/shift_of_sampling_points.hpp" #include <vector> #include <atcoder/convolution> #line 1 "library/math/factorial.hpp" #include <cassert> #line 6 "library/math/factorial.hpp" namespace suisen { template <typename T, typename U = T> struct factorial { factorial() = default; factorial(int n) { ensure(n); } static void ensure(const int n) { int sz = _fac.size(); if (n + 1 <= sz) return; int new_size = std::max(n + 1, sz * 2); _fac.resize(new_size), _fac_inv.resize(new_size); for (int i = sz; i < new_size; ++i) _fac[i] = _fac[i - 1] * i; _fac_inv[new_size - 1] = U(1) / _fac[new_size - 1]; for (int i = new_size - 1; i > sz; --i) _fac_inv[i - 1] = _fac_inv[i] * i; } T fac(const int i) { ensure(i); return _fac[i]; } T operator()(int i) { return fac(i); } U fac_inv(const int i) { ensure(i); return _fac_inv[i]; } U binom(const int n, const int r) { if (n < 0 or r < 0 or n < r) return 0; ensure(n); return _fac[n] * _fac_inv[r] * _fac_inv[n - r]; } template <typename ...Ds, std::enable_if_t<std::conjunction_v<std::is_integral<Ds>...>, std::nullptr_t> = nullptr> U polynom(const int n, const Ds& ...ds) { if (n < 0) return 0; ensure(n); int sumd = 0; U res = _fac[n]; for (int d : { ds... }) { if (d < 0 or d > n) return 0; sumd += d; res *= _fac_inv[d]; } if (sumd > n) return 0; res *= _fac_inv[n - sumd]; return res; } U perm(const int n, const int r) { if (n < 0 or r < 0 or n < r) return 0; ensure(n); return _fac[n] * _fac_inv[n - r]; } private: static std::vector<T> _fac; static std::vector<U> _fac_inv; }; template <typename T, typename U> std::vector<T> factorial<T, U>::_fac{ 1 }; template <typename T, typename U> std::vector<U> factorial<T, U>::_fac_inv{ 1 }; } // namespace suisen #line 8 "library/polynomial/shift_of_sampling_points.hpp" namespace suisen { template <typename mint, typename Convolve, std::enable_if_t<std::is_invocable_r_v<std::vector<mint>, Convolve, std::vector<mint>, std::vector<mint>>, std::nullptr_t> = nullptr> std::vector<mint> shift_of_sampling_points(const std::vector<mint>& ys, mint t, int m, const Convolve &convolve) { const int n = ys.size(); factorial<mint> fac(std::max(n, m)); std::vector<mint> b = [&] { std::vector<mint> f(n), g(n); for (int i = 0; i < n; ++i) { f[i] = ys[i] * fac.fac_inv(i); g[i] = (i & 1 ? -1 : 1) * fac.fac_inv(i); } std::vector<mint> b = convolve(f, g); b.resize(n); return b; }(); std::vector<mint> e = [&] { std::vector<mint> c(n); mint prd = 1; std::reverse(b.begin(), b.end()); for (int i = 0; i < n; ++i) { b[i] *= fac.fac(n - i - 1); c[i] = prd * fac.fac_inv(i); prd *= t - i; } std::vector<mint> e = convolve(b, c); e.resize(n); return e; }(); std::reverse(e.begin(), e.end()); for (int i = 0; i < n; ++i) { e[i] *= fac.fac_inv(i); } std::vector<mint> f(m); for (int i = 0; i < m; ++i) f[i] = fac.fac_inv(i); std::vector<mint> res = convolve(e, f); res.resize(m); for (int i = 0; i < m; ++i) res[i] *= fac.fac(i); return res; } template <typename mint> std::vector<mint> shift_of_sampling_points(const std::vector<mint>& ys, mint t, int m) { auto convolve = [&](const std::vector<mint> &f, const std::vector<mint> &g) { return atcoder::convolution(f, g); }; return shift_of_sampling_points(ys, t, m, convolve); } } // namespace suisen #line 6 "test/src/polynomial/shift_of_sampling_points/shift_of_sampling_points_of_polynomial.test.cpp" int main() { using mint = atcoder::modint998244353; std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m, c; std::cin >> n >> m >> c; std::vector<mint> ys(n); for (int i = 0, v; i < n; ++i) std::cin >> v, ys[i] = v; std::vector<mint> ans = suisen::shift_of_sampling_points<mint>(ys, c, m); for (int i = 0; i < m; ++i) { std::cout << ans[i].val(); if (i + 1 != m) std::cout << ' '; } std::cout << '\n'; return 0; }