Submit Info #2994

Problem Lang User Status Time Memory
Convolution (mod 1,000,000,007) cpp wisteria0410ss AC 1505 ms 136.96 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1265 ms 128.89 MiB
example_01 AC 1253 ms 128.90 MiB
fft_killer_00 AC 1505 ms 136.88 MiB
fft_killer_01 AC 1503 ms 136.90 MiB
max_random_00 AC 1504 ms 136.96 MiB
max_random_01 AC 1505 ms 136.90 MiB
medium_00 AC 1314 ms 129.04 MiB
medium_01 AC 1312 ms 128.91 MiB
medium_02 AC 1320 ms 128.92 MiB
random_00 AC 1466 ms 135.05 MiB
random_01 AC 1474 ms 135.54 MiB
random_02 AC 1405 ms 132.16 MiB
small_00 AC 1248 ms 128.91 MiB
small_01 AC 1254 ms 128.93 MiB
small_02 AC 1257 ms 128.91 MiB
small_03 AC 1261 ms 128.95 MiB
small_04 AC 1256 ms 128.93 MiB
small_05 AC 1258 ms 128.91 MiB
small_06 AC 1260 ms 128.95 MiB
small_07 AC 1261 ms 128.89 MiB
small_08 AC 1254 ms 128.86 MiB
small_09 AC 1258 ms 128.89 MiB
small_10 AC 1264 ms 128.91 MiB
small_11 AC 1263 ms 128.94 MiB
small_12 AC 1257 ms 128.93 MiB
small_13 AC 1258 ms 128.89 MiB
small_14 AC 1267 ms 128.95 MiB
small_15 AC 1261 ms 128.91 MiB

