Submit Info #2995

Problem Lang User Status Time Memory
Inv of Formal Power Series cpp wisteria0410ss WA 1140 ms 80.82 MiB

ケース詳細
Name Status Time Memory
example_00 AC 942 ms 80.75 MiB
max_random_00 WA 1139 ms 80.81 MiB
max_random_01 WA 1136 ms 80.75 MiB
max_random_02 WA 1138 ms 80.77 MiB
max_random_03 WA 1140 ms 80.76 MiB
max_random_04 WA 1139 ms 80.72 MiB
random_00 WA 1104 ms 80.75 MiB
random_01 WA 1132 ms 80.82 MiB
random_02 WA 995 ms 80.82 MiB
random_03 WA 1118 ms 80.71 MiB
random_04 WA 1067 ms 80.75 MiB

#include <bits/stdc++.h> template <uint32_t mod> class modint{ uint64_t value; public: //constexpr modint(const int64_t x=0) noexcept: value(x % mod + (x < 0 ? mod : 0)){ } 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, uint32_t root, size_t K> modint<mod> *convolution(size_t n...){ va_list args; va_start(args, n); modint<mod> *fa, *f; f = new modint<mod>[K]; for(size_t j=0;j<K;++j) f[j] = 1; for(size_t i=0;i<n;++i){ modint<mod> *input = static_cast<modint<mod>*>(va_arg(args, void*)); fa = ntt<mod, root, K>(input); for(size_t j=0;j<K;++j) f[j] *= fa[j]; delete[] fa; } va_end(args); fa = ntt<mod, root, K>(f); f[0] = fa[0] / K; for(size_t j=1;j<K;++j) f[j] = fa[K-j] / K; delete[] fa; return f; } 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; } template <uint32_t mod, uint32_t root, size_t K> class formal_power_series{ static_assert((K & -K) == K, ""); std::vector<modint<mod>> value; template<size_t N> constexpr std::vector<modint<mod>> inv() const noexcept{ if(N == 1){ return { value[0].inverse() }; } std::vector<modint<mod>> ret = inv<N/2?N/2:1>(); ret.resize(2*N); auto p = convolution<mod, root, 2*N>(&ret[0], &value[0]); auto q = convolution<mod, root, 2*N>(&ret[0], p); for(size_t i=0;i<N;++i) ret[i] = ret[i] * 2 - q[i]; delete[] p; delete[] q; return ret; } public: formal_power_series(): value(2*K){ } formal_power_series(const std::vector<modint<mod>> &v): value(v){ value.resize(2*K); } constexpr formal_power_series inverse() const noexcept{ return formal_power_series{inv<K>()}; } constexpr formal_power_series operator+() const noexcept{ return formal_power_series(*this); } constexpr formal_power_series operator-() const noexcept{ auto ret = formal_power_series(*this); for(size_t i=0;i<K;++i) ret.value *= mod - 1; return ret; } constexpr formal_power_series operator+(const formal_power_series &rhs) const noexcept{ return formal_power_series(*this) += rhs; } constexpr formal_power_series operator-(const formal_power_series &rhs) const noexcept{ return formal_power_series(*this) -= rhs; } constexpr formal_power_series operator*(const formal_power_series &rhs) const noexcept{ return formal_power_series(*this) *= rhs; } constexpr formal_power_series operator*(const modint<mod> &rhs) const noexcept{ return formal_power_series(*this) *= rhs; } constexpr formal_power_series operator/(const formal_power_series &rhs) const noexcept{ return formal_power_series(*this) /= rhs; } constexpr formal_power_series &operator+=(const formal_power_series &rhs) noexcept{ for(size_t i=0;i<K;++i) value[i] += rhs.value[i]; return *this; } constexpr formal_power_series &operator-=(const formal_power_series &rhs) noexcept{ for(size_t i=0;i<K;++i) value[i] -= rhs.value[i]; return *this; } constexpr formal_power_series &operator*=(const formal_power_series &rhs) noexcept{ auto p = convolution<mod, root, 2*K>(&value[0], &rhs.value[0]); for(size_t i=0;i<K;++i) value[i] = p[i]; delete[] p; return *this; } constexpr formal_power_series &operator*=(const modint<mod> &rhs) noexcept{ for(size_t i=0;i<K;++i) value[i] *= rhs; return *this; } constexpr formal_power_series &operator/=(const formal_power_series &rhs) noexcept{ return *this *= rhs.inverse(); } constexpr modint<mod> &operator[](size_t i) & noexcept{ return value[i]; } constexpr const modint<mod> &operator[](size_t i) const& noexcept{ return value[i]; } constexpr modint<mod> operator[](size_t i) const&& noexcept{ return value[i]; } }; using namespace std; int main(){ int n; formal_power_series<998244353, 3, 1 << 19> f; cin >> n; for(int i=0;i<n;++i){ int a; cin >> a; f[i] = a; } auto d = f.inverse(); for(size_t i=0;i<n;++i) cout << d[i] << " "; cout << endl; return 0; }