Submit Info #57975

Problem Lang User Status Time Memory
Multipoint Evaluation cpp-acl Ebishu AC 892 ms 43.92 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.45 MiB
example_01 AC 1 ms 0.42 MiB
max_random_00 AC 892 ms 43.89 MiB
max_random_01 AC 888 ms 43.92 MiB
random_00 AC 208 ms 12.79 MiB
random_01 AC 189 ms 10.77 MiB
random_02 AC 758 ms 41.46 MiB

#include <algorithm> #include <array> #include <bitset> #include <cassert> #include <climits> #include <cmath> #include <complex> #include <cstring> #include <deque> #include <functional> #include <iostream> #include <map> #include <numeric> #include <optional> #include <queue> #include <random> #include <set> #include <stack> #include <string> #include <tuple> #include <unordered_map> #include <unordered_set> #include <vector> using namespace std; using lint = long long; using P = pair<lint, lint>; #define rep(i, n) for (lint i = 0; i < (lint)(n); ++i) #define repe(i, n) for(lint i = 0; i <= (lint)(n); ++i) #define rep1(i, n) for (lint i = 1; i < (lint)(n); ++i) #define repn(i, a, b) for(lint i = (a); i < (lint)(b); ++i) #define rep_inv(i, n) for (lint i = (n); i >= 0; --i) #define all(vec) (vec).begin(), (vec).end() constexpr long long Mod = /** 1000'000'007LL /*/ 998244353LL /**/; constexpr long long Inf = 1'000'000'000'000'000'010LL; constexpr int IntInf = 1000'000'010; constexpr double Pi = 3.141592653589793238; constexpr double InvPi = 0.318309886183790671; const int di[4] = { 0,1,0,-1 }, dj[4] = { 1,0,-1,0 }; #if __has_include(<atcoder/all>) #include <atcoder/all> using namespace atcoder; using mint = static_modint<Mod>; inline istream& operator>>(istream& is, mint& rhs) { long long tmp; is >> tmp; rhs = tmp; return is; } inline ostream& operator<<(ostream& os, const mint& rhs) { return os << rhs.val(); } mint lagrange_interpolation(const vector<mint>& y, mint t) { const int n = (int)y.size(); mint res = 0; vector<mint> inv(n), fact_inv(n); inv[1] = 1; fact_inv[0] = 1; fact_inv[1] = 1; for (int i = 2; i < n; ++i) { inv[i] = -Mod / i * inv[Mod % i]; fact_inv[i] = fact_inv[i - 1] * inv[i]; } vector<mint> prod2(n); prod2.back() = 1; for (int i = n - 1; i > 0; --i) { prod2[i - 1] = (t - i) * prod2[i]; } mint prod1 = 1; for (int i = 0; i < n; ++i) { mint a = y[i]; a *= fact_inv[i] * fact_inv[n - 1 - i]; if ((n - 1 - i) & 1) a = -a; res += a * prod1 * prod2[i]; prod1 *= (t - i); } return res; } template<typename T> lint inversion_number(const vector<T> vec) { vector<T> v = vec; sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); const int n = vec.size(); lint res = 0; fenwick_tree<int> b(n); for (int i = 0; i < n; ++i) { const int j = lower_bound(v.begin(), v.end(), vec[i]) - v.begin(); res += i - b.sum(0, j); b.add(j, 1); } return res; } #endif template<typename T> using prique = priority_queue<T>; template<typename T> using prique_inv = priority_queue<T, vector<T>, greater<T>>; template<typename T> inline istream& operator>>(istream& is, vector<T>& v) { for (auto&& e : v) is >> e; return is; } template<typename T> inline istream& operator>>(istream& is, complex<T>& c) { double real, imag; is >> real >> imag; c.real(real); c.imag(imag); return is; } template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { size_t i = 0, n = v.size(); for (const auto& e : v) { os << e; if (++i < n) os << " "; } return os; } template<typename T, typename U> inline bool chmin(T& a, const U b) { return a > b ? a = b, true : false; } template<typename T, typename U> inline bool chmax(T& a, const U b) { return a < b ? a = b, true : false; } template<typename T, typename U> inline istream& operator>>(istream& is, pair<T, U>& rhs) { return is >> rhs.first >> rhs.second; } template<typename T, typename U> inline ostream& operator<<(ostream& os, const pair<T, U>& rhs) { return os << "{" << rhs.first << ", " << rhs.second << "}"; } template<typename T> T gcd(const vector<T>& vec) { T res = vec.front(); for (T e : vec) { res = gcd(res, e); if (res == 1) return 1; } return res; } template<typename T> T gcd(initializer_list<T> init) { auto first = init.begin(), last = init.end(); T res = *(first++); for (auto itr = first; itr != last; ++itr) { res = gcd(res, *itr); if (res == 1) return 1; } return res; } template<typename T> T lcm(const vector<T>& vec) { T res = vec.front(); for (T e : vec) res = lcm(res, e); return res; } template<typename T> T lcm(initializer_list<T> init) { auto first = init.begin(), last = init.end(); T res = *(first++); for (auto itr = first; itr != last; ++itr) { res = lcm(res, *itr); } return res; } template<typename T> T pow(T x, lint n) { T res = 1; while (n > 0) { if (n & 1) res *= x; x *= x; n >>= 1; } return res; } void out() {} template<typename T> void out(T x) { cout << x << endl; } template<typename T, typename... Args> void out(T x, Args... xs) { cout << x << ", "; out(xs...); } bool is_prime(lint x) { for (lint i = 2; i * i <= x; ++i) { if (x % i == 0) return false; } return 1 < x; } vector<lint> divisors(lint n) { vector<lint> res; for (lint x = 1; x * x <= n; ++x) { if (n % x == 0) { res.push_back(x); if (x * x != n) res.push_back(n / x); } } return res; } lint floor_sqrt(lint n) { lint l = 0, r = 3000'000'000LL; while (r - l > 1) { lint mid = (l + r) / 2; (mid * mid <= n ? l : r) = mid; } return l; } lint ceil_sqrt(lint n) { lint l = 0, r = 3000'000'000LL; while (r - l > 1) { lint mid = (l + r) / 2; (mid * mid < n ? l : r) = mid; } return r; } template<typename T> constexpr bool is_intersect(T l1, T r1, T l2, T r2) { return l1 <= r2 && r1 >= l2; } vector<lint> fact, fact_inv; void fact_init(lint n, lint m = Mod) { fact.resize(n + 1); fact_inv.resize(n + 1); vector<lint> inv(n + 1); inv[1] = 1; fact[0] = fact[1] = 1; fact_inv[0] = 1; for (lint i = 2; i <= n; ++i) { fact[i] = i * fact[i - 1] % m; inv[i] = m - m / i * inv[m % i] % m; } for (lint i = 1; i <= n; ++i) { fact_inv[i] = fact_inv[i - 1] * inv[i] % m; } } lint modinv(lint a, lint m = Mod) { lint b = m, u = 1, v = 0; while (b != 0) { lint t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; if (u < 0) u += m; return u; } lint modpow(lint x, lint n, lint m = Mod) { if (m == 1) return 0; lint res = 1; x %= m; while (n > 0) { if (n & 1) res = res * x % m; x = x * x % m; n >>= 1; } return res; } lint intpow(lint x, lint n) { lint res = 1; while (n > 0) { if (n & 1) res *= x; x *= x; n >>= 1; } return res; } lint comb(lint n, lint r) { if (n < 0 || r < 0 || n < r) return 0; if (r == 0 || r == n) return 1; return fact[n] * fact_inv[n - r] % Mod * fact_inv[r] % Mod; } lint perm(lint n, lint r) { if (n < 0 || r < 0 || n < r) return 0; return fact[n] * fact_inv[n - r] % Mod; } template<typename T = int> vector<T> as_vector(const string& str) { const size_t n = str.size(); vector<T> res(n); T* p_res = res.data(); const char* p_str = str.data(); for (size_t i = 0; i < n; ++i) { *p_res++ = T(*p_str++ - '0'); } return res; } template<typename T> vector<T> compressed(vector<T> v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); return v; } // { 値, 個数 } template<typename T> pair<vector<T>, vector<int>> compressed_pair(vector<T> v) { size_t n = v.size(); sort(all(v)); vector<T> cnt, val; cnt.reserve(n); val.reserve(n); int now_cnt = 1; for (size_t i = 1; i < n; ++i) { if (v[i - 1] != v[i]) { cnt.push_back(now_cnt); val.push_back(v[i - 1]); now_cnt = 1; } else ++now_cnt; } cnt.push_back(now_cnt); val.push_back(v.back()); return { val, cnt }; } class Factring { private: const lint max_n; vector<lint> sieve; public: explicit Factring(lint max_n) noexcept : max_n{ max_n } , sieve{ max_n } { iota(sieve.begin(), sieve.end(), 0); for (lint i = 2; i * i < max_n; ++i) { if (sieve[i] < i) continue; for (lint j = i * i; j < max_n; j += i) { if (sieve[j] == j) sieve[j] = i; } } } unordered_map<lint, lint> calc(lint x) const noexcept { unordered_map<lint, lint> res; while (x > 1) { ++res[sieve[x]]; x /= sieve[x]; } return res; } }; struct UnionFind { const int n; vector<int> par, rank, siz, es; explicit UnionFind(int _n) noexcept : n(_n) , par(n) , rank(n) , siz(n, 1) , es(n) { iota(par.begin(), par.end(), 0); } int root(int x) noexcept { if (par[x] == x) return x; return par[x] = root(par[x]); } bool same(int x, int y) noexcept { return root(x) == root(y); } void unite(int x, int y) noexcept { x = root(x); y = root(y); if (x == y) ++es[x]; else if (rank[x] < rank[y]) { par[x] = y; siz[y] += siz[x]; es[y] += es[x] + 1; } else { par[y] = x; if (rank[x] == rank[y]) ++rank[x]; siz[x] += siz[y]; es[x] += es[y] + 1; } } int count(int x) noexcept { return siz[root(x)]; } vector<vector<int>> groups() noexcept { vector<int> roots(n), group_size(n); for (int i = 0; i < n; ++i) { roots[i] = root(i); ++group_size[roots[i]]; } vector<vector<int>> res(n); for (int i = 0; i < n; ++i) { res.reserve(group_size[i]); } for (int i = 0; i < n; ++i) { res[roots[i]].push_back(i); } res.erase( remove_if(res.begin(), res.end(), [](const vector<int>& v) { return v.empty(); }), res.end() ); return res; } }; template<typename T> class CumulativeSum { private: const int n; vector<T> dat; public: CumulativeSum() = default; explicit CumulativeSum(const int n) : n(n), dat(n + 1) {} CumulativeSum(const vector<T>& vec) : n(vec.size()) , dat(n + 1) { for (int i = 0; i < n; ++i) dat[i + 1] = vec[i]; } void add(const int i, const T& x) { dat[i + 1] += x; } void build() { for (int i = 0; i < n; ++i) { dat[i + 1] += dat[i]; } } // [l, r) T sum(const int l, const int r) const { return dat[r] - dat[l]; } // [0, a) T sum(const int a) const { return dat[a]; } }; template<typename T> class CumulativeSum2D { private: vector<vector<T>> dat; public: CumulativeSum2D() = default; explicit CumulativeSum2D(size_t n) : dat(n + 1, vector<T>(n + 1)) {} CumulativeSum2D(size_t h, size_t w) : dat(h + 1, vector<T>(w + 1)) {} CumulativeSum2D(const vector<vector<T>>& vec) noexcept { const size_t h = vec.size(), w = vec.front().size(); dat.resize(h + 1, vector<T>(w + 1)); for (size_t i = 0; i < h; ++i) { for (size_t j = 0; j < w; ++j) { dat[i + 1][j + 1] = dat[i][j + 1] + dat[i + 1][j] - dat[i][j] + vec[i][j]; } } } void add(int h, int w, int v) noexcept { dat[h + 1][w + 1] += v; } void build() { const size_t h = dat.size(), w = dat.front().size(); for (size_t i = 0; i < h; ++i) { for (size_t j = 0; j < w; ++j) { dat[i + 1][j + 1] = dat[i][j + 1] + dat[i + 1][j] - dat[i][j]; } } } // [0, h) × [0, w) T sum(int h, int w) const noexcept { return sum(0, 0, h, w); } // [h1, h2) × [w1, w2) T sum(int h1, int w1, int h2, int w2) const noexcept { return dat[h2][w2] - dat[h1][w2] - dat[h2][w1] + dat[h1][w1]; } }; template<typename T> class BinaryIndexedTree { private: const int size; vector<T> dat; public: explicit BinaryIndexedTree(const int size) noexcept : size(size) , dat(size + 1) {} explicit BinaryIndexedTree(const vector<T>& vec) noexcept : size(vec.size()) , dat(size + 1) { for (int i = 0; i < size; ++i) dat[i + 1] = vec[i]; for (int i = 0; i <= size; ++i) { const int j = i + (i & -i); if (j <= size) dat[j] += dat[i]; } } void add(const int a, const T w) noexcept { for (int x = a + 1; x <= size; x += (x & -x)) dat[x] += w; } void set(const int a, const T w) noexcept { add(a, w - dat[a]); } // [0, a) T sum(const int a) const noexcept { T res = 0; for (int x = a; x > 0; x -= x & -x) res += dat[x]; return res; } // [a, b) T sum(const int a, const int b) const noexcept { return sum(b) - sum(a); } const T& operator[](const size_t x) const noexcept { return dat[x + 1]; } }; template<typename T, typename U> T nearest_value(const vector<T>& v, const U& value) { auto itr = lower_bound(v.begin(), v.end(), value); if (itr == v.begin()) return *itr; if (itr == v.end()) return *prev(itr); return min(*itr - value, value - *prev(itr)) + value; } template<typename T> struct FormalPowerSeries : vector<T> { using vector<T>::vector; using vector<T>::operator=; using F = FormalPowerSeries; void shrink() { while (!this->empty() && this->back() == T(0)) this->pop_back(); } F operator+() const noexcept { return *this; } F operator-() const noexcept { F res(*this); for (auto&& e : res) e = -e; return res; } F operator*(const T& k) const noexcept { return F(*this) *= k; } F operator/(const T& k) const { return F(*this) /= k; } F operator+(const F& g) const noexcept { return F(*this) += g; } F operator-(const F& g) const noexcept { return F(*this) -= g; } F operator<<(const int d) const noexcept { return F(*this) <<= d; } F operator>>(const int d) const noexcept { return F(*this) >>= d; } F operator*(const F& g) const { return F(*this) *= g; } F operator/(const F& g) const { return F(*this) /= g; } F operator%(const F& g) const { return F(*this) %= g; } F& operator*=(const T& k) noexcept { for (auto&& e : *this) e *= k; return *this; } F& operator/=(const T& k) { assert(k != T(0)); *this *= k.inv(); return *this; } F& operator+=(const F& g) noexcept { const int n = this->size(), m = g.size(); for (int i = 0; i < min(n, m); ++i) (*this)[i] += g[i]; this->shrink(); return *this; } F& operator-=(const F& g) noexcept { const int n = this->size(), m = g.size(); for (int i = 0; i < min(n, m); ++i) (*this)[i] -= g[i]; this->shrink(); return *this; } F& operator<<=(const int d) { const int n = this->size(); this->insert(this->begin(), d, T(0)); return *this; } F& operator>>=(const int d) { const int n = this->size(); if (n <= d) this->clear(); else this->erase(this->begin(), this->begin() + d); return *this; } F& operator*=(const F& g) { const auto f = atcoder::convolution(std::move(*this), g); return *this = F(f.begin(), f.end()); } F& operator/=(const F& g) { if (this->size() < g.size()) { this->clear(); return *this; } const int n = this->size() - g.size() + 1; return *this = (rev().pre(n) * g.rev().inv(n)).pre(n).rev(n); } F& operator%=(const F& g) { *this -= *this / g * g; this->shrink(); return *this; } T eval(const T& x) const noexcept { T res = this->back(); for (auto itr = ++this->rbegin(), itr_rend = this->rend(); itr != itr_rend; ++itr) { res *= x; res += *itr; } return res; } F pre(int d) const { return F(this->begin(), this->begin() + min((int)this->size(), d)); } F rev(int d = -1) const { F res(*this); if (d != -1) res.resize(d, T(0)); reverse(res.begin(), res.end()); return res; } F inv(int d = -1) const { int n = this->size(); assert(n != 0 && this->front() != T(0)); if (d == -1) d = n; assert(d > 0); F res = { 1 / this->front() }; res.reserve(2 * d); int m = res.size(); while (m < d) { F f(this->begin(), this->begin() + min(n, 2 * m)); F r(res); f.resize(2 * m); r.resize(2 * m); atcoder::internal::butterfly(f); atcoder::internal::butterfly(r); for (int i = 0; i < 2 * m; ++i) f[i] *= r[i]; atcoder::internal::butterfly_inv(f); f.erase(f.begin(), f.begin() + m); f.resize(2 * m); atcoder::internal::butterfly(f); for (int i = 0; i < 2 * m; ++i) f[i] *= r[i]; atcoder::internal::butterfly_inv(f); T iz = T(1) / (2 * m); iz *= -iz; for (int i = 0; i < m; ++i) f[i] *= iz; res.insert(res.end(), f.begin(), f.begin() + m); m <<= 1; } return { res.begin(), res.begin() + d }; } F& multiply_inplace(const F& g, int d = -1) { if (d == -1) d = this->size(); assert(d >= 0); *this = atcoder::convolution(move(*this), g); this->resize(d); return *this; } F multiply(const F& g, int d = -1) const { return F(*this).multiply_inplace(g, d); } F& diff_inplace() noexcept { const int n = this->size(); for (int i = 2; i < n; ++i) (*this)[i] *= i; this->erase(this->begin()); this->push_back(0); return *this; } F diff() const noexcept { return F(*this).diff_inplace(); } F& integral_inplace() noexcept { constexpr int p = T::mod(); const int n = this->size(); vector<T> inv(n); inv[1] = 1; for (int i = 2; i < n; ++i) inv[i] = -inv[p % i] * (p / i); for (int i = n - 1; i > 0; --i) (*this)[i] = (*this)[i - 1] * inv[i]; this->front() = 0; return *this; } F integral() const noexcept { return F(*this).integral_inplace(); } F& log_inplace(int d = -1) { const int n = this->size(); assert(this->front() == 1); if (d == -1) d = n; assert(d >= 0); if (d < n) this->resize(d); const F f_inv = this->inv(); this->diff_inplace().multiply_inplace(f_inv).integral_inplace(); return *this; } F log(int d = -1) const { return F(*this).log_inplace(d); } F& exp_inplace(int d = -1) { const int n = this->size(); assert(this->front() == T(0)); if (d == -1) d = n; assert(d >= 0); F g = { 1 }, g_fft; this->resize(d); this->front() = 1; const F h_diff = this->diff(); for (int m = 1; m < d; m <<= 1) { F f_fft(this->begin(), this->begin() + m); f_fft.resize(2 * m); atcoder::internal::butterfly(f_fft); if (m > 1) { F _f(m); for (int i = 0; i < m; ++i) _f[i] = f_fft[i] * g_fft[i]; atcoder::internal::butterfly_inv(_f); _f.erase(_f.begin(), _f.begin() + m / 2); _f.resize(m); atcoder::internal::butterfly(_f); for (int i = 0; i < m; ++i) _f[i] *= g_fft[i]; atcoder::internal::butterfly_inv(_f); _f.resize(m / 2); _f /= T(-m) * m; g.insert(g.end(), _f.begin(), _f.begin() + m / 2); } F t(this->begin(), this->begin() + m); t.diff_inplace(); { F r(h_diff.begin(), h_diff.begin() + (m - 1)); r.resize(m); atcoder::internal::butterfly(r); for (int i = 0; i < m; ++i) r[i] *= f_fft[i]; atcoder::internal::butterfly_inv(r); r /= -m; t += r; t.insert(t.begin(), t.back()); t.pop_back(); } if (2 * m < d || m == 1) { t.resize(2 * m); atcoder::internal::butterfly(t); g_fft = g; g_fft.resize(2 * m); atcoder::internal::butterfly(g_fft); for (int i = 0; i < 2 * m; ++i) t[i] *= g_fft[i]; atcoder::internal::butterfly_inv(t); t.resize(m); t /= 2 * m; } else { F g1(g.begin() + m / 2, g.end()); F s1(t.begin() + m / 2, t.end()); t.resize(m / 2); g1.resize(m); atcoder::internal::butterfly(g1); t.resize(m); atcoder::internal::butterfly(t); s1.resize(m); atcoder::internal::butterfly(s1); for (int i = 0; i < m; ++i) s1[i] = g_fft[i] * s1[i] + g1[i] * t[i]; for (int i = 0; i < m; ++i) t[i] *= g_fft[i]; atcoder::internal::butterfly_inv(t); atcoder::internal::butterfly_inv(s1); for (int i = 0; i < m / 2; ++i) t[i + m / 2] += s1[i]; t /= m; } F v(this->begin() + m, this->begin() + min(d, 2 * m)); v.resize(m); t.insert(t.begin(), m - 1, 0); t.push_back(0); t.integral_inplace(); for (int i = 0; i < m; ++i) v[i] -= t[m + i]; v.resize(2 * m); atcoder::internal::butterfly(v); for (int i = 0; i < 2 * m; ++i) v[i] *= f_fft[i]; atcoder::internal::butterfly_inv(v); v.resize(m); v /= 2 * m; for (int i = 0; i < min(d - m, m); ++i) (*this)[m + i] = v[i]; } return *this; } F exp(int d = -1) const { return F(*this).exp_inplace(d); } F& pow_inplace(long long m, int d = -1) { const int n = this->size(); if (d == -1) d = n; assert(d >= 0); int k = 0; while (k < n && (*this)[k] == 0) ++k; if (k > d / m) return *this = F(d); const T c_inv = (*this)[k].inv(); const T c_pow = (*this)[k].pow(m); this->erase(this->begin(), this->begin() + k); *this *= c_inv; this->log_inplace(); *this *= m; this->exp_inplace(); *this *= c_pow; this->insert(this->begin(), m * k, T(0)); this->resize(d); return *this; } F pow(long long m, int d = -1) const { return F(*this).pow_inplace(m, d); } vector<T> eval(const vector<T>& x) const { const int m1 = x.size(); int m = 1; while (m < m1) m <<= 1; vector<F> subproducts(2 * m, F{ 1 }); for (int i = m; i < m + m1; ++i) { subproducts[i].resize(2); subproducts[i][0] = -x[i - m]; subproducts[i][1] = 1; } for (int i = m - 1; i > 0; --i) { subproducts[i] = subproducts[i << 1] * subproducts[i << 1 | 1]; } vector<F> rem(2 * m); rem[1] = *this; for (int i = 1; i < m; ++i) { rem[i << 1] = rem[i] % subproducts[i << 1]; rem[i << 1 | 1] = rem[i] % subproducts[i << 1 | 1]; } vector<T> res(m1); for (int i = 0; i < m1; ++i) { res[i] = rem[i + m][0]; } return res; } }; using FPS = FormalPowerSeries<mint>; int main() { int n, m; scanf("%d%d", &n, &m); FPS f(n); for(mint& e : f) { int c; scanf("%d", &c); e = mint::raw(c); } vector<mint> p(m); for (mint& e : p) { int p1; scanf("%d", &p1); e = mint::raw(p1); } const auto& ans = f.eval(p); for(const mint& e : ans) { printf("%u ", e.val()); } }