Submit Info #3047

Problem Lang User Status Time Memory
Convolution cpp ei1333 AC 279 ms 30.89 MiB

ケース詳細
Name Status Time Memory
example_00 AC 4 ms 0.62 MiB
example_01 AC 5 ms 0.64 MiB
fft_killer_00 AC 279 ms 30.86 MiB
fft_killer_01 AC 264 ms 30.86 MiB
max_random_00 AC 264 ms 30.89 MiB
max_random_01 AC 266 ms 30.87 MiB
medium_00 AC 9 ms 1.12 MiB
medium_01 AC 8 ms 0.92 MiB
medium_02 AC 8 ms 1.09 MiB
random_00 AC 226 ms 27.56 MiB
random_01 AC 241 ms 28.53 MiB
random_02 AC 125 ms 14.51 MiB
small_00 AC 6 ms 0.68 MiB
small_01 AC 4 ms 0.63 MiB
small_02 AC 6 ms 0.55 MiB
small_03 AC 6 ms 0.62 MiB
small_04 AC 6 ms 0.59 MiB
small_05 AC 5 ms 0.68 MiB
small_06 AC 6 ms 0.54 MiB
small_07 AC 7 ms 0.59 MiB
small_08 AC 5 ms 0.64 MiB
small_09 AC 4 ms 0.63 MiB
small_10 AC 5 ms 0.54 MiB
small_11 AC 6 ms 0.59 MiB
small_12 AC 4 ms 0.63 MiB
small_13 AC 5 ms 0.66 MiB
small_14 AC 8 ms 0.67 MiB
small_15 AC 7 ms 0.64 MiB

#include <bits/stdc++.h> using namespace std; using int64 = long long; //const int mod = 1e9 + 7; const int mod = 998244353; const int64 infll = (1LL << 62) - 1; const int inf = (1 << 30) - 1; struct IoSetup { IoSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } } iosetup; template< typename T1, typename T2 > ostream &operator<<(ostream &os, const pair< T1, T2 > &p) { os << p.first << " " << p.second; return os; } template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; } template< typename T > ostream &operator<<(ostream &os, const vector< T > &v) { for(int i = 0; i < (int) v.size(); i++) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } template< typename T > istream &operator>>(istream &is, vector< T > &v) { for(T &in : v) is >> in; return is; } template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } template< typename T = int64 > vector< T > make_v(size_t a) { return vector< T >(a); } template< typename T, typename... Ts > auto make_v(size_t a, Ts... ts) { return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...)); } template< typename T, typename V > typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) { t = v; } template< typename T, typename V > typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) { for(auto &e : t) fill_v(e, v); } template< typename F > struct FixPoint : F { FixPoint(F &&f) : F(forward< F >(f)) {} template< typename... Args > decltype(auto) operator()(Args &&... args) const { return F::operator()(*this, forward< Args >(args)...); } }; template< typename F > inline decltype(auto) MFP(F &&f) { return FixPoint< F >{forward< F >(f)}; } static constexpr uint32_t mul_inv(uint32_t n, int e = 5, uint32_t x = 1) { return e == 0 ? x : mul_inv(n, e - 1, x * (2 - x * n)); } template< uint32_t mod, bool fast = false > struct ModInt { using u32 = uint32_t; using u64 = uint64_t; static constexpr u32 inv = mul_inv(mod); static constexpr u32 r2 = -uint64_t(mod) % mod; uint32_t x; ModInt() : x(0) {} ModInt(const int64_t &y) : x(reduce(u64(fast ? y : (y >= 0 ? y % mod : (mod - (-y) % mod) % mod)) * r2)) {} u32 reduce(const u64 &w) const { return u32(w >> 32) + mod - u32((u64(u32(w) * inv) * mod) >> 32); } ModInt &operator+=(const ModInt &p) { if(int(x += p.x - 2 * mod) < 0) x += 2 * mod; return *this; } ModInt &operator-=(const ModInt &p) { if(int(x -= p.x) < 0) x += 2 * mod; return *this; } ModInt &operator*=(const ModInt &p) { x = reduce(uint64_t(x) * p.x); return *this; } ModInt &operator/=(const ModInt &p) { *this *= p.inverse(); return *this; } ModInt operator-() const { return ModInt() - *this; } ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; } ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; } ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; } ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; } bool operator==(const ModInt &p) const { return get() == p.get(); } bool operator!=(const ModInt &p) const { return get() != p.get(); } int get() const { return reduce(x) % mod; } ModInt pow(int64_t n) const { ModInt ret(1), mul(*this); while(n > 0) { if(n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } ModInt inverse() const { return pow(mod - 2); } friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.get(); } friend istream &operator>>(istream &is, ModInt &a) { int64_t t; is >> t; a = ModInt< mod, fast >(t); return (is); } static int get_mod() { return mod; } }; using modint = ModInt< mod, false >; template< typename Mint > struct NumberTheoreticTransformFriendlyModInt { vector< int > rev; vector< Mint > rts; int base, max_base; Mint root; NumberTheoreticTransformFriendlyModInt() : base(1), rev{0, 1}, rts{0, 1} { const int mod = Mint::get_mod(); assert(mod >= 3 && mod % 2 == 1); auto tmp = mod - 1; max_base = 0; while(tmp % 2 == 0) tmp >>= 1, max_base++; root = 2; while(root.pow((mod - 1) >> 1) == 1) root += 1; assert(root.pow(mod - 1) == 1); root = root.pow((mod - 1) >> max_base); } void ensure_base(int nbase) { if(nbase <= base) return; rev.resize(1 << nbase); rts.resize(1 << nbase); for(int i = 0; i < (1 << nbase); i++) { rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1)); } assert(nbase <= max_base); while(base < nbase) { Mint z = root.pow(1 << (max_base - 1 - base)); for(int i = 1 << (base - 1); i < (1 << base); i++) { rts[i << 1] = rts[i]; rts[(i << 1) + 1] = rts[i] * z; } ++base; } } void ntt(vector< Mint > &a) { const int n = (int) a.size(); assert((n & (n - 1)) == 0); int zeros = __builtin_ctz(n); ensure_base(zeros); int shift = base - zeros; for(int i = 0; i < n; i++) { if(i < (rev[i] >> shift)) { swap(a[i], a[rev[i] >> shift]); } } for(int k = 1; k < n; k <<= 1) { for(int i = 0; i < n; i += 2 * k) { for(int j = 0; j < k; j++) { Mint z = a[i + j + k] * rts[j + k]; a[i + j + k] = a[i + j] - z; a[i + j] = a[i + j] + z; } } } } void intt(vector< Mint > &a) { const int n = (int) a.size(); ntt(a); reverse(a.begin() + 1, a.end()); Mint inv_sz = Mint(1) / n; for(int i = 0; i < n; i++) a[i] *= inv_sz; } vector< Mint > multiply(vector< Mint > a, vector< Mint > b) { int need = a.size() + b.size() - 1; int nbase = 1; while((1 << nbase) < need) nbase++; ensure_base(nbase); int sz = 1 << nbase; a.resize(sz, 0); b.resize(sz, 0); ntt(a); ntt(b); Mint inv_sz = Mint(1) / sz; for(int i = 0; i < sz; i++) { a[i] *= b[i] * inv_sz; } reverse(a.begin() + 1, a.end()); ntt(a); a.resize(need); return a; } }; int main() { int N, M; cin >> N >> M; vector< modint > A(N), B(M); cin >> A >> B; NumberTheoreticTransformFriendlyModInt< modint > ntt; cout << ntt.multiply(A, B) << endl; }