Submit Info #3078

Problem Lang User Status Time Memory
Convolution cpp risujiroh AC 130 ms 16.84 MiB

ケース詳細
Name Status Time Memory
example_00 AC 5 ms 0.63 MiB
example_01 AC 6 ms 0.66 MiB
fft_killer_00 AC 130 ms 16.76 MiB
fft_killer_01 AC 128 ms 16.84 MiB
max_random_00 AC 129 ms 16.77 MiB
max_random_01 AC 130 ms 16.84 MiB
medium_00 AC 8 ms 0.88 MiB
medium_01 AC 7 ms 0.77 MiB
medium_02 AC 7 ms 0.85 MiB
random_00 AC 114 ms 13.97 MiB
random_01 AC 120 ms 14.66 MiB
random_02 AC 63 ms 8.29 MiB
small_00 AC 5 ms 0.62 MiB
small_01 AC 6 ms 0.57 MiB
small_02 AC 7 ms 0.62 MiB
small_03 AC 5 ms 0.55 MiB
small_04 AC 6 ms 0.55 MiB
small_05 AC 6 ms 0.62 MiB
small_06 AC 4 ms 0.63 MiB
small_07 AC 6 ms 0.59 MiB
small_08 AC 4 ms 0.63 MiB
small_09 AC 6 ms 0.62 MiB
small_10 AC 4 ms 0.63 MiB
small_11 AC 7 ms 0.62 MiB
small_12 AC 6 ms 0.62 MiB
small_13 AC 5 ms 0.64 MiB
small_14 AC 5 ms 0.62 MiB
small_15 AC 6 ms 0.55 MiB

#include <bits/stdc++.h> using namespace std; #ifdef __linux__ #define getchar getchar_unlocked #define putchar putchar_unlocked #endif template <class Z> Z getint() { char c = getchar(); bool neg = c == '-'; Z res = neg ? 0 : c - '0'; while (isdigit(c = getchar())) res = res * 10 + (c - '0'); return neg ? -res : res; } template <class Z> void putint(Z a, char c = '\n') { if (a < 0) putchar('-'), a = -a; int d[40], i = 0; do d[i++] = a % 10; while (a /= 10); while (i--) putchar('0' + d[i]); putchar(c); } template <class T, class F = multiplies<T>> T power(T a, long long n, F op = multiplies<T>(), T e = {1}) { assert(n >= 0); T res = e; while (n) { if (n & 1) res = op(res, a); if (n >>= 1) a = op(a, a); } return res; } template <unsigned Mod> struct Modular { using M = Modular; unsigned v; Modular(long long a = 0) : v((a %= Mod) < 0 ? a + Mod : a) {} M operator-() const { return M() -= *this; } M& operator+=(M r) { if ((v += r.v) >= Mod) v -= Mod; return *this; } M& operator-=(M r) { if ((v += Mod - r.v) >= Mod) v -= Mod; return *this; } M& operator*=(M r) { v = (uint64_t)v * r.v % Mod; return *this; } M& operator/=(M r) { return *this *= power(r, Mod - 2); } friend M operator+(M l, M r) { return l += r; } friend M operator-(M l, M r) { return l -= r; } friend M operator*(M l, M r) { return l *= r; } friend M operator/(M l, M r) { return l /= r; } friend bool operator==(M l, M r) { return l.v == r.v; } }; template <unsigned Mod> void ntt(vector<Modular<Mod>>& a, bool inverse) { static vector<Modular<Mod>> dw(30), idw(30); if (dw[0] == 0) { Modular<Mod> root = 2; while (power(root, (Mod - 1) / 2) == 1) root += 1; for (int i = 0; i < 30; ++i) dw[i] = -power(root, (Mod - 1) >> (i + 2)), idw[i] = 1 / dw[i]; } int n = a.size(); assert((n & (n - 1)) == 0); if (not inverse) { for (int m = n; m >>= 1; ) { Modular<Mod> w = 1; for (int s = 0, k = 0; s < n; s += 2 * m) { for (int i = s, j = s + m; i < s + m; ++i, ++j) { auto x = a[i], y = a[j] * w; if (x.v >= Mod) x.v -= Mod; a[i].v = x.v + y.v, a[j].v = x.v + (Mod - y.v); } w *= dw[__builtin_ctz(++k)]; } } } else { for (int m = 1; m < n; m *= 2) { Modular<Mod> w = 1; for (int s = 0, k = 0; s < n; s += 2 * m) { for (int i = s, j = s + m; i < s + m; ++i, ++j) { auto x = a[i], y = a[j]; a[i] = x + y, a[j].v = x.v + (Mod - y.v), a[j] *= w; } w *= idw[__builtin_ctz(++k)]; } } auto inv = 1 / Modular<Mod>(n); for (auto&& e : a) e *= inv; } } template <unsigned Mod> vector<Modular<Mod>> operator*(vector<Modular<Mod>> l, vector<Modular<Mod>> r) { if (l.empty() or r.empty()) return {}; int n = l.size(), m = r.size(), sz = 1 << __lg(2 * (n + m - 1) - 1); if (min(n, m) < 30) { vector<long long> res(n + m - 1); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) res[i + j] += (l[i] * r[j]).v; return {begin(res), end(res)}; } bool eq = l == r; l.resize(sz), ntt(l, false); if (eq) r = l; else r.resize(sz), ntt(r, false); for (int i = 0; i < sz; ++i) l[i] *= r[i]; ntt(l, true), l.resize(n + m - 1); return l; } constexpr long long mod = 998244353; using Mint = Modular<mod>; int main() { int n = getint<int>(); int m = getint<int>(); vector<Mint> a(n), b(m); for_each(begin(a), end(a), [](Mint& e) { e.v = getint<int>(); }); for_each(begin(b), end(b), [](Mint& e) { e.v = getint<int>(); }); a = a * b; for (int i = 0; i < n + m - 1; ++i) { putint(a[i].v, " \n"[i == n + m - 2]); } }