#include <bits/stdc++.h> template <uint32_t mod> class modint{ uint64_t value; public: constexpr modint(const uint64_t x=0) noexcept: value(x % mod){ } constexpr explicit operator uint64_t() const noexcept{ return value; } constexpr modint inverse() const noexcept{ return pow(*this, mod-2); } constexpr bool operator==(const modint &rhs) const noexcept{ return value == rhs.value; } constexpr bool operator!=(const modint &rhs) const noexcept{ return value != rhs.value; } constexpr modint operator+() const noexcept{ return modint(*this); } constexpr modint operator-() const noexcept{ return modint(mod - value); } constexpr modint operator+(const modint &rhs) const noexcept{ return modint(*this) += rhs; } constexpr modint operator-(const modint &rhs) const noexcept{ return modint(*this) -= rhs; } constexpr modint operator*(const modint &rhs) const noexcept{ return modint(*this) *= rhs; } constexpr modint operator/(const modint &rhs) const noexcept{ return modint(*this) /= rhs; } constexpr modint &operator+=(const modint &rhs) noexcept{ if((value += rhs.value) >= mod) value -= mod; return *this; } constexpr modint &operator-=(const modint &rhs) noexcept{ return *this += mod - rhs.value; } constexpr modint &operator*=(const modint &rhs) noexcept{ if((value *= rhs.value) >= mod) value %= mod; return *this; } constexpr modint &operator/=(const modint &rhs) noexcept{ return *this *= rhs.inverse(); } constexpr modint operator++(int) noexcept{ modint ret(*this); if((++value) >= mod) value -= mod; return ret; } constexpr modint operator--(int) noexcept{ modint ret(*this); if((value += mod - 1) >= mod) value -= mod; return ret; } constexpr modint &operator++() noexcept{ return *this += 1; } constexpr modint &operator--() noexcept{ return *this -= 1; } friend std::ostream &operator<<(std::ostream &os, const modint<mod> &x){ return os << x.value; } friend std::istream &operator>>(std::istream &is, modint<mod> &x){ int64_t i; is >> i; x = modint<mod>(i); return is; } friend constexpr modint<mod> pow(const modint<mod> &x, uint64_t y){ modint<mod> ret{1}, m{x}; while(y > 0){ if(y & 1) ret *= m; m *= m; y >>= 1; } return ret; } }; template<uint32_t mod, uint32_t root, size_t K> modint<mod> *ntt(const modint<mod> *input){ static_assert((K ^ (K & -K)) == 0 && (mod - 1) % K == 0, "template parameter T must be power of 2"); static modint<mod> hp[K]; hp[0] = 1; hp[1] = pow(modint<mod>(root), (mod - 1) / K); for(size_t i=2;i<K;++i) hp[i] = hp[i-1] * hp[1]; modint<mod> *output[2] = { new modint<mod>[K], new modint<mod>[K] }; std::copy(input, input+K, output[0]); bool f = 0; size_t m = K >> 1; for(size_t s = 1; s < K; s <<= 1){ for(size_t p = 0; p < m; ++p){ for(size_t q = 0; q < s; ++q){ auto a = output[f][q + s * (p + 0)]; auto b = output[f][q + s * (p + m)]; output[!f][q + s * (2 * p + 0)] = a + b; output[!f][q + s * (2 * p + 1)] = (a - b) * hp[s * p % K]; } } f ^= 1; m >>= 1; } delete[] output[!f]; return output[f]; } template<uint32_t mod, size_t K> modint<mod> *hadamard_product(const modint<mod> *lhs, const modint<mod> *rhs){ modint<mod> *p = new modint<mod>[K]; for(size_t i=0;i<K;++i) p[i] = lhs[i] * rhs[i]; return p; } template<uint32_t mod, uint32_t root, size_t K> modint<mod> *convolution(const modint<mod> *lhs, const modint<mod> *rhs){ modint<mod> *flhs, *frhs, *p, *pr; flhs = ntt<mod, root, K>(lhs); frhs = ntt<mod, root, K>(rhs); p = hadamard_product<mod, K>(flhs, frhs); pr = ntt<mod, root, K>(p); p[0] = pr[0] / K; for(size_t i=1;i<K;++i) p[i] = pr[K-i] / K; delete[] flhs; delete[] frhs; delete[] pr; return p; } template<uint32_t mod_out, uint32_t mod_in, uint32_t root, size_t K> modint<mod_out> *convolution(const modint<mod_in> *lhs, const modint<mod_in> *rhs){ static modint<mod_out> l[K], r[K]; for(size_t i=0;i<K;++i){ l[i] = (uint64_t)lhs[i]; r[i] = (uint64_t)rhs[i]; } return convolution<mod_out, root, K>(l, r); } template<uint32_t mod, size_t K> modint<mod> *convolution(const modint<mod> *lhs, const modint<mod> *rhs){ constexpr uint32_t mods[] = { 469762049, 998244353, 3 * (1UL << 30) + 1 }; constexpr uint32_t roots[] = { 3, 3, 5 }; auto x0 = convolution<mods[0], mod, roots[0], K>(lhs, rhs); auto x1 = convolution<mods[1], mod, roots[1], K>(lhs, rhs); auto x2 = convolution<mods[2], mod, roots[2], K>(lhs, rhs); modint<mod> *x = new modint<mod>[K]; for(size_t i=0;i<K;++i){ uint64_t v[3]; v[0] = (uint64_t)x0[i]; v[1] = (uint64_t)((x1[i] - v[0]) / mods[0]); v[2] = (uint64_t)((x2[i] - v[0] - modint<mods[2]>{v[1]}*mods[0]) / mods[0] / mods[1]); x[i] = modint<mod>{v[0]} + modint<mod>{v[1]}*mods[0] + modint<mod>{v[2]}*mods[0]*mods[1]; } delete[] x0; delete[] x1; delete[] x2; return x; } using namespace std; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); constexpr uint32_t mod = 1'000'000'007; constexpr size_t K = 1 << 20; size_t n, m; static modint<mod> a[K], b[K]; cin >> n >> m; for(size_t i=0;i<n;++i) cin >> a[i]; for(size_t i=0;i<m;++i) cin >> b[i]; auto c = convolution<mod, K>(a, b); for(size_t i=0;i<n+m-1;++i) cout << c[i] << " \n"[i==n+m-2]; delete[] c; return 0; }