Submit Info #2675

Problem Lang User Status Time Memory
Exp of Formal Power Series cpp risujiroh AC 3877 ms 226.44 MiB

ケース詳細
Name Status Time Memory
example_00 AC 4 ms 0.63 MiB
max_random_00 AC 3877 ms 226.42 MiB
max_random_01 AC 3876 ms 226.35 MiB
max_random_02 AC 3877 ms 226.43 MiB
max_random_03 AC 3874 ms 226.39 MiB
max_random_04 AC 3870 ms 226.44 MiB
random_00 AC 3834 ms 225.01 MiB
random_01 AC 3855 ms 226.28 MiB
random_02 AC 407 ms 27.73 MiB
random_03 AC 3833 ms 226.16 MiB
random_04 AC 3849 ms 224.57 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> vector<T> operator-(vector<T> a) { for (auto&& e : a) e = -e; return a; } template <class T> vector<T>& operator+=(vector<T>& l, const vector<T>& r) { l.resize(max(l.size(), r.size())); for (int i = 0; i < (int)r.size(); ++i) l[i] += r[i]; return l; } template <class T> vector<T> operator+(vector<T> l, const vector<T>& r) { return l += r; } template <class T> vector<T>& operator-=(vector<T>& l, const vector<T>& r) { l.resize(max(l.size(), r.size())); for (int i = 0; i < (int)r.size(); ++i) l[i] -= r[i]; return l; } template <class T> vector<T> operator-(vector<T> l, const vector<T>& r) { return l -= r; } template <class T> vector<T>& operator<<=(vector<T>& a, size_t n) { return a.insert(begin(a), n, 0), a; } template <class T> vector<T> operator<<(vector<T> a, size_t n) { return a <<= n; } template <class T> vector<T>& operator>>=(vector<T>& a, size_t n) { return a.erase(begin(a), begin(a) + min(a.size(), n)), a; } template <class T> vector<T> operator>>(vector<T> a, size_t n) { return a >>= n; } template <class T> vector<T> operator*(const vector<T>& l, const vector<T>& r) { if (l.empty() or r.empty()) return {}; vector<T> res(l.size() + r.size() - 1); for (int i = 0; i < (int)l.size(); ++i) for (int j = 0; j < (int)r.size(); ++j) res[i + j] += l[i] * r[j]; return res; } template <class T> vector<T>& operator*=(vector<T>& l, const vector<T>& r) { return l = l * r; } template <class T> vector<T> inverse(const vector<T>& a) { assert(not a.empty() and not (a[0] == 0)); vector<T> b{1 / a[0]}; while (b.size() < a.size()) { vector<T> x(begin(a), begin(a) + min(a.size(), 2 * b.size())); x *= b * b; b.resize(2 * b.size()); for (auto i = b.size() / 2; i < min(x.size(), b.size()); ++i) b[i] = -x[i]; } return {begin(b), begin(b) + a.size()}; } template <class T> vector<T> operator/(vector<T> l, vector<T> r) { if (l.size() < r.size()) return {}; reverse(begin(l), end(l)), reverse(begin(r), end(r)); int n = l.size() - r.size() + 1; l.resize(n), r.resize(n); l *= inverse(r); return {rend(l) - n, rend(l)}; } template <class T> vector<T>& operator/=(vector<T>& l, const vector<T>& r) { return l = l / r; } template <class T> vector<T> operator%(vector<T> l, const vector<T>& r) { if (l.size() < r.size()) return l; l -= l / r * r; return {begin(l), begin(l) + (r.size() - 1)}; } template <class T> vector<T>& operator%=(vector<T>& l, const vector<T>& r) { return l = l % r; } template <class T> vector<T> derivative(const vector<T>& a) { vector<T> res(max((int)a.size() - 1, 0)); for (int i = 0; i < (int)res.size(); ++i) res[i] = (i + 1) * a[i + 1]; return res; } template <class T> vector<T> primitive(const vector<T>& a) { vector<T> res(a.size() + 1); for (int i = 1; i < (int)res.size(); ++i) res[i] = a[i - 1] / i; return res; } template <class T> vector<T> logarithm(const vector<T>& a) { assert(not a.empty() and a[0] == 1); auto res = primitive(derivative(a) * inverse(a)); return {begin(res), begin(res) + a.size()}; } template <class T> vector<T> exponent(const vector<T>& a) { assert(a.empty() or a[0] == 0); vector<T> b{1}; while (b.size() < a.size()) { vector<T> x(begin(a), begin(a) + min(a.size(), 2 * b.size())); x[0] += 1; b.resize(2 * b.size()); x -= logarithm(b); x *= {begin(b), begin(b) + b.size() / 2}; for (auto i = b.size() / 2; i < min(x.size(), b.size()); ++i) b[i] = x[i]; } return {begin(b), begin(b) + a.size()}; } 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 <class T> complex<T> mul(const complex<T>& l, const complex<T>& r) { return {real(l) * real(r) - imag(l) * imag(r), real(l) * imag(r) + imag(l) * real(r)}; } template <class T> void fft(vector<complex<T>>& a, bool inverse) { int n = a.size(); assert((n & (n - 1)) == 0); static vector<complex<T>> w{1}; if (2 * w.size() < a.size()) { w.resize(n / 2); T th = 2 * acos((T)-1) / n; for (int i = 1, j = 0; 2 * i < n; ++i) { int k = n >> 2; while (j >= k) j -= k, k >>= 1; w[i] = polar<T>(1, (j += k) * th); } } if (not inverse) { for (int m = n; m >>= 1; ) { for (int s = 0, k = 0; s < n; s += 2 * m, ++k) { for (int i = s, j = s + m; i < s + m; ++i, ++j) { auto x = a[i], y = mul(a[j], w[k]); a[i] = x + y, a[j] = x - y; } } } } else { for (int m = 1; m < n; m *= 2) { for (int s = 0, k = 0; s < n; s += 2 * m, ++k) { 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] = mul(x - y, conj(w[k])); } } } auto inv = (T)1 / complex<T>(n); for (auto&& e : a) e = mul(e, inv); } } template <class T> void two_real_fft(vector<complex<T>>& a, vector<complex<T>>& b) { assert(a.size() == b.size()); int n = a.size(); for (int i = 0; i < n; ++i) a[i].imag(real(b[i])); fft(a, false); for (int i = 0; i < n; ++i) { int j = i ? i ^ ((1 << __lg(i)) - 1): 0; if (i > j) continue; b[i] = mul(conj(a[j]) - a[i], {0, 0.5}), b[j] = conj(b[i]); a[i] = mul(a[i] + conj(a[j]), {0.5, 0}), a[j] = conj(a[i]); } } template <class T> void two_real_ifft(vector<complex<T>>& a, vector<complex<T>>& b) { assert(a.size() == b.size()); int n = a.size(); for (int i = 0; i < n; ++i) a[i] += mul({0, 1}, b[i]); fft(a, true); for (int i = 0; i < n; ++i) b[i].real(imag(a[i])); } vector<long long> operator*(const vector<int>& l, const vector<int>& 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] += (long long)l[i] * r[j]; return res; } vector<complex<double>> a(begin(l), end(l)), b(begin(r), end(r)); a.resize(sz), b.resize(sz), two_real_fft(a, b); for (int i = 0; i < sz; ++i) a[i] *= b[i]; fft(a, true); vector<long long> res(n + m - 1); for (int i = 0; i < n + m - 1; ++i) res[i] = round(real(a[i])); return res; } template <unsigned Mod, int K = 3, int B = 11> vector<Modular<Mod>> operator*( const vector<Modular<Mod>>& l, const 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)}; } vector<vector<complex<double>>> a(K, vector<complex<double>>(sz)), b = a; for (int x = 0; x < K; ++x) { for (int i = 0; i < n; ++i) a[x][i] = (l[i].v >> (x * B)) & ((1 << B) - 1); for (int j = 0; j < m; ++j) b[x][j] = (r[j].v >> (x * B)) & ((1 << B) - 1); two_real_fft(a[x], b[x]); } vector<vector<complex<double>>> c(2 * K - 1, vector<complex<double>>(sz)); for (int x = 0; x < K; ++x) for (int y = 0; y < K; ++y) for (int i = 0; i < sz; ++i) c[x + y][i] += mul(a[x][i], b[y][i]); vector<Modular<Mod>> res(n + m - 1); for (int x = 0; x < 2 * K - 1; ++x) { if (x == 0) fft(c[x], true); else if (x & 1) two_real_ifft(c[x], c[x + 1]); auto base = power(Modular<Mod>(2), x * B); for (int i = 0; i < n + m - 1; ++i) res[i] += round(real(c[x][i])) * base; } return res; } constexpr long long mod = 998244353; using Mint = Modular<mod>; int main() { int n = getint<int>(); vector<Mint> a(n); generate(begin(a), end(a), [] { return getint<int>(); }); a = exponent(a); for (int i = 0; i < n; ++i) { putint(a[i].v, " \n"[i == n - 1]); } }