Submit Info #3056

Problem Lang User Status Time Memory
Convolution (mod 1,000,000,007) cpp wisteria0410ss CE -1 ms -1 Mib

ケース詳細
Name Status Time Memory

#pragma GCC optimize("O3") #pragma GCC target("AVX") #include <bits/stdc++.h> void put_u64(uint64_t x){ int digit[25], i = 0; if(x < 0) putchar_unlocked('-'), x = -x; do digit[i++] = x % 10; while(x /= 10); while(i--) putchar_unlocked('0' + digit[i]); } 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<> class modint<1>{ constexpr static uint64_t mod = 0xffffffff00000001ull; uint64_t value; public: constexpr modint(const uint64_t x=0) noexcept: value(x < mod ? x : x - mod){ } constexpr explicit operator uint64_t() const noexcept{ return value; } constexpr modint inverse() const noexcept{ return pow(*this, mod-2); } 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{ unsigned long long ret = 0; if(__builtin_uaddll_overflow(value, rhs.value, &ret)){ if(__builtin_uaddll_overflow(ret, 0xffffffff, &ret)){ value = ret + 0xffffffff; return *this; } } if(ret < mod) value = ret; else value = ret + 0xffffffff; return *this; } constexpr modint &operator-=(const modint &rhs) noexcept{ return *this += mod - rhs.value; } constexpr modint &operator*=(const modint &rhs) noexcept{ uint64_t lh = value >> 32, ll = value & 0xffffffff; uint64_t rh = rhs.value >> 32, rl = rhs.value & 0xffffffff; uint64_t z3 = lh * rh, z2 = lh * rl, z1 = ll * rh, z0 = ll * rl; z3 += (z2 >> 32) + (z1 >> 32); z2 &= 0xffffffff; z2 += (z1 & 0xffffffff) + (z0 >> 32); z3 += z2 >> 32; value *= rhs.value; if(value > mod) value -= mod; *this += (z3 & 0xffffffff) * 0xffffffff; return *this -= z3 >> 32; } friend std::ostream &operator<<(std::ostream &os, const modint<1> &x){ return os << x.value; } friend std::istream &operator>>(std::istream &is, modint<1> &x){ int64_t i; is >> i; x = modint<1>(i); return is; } friend constexpr modint<1> pow(const modint<1> &x, uint64_t y){ modint<1> ret = 1, m = x; while(y > 0){ if(y & 1) ret *= m; m *= m; y >>= 1; } return ret; } }; template<uint64_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"); constexpr uint64_t yp = (mod == 1) ? 0xffffffff00000000ull / K : (mod - 1) / K; static modint<mod> hp[K]; hp[0] = 1; hp[1] = pow(modint<mod>{root}, yp); 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, uint32_t root, size_t K> modint<mod> *convolution(const modint<mod> *lhs, const modint<mod> *rhs){ constexpr modint<mod> Kinv = modint<mod>{K}.inverse(); modint<mod> *flhs, *frhs, *pr; flhs = ntt<mod, root, K>(lhs); frhs = ntt<mod, root, K>(rhs); for(size_t i=0;i<K;++i) flhs[i] *= frhs[i]; pr = ntt<mod, root, K>(flhs); flhs[0] = pr[0] * Kinv; for(size_t i=1;i<K;++i) flhs[i] = pr[K-i] * Kinv; delete[] frhs; delete[] pr; return flhs; } template<uint32_t mod, size_t K> modint<mod> *convolution(const modint<mod> *lhs, const modint<mod> *rhs){ constexpr uint32_t mod0 = 1, mod1 = 3 * (1UL << 30) + 1; constexpr uint32_t root0 = 7, root1 = 5; constexpr modint<mod1> mod0inv = modint<mod1>{0xffffffff00000001ull}.inverse(); constexpr modint<mod> mmod0 = modint<mod>{0xffffffff00000001ull}; static modint<mod0> l0[K], r0[K]; for(size_t i=0;i<K;++i){ l0[i] = (uint64_t)lhs[i]; r0[i] = (uint64_t)rhs[i]; } auto x0 = convolution<mod0, root0, K>(l0, r0); static modint<mod1> l1[K], r1[K]; for(size_t i=0;i<K;++i){ l1[i] = (uint64_t)lhs[i]; r1[i] = (uint64_t)rhs[i]; } auto x1 = convolution<mod1, root1, K>(l1, r1); modint<mod> *x = new modint<mod>[K]; for(size_t i=0;i<K;++i){ modint<mod1> v = (x1[i] - (uint64_t)x0[i]) * mod0inv; x[i] = mmod0 * (uint64_t)v + (uint64_t)x0[i]; } delete[] x0; delete[] x1; return x; } using namespace std; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); constexpr size_t K = 1ull << 20; constexpr uint32_t mod = 1'000'000'007; int 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){ put_u64((uint64_t)c[i]); putchar_unlocked(" \n"[i == n+m-2]); } delete[] c; return 0; }