Submit Info #65167

Problem Lang User Status Time Memory
Multipoint Evaluation cpp (anonymous) AC 2759 ms 72.51 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.45 MiB
example_01 AC 1 ms 0.45 MiB
max_random_00 AC 2751 ms 72.50 MiB
max_random_01 AC 2759 ms 72.51 MiB
random_00 AC 763 ms 30.97 MiB
random_01 AC 660 ms 22.82 MiB
random_02 AC 2528 ms 65.95 MiB
zero_00 AC 1 ms 0.45 MiB

#pragma GCC optimize("O3", "unroll-loops") #pragma GCC target("sse4.2") #include <bits/stdc++.h> using namespace std; #define int long long #define ll long long const long long mod = 998244353; struct zet { int val; explicit operator int() const { return val; } zet(ll x = 0) { val = (x >= -mod && x < mod ? x : x % mod); if (val < 0) val += mod; } zet(ll a, ll b) { *this += a; *this /= b; } zet& operator+=(zet const &b) { val += b.val; if (val >= mod) val -= mod; return *this; } zet& operator-=(zet const &b) { val -= b.val; if (val < 0) val += mod; return *this; } zet& operator*=(zet const &b) { val = (val * (ll)b.val) % mod; return *this; } friend zet mypow(zet a, ll n) { zet res = 1; while (n) { if (n & 1) res *= a; a *= a; n >>= 1; } return res; } friend zet inv(zet a) { return mypow(a, mod - 2); } zet& operator/=(zet const& b) { return *this *= inv(b); } friend zet operator+(zet a, const zet &b) { return a += b; } friend zet operator-(zet a, const zet &b) { return a -= b; } friend zet operator-(zet a) { return 0 - a; } friend zet operator*(zet a, const zet &b) { return a *= b; } friend zet operator/(zet a, const zet &b) { return a /= b; } friend istream& operator>>(istream& stream, zet &a) { return stream >> a.val; } friend ostream& operator<<(ostream& stream, const zet &a) { return stream << a.val; } friend bool operator==(zet const &a, zet const &b) { return a.val == b.val; } friend bool operator!=(zet const &a, zet const &b) { return a.val != b.val; } friend bool operator<(zet const &a, zet const &b) { return a.val < b.val; } }; template<int md, int maxpw = 23> struct NTT { int mul(int a, int b) { return a * (ll)b % md; } int sum(int a, int b) { a += b; if (a >= md) a -= md; return a; } int diff(int a, int b) { a -= b; if (a < 0) a += md; return a; } int mpow(int a, int n) { int ans = 1; for (; n > 0; n >>= 1, a = mul(a, a)) if (n & 1) ans = mul(ans, a); return ans; } int inv(int a) { return mpow(a, md - 2); } int div(int a, int b) { return a * (ll)inv(b) % md; } int lst(int n) const { return 31 - __builtin_clz(n); } vector<int> sq; NTT() { int rt = 2; while (mpow(rt, 1 << maxpw) != 1 || mpow(rt, 1 << maxpw - 1) == 1) ++rt; sq = vector<int>(maxpw + 1); sq[maxpw] = rt; for (int i = maxpw - 1; i >= 0; --i) sq[i] = mul(sq[i + 1], sq[i + 1]); } vector<int> ind; void dft(vector<int> &a, int n) { int LOG = lst(n); if (ind.size() != n) { ind.resize(n); for (int i = 1; i < n; ++i) { int l = lst(i); ind[i] = ind[i ^ (1 << l)] | (1 << LOG - 1 - l); } } vector<int> cp(n); for (int i = 0; i < n; ++i) cp[i] = a[ind[i]]; swap(a, cp); for (int len = 2; len <= n; len *= 2) { int w = sq[lst(len)]; int l2 = len >> 1, msk = l2 - 1; for (int i = 0; i < n; i += len) { int c = 1; for (int j = 0; j < l2; ++j) { int x = a[i + j], y = mul(a[i + l2 + j], c); a[i + j] = sum(x, y); a[i + j + l2] = diff(x, y); c = mul(c, w); } } } } vector<int> multiply(vector<int> a, vector<int> b) { int n = 1; while (n < a.size() || n < b.size()) n *= 2; n *= 2; a.resize(n); b.resize(n); dft(a, n); dft(b, n); vector<int> ans(n); for (int i = 0; i < n; ++i) ans[i] = mul(a[i], b[i]); dft(ans, n); reverse(ans.begin() + 1, ans.end()); int inv = mpow(n, md - 2); for (auto &i : ans) i = mul(i, inv); return ans; } vector<zet> multiply(vector<zet> _a, vector<zet> _b) { vector<int> a, b; for (int i = 0; i < _a.size(); ++i) a.push_back((int)(_a[i])); for (int i = 0; i < _b.size(); ++i) b.push_back((int)(_b[i])); int n = 1; while (n < a.size() || n < b.size()) n *= 2; n *= 2; a.resize(n); b.resize(n); dft(a, n); dft(b, n); vector<int> ans(n); for (int i = 0; i < n; ++i) ans[i] = mul(a[i], b[i]); dft(ans, n); reverse(ans.begin() + 1, ans.end()); int inv = mpow(n, md - 2); for (auto &i : ans) i = mul(i, inv); vector<zet> _ans; for (int i = 0; i < ans.size(); ++i) _ans.push_back(zet(ans[i])); return _ans; } }; using Poly = vector<zet>; zet get(const Poly & a, int i) { return (i < a.size() ? a[i] : 0); } Poly add(const Poly & a, const Poly & b) { Poly res(max(a.size(), b.size())); for (int i = 0; i < res.size(); ++i) res[i] = get(a, i) + get(b, i); return res; } Poly sub(const Poly & a, const Poly & b) { Poly res(max(a.size(), b.size())); for (int i = 0; i < res.size(); ++i) res[i] = get(a, i) - get(b, i); return res; } NTT<998244353> ntt; Poly mul(const Poly & a, const Poly & b) { return ntt.multiply(a, b); } Poly mul(const Poly & a, zet b) { Poly res(a.size()); for (int i = 0; i < res.size(); ++i) res[i] = get(a, i) * b; return res; } Poly operator+(const Poly & a, const Poly & b) { return add(a, b); } Poly operator-(const Poly & a, const Poly & b) { return sub(a, b); } Poly operator*(const Poly & a, const Poly & b) { return mul(a, b); } Poly operator*(const Poly & a, int b) { return mul(a, zet(b)); } Poly operator*(const Poly & a, zet b) { return mul(a, b); } Poly top(const Poly & a, int n) { return {a.begin(), a.begin() + min((int)a.size(), n)}; } Poly reverse(const Poly & a) { Poly res = a; reverse(res.begin(), res.end()); return res; } Poly shrink(const Poly & a) { Poly res = a; while (res[res.size() - 1] == zet(0)) res.pop_back(); return res; } Poly inv(const Poly & a, int m) { Poly res = {1 / get(a, 0)}; for (int i = 1; i < m; i *= 2) { res = top(res * 2 - res * res * top(a, 2 * i), 2 * i); } return top(res, m); } pair<Poly, Poly> div(const Poly & a, const Poly & b) { if (a.size() < b.size()) return {{0}, a}; int n = a.size() - b.size() + 1; Poly Q = shrink(reverse(top(top(reverse(a), n) * inv(shrink(reverse(b)), n), n))); Poly R = shrink(a - b * Q); // for (auto i : Q) // cout << i << ' '; // cout << endl; // for (auto i : R) // cout << i << ' '; // cout << endl; if (R.size() == 0) R.push_back(0); return {Q, R}; } vector<zet> pts; vector<Poly> tree; vector<zet> ans; void dfs1(int v, int L, int R) { if (L >= R) { return; } else if (L + 1 == R) { tree[v] = {-pts[L], 1}; } else { int M = (L + R) / 2; dfs1(2 * v + 1, L, M); dfs1(2 * v + 2, M, R); tree[v] = shrink(tree[2 * v + 1] * tree[2 * v + 2]); } } void dfs2(int v, int L, int R, Poly f) { if (L >= R) { return; } else if (L + 1 == R) { f = div(f, tree[v]).second; ans.push_back(f[0]); // cout << ans.size() << "/131072\r"; } else { f = div(f, tree[v]).second; int M = (L + R) / 2; dfs2(2 * v + 1, L, M, f); dfs2(2 * v + 2, M, R, f); } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); Poly A = {1, 2, 3, 4, 5, 6, 7, 8}; Poly B = {1, 2, 3, 4}; int n, m; cin >> n >> m; Poly f; f.resize(n); pts.resize(m); for (int i = 0; i < n; ++i) cin >> f[i]; for (int i = 0; i < m; ++i) cin >> pts[i]; int mm = 1; while (mm < m) mm <<= 1; int old_m = m; m = mm; pts.resize(m); tree.resize(4 * mm); dfs1(0, 0, mm); dfs2(0, 0, mm, f); for (int i = 0; i < old_m; ++i) cout << ans[i] << ' '; cout << endl; }