Submit Info #48822

Problem Lang User Status Time Memory
Log of Formal Power Series cpp WeakestTopology AC 2118 ms 61.88 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
max_all_zero_00 AC 2100 ms 61.79 MiB
max_random_00 AC 2113 ms 61.80 MiB
max_random_01 AC 2113 ms 61.80 MiB
max_random_02 AC 2116 ms 61.80 MiB
max_random_03 AC 2118 ms 61.80 MiB
max_random_04 AC 2114 ms 61.80 MiB
near_262144_00 AC 1006 ms 31.78 MiB
near_262144_01 AC 1006 ms 30.82 MiB
near_262144_02 AC 2085 ms 61.76 MiB
random_00 AC 2100 ms 61.88 MiB
random_01 AC 2106 ms 61.83 MiB
random_02 AC 227 ms 8.37 MiB
random_03 AC 2114 ms 61.84 MiB
random_04 AC 2084 ms 61.78 MiB
small_degree_00 AC 1 ms 0.68 MiB
small_degree_01 AC 1 ms 0.71 MiB
small_degree_02 AC 2 ms 0.68 MiB
small_degree_03 AC 1 ms 0.68 MiB
small_degree_04 AC 1 ms 0.71 MiB
small_degree_05 AC 1 ms 0.61 MiB
small_degree_06 AC 3 ms 0.68 MiB
small_degree_07 AC 1 ms 0.71 MiB
small_degree_08 AC 1 ms 0.68 MiB
small_degree_09 AC 1 ms 0.61 MiB

#include "bits/stdc++.h" using namespace std; #define endl '\n' #define debug(x) cerr << #x << " == " << (x) << '\n'; #define all(x) begin(x), end(x) using ll = long long; const int INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3fLL; template<ll mod> struct Mint { ll x; Mint(ll x = 0) : x((x %= mod) < 0 ? x + mod : x) { } Mint& operator+=(Mint rhs) { return (x += rhs.x) >= mod ? x -= mod : 0, *this; } Mint& operator-=(Mint rhs) { return (x -= rhs.x) < 0 ? x += mod : 0, *this; } Mint& operator*=(Mint rhs) { return (x *= rhs.x) %= mod, *this; } Mint& operator/=(Mint rhs) { return *this *= rhs.power(-1); } Mint power(ll p) const { p %= mod - 1; if (p < 0) p += mod - 1; Mint res = 1; for (Mint y = *this; p; p >>= 1, y *= y) if (p & 1) res *= y; return res; } bool operator==(Mint rhs) const { return x == rhs.x; } bool operator<(Mint rhs) const { return x < rhs.x; } friend Mint operator+(Mint lhs, Mint rhs) { return lhs += rhs; } friend Mint operator-(Mint lhs, Mint rhs) { return lhs -= rhs; } friend Mint operator*(Mint lhs, Mint rhs) { return lhs *= rhs; } friend Mint operator/(Mint lhs, Mint rhs) { return lhs /= rhs; } friend ostream& operator<<(ostream& out, Mint a) { return out << a.x; } friend istream& operator>>(istream& in, Mint& a) { ll x; in >> x; a = Mint(x); return in; } }; constexpr ll mod = 998244353; using mint = Mint<mod>; template<typename T> T getroot(int N) { static auto PI = acos(T(-1).real()); return polar<decltype(PI)>(1, 2 * PI / N); } // 998244353 = 1 + 7 * 17 * (2 ^ 23) // 469762049 = 1 + 7 * (2 ^ 26) // 167772161 = 1 + 5 * (2 ^ 25) constexpr int MODs[] = { 998244353, 469762049, 167772161 }; constexpr int preexp[] = { 7 * 17, 7, 5 }; constexpr int explog[] = { 23, 26, 25 }; constexpr int primitive[] = { 3, 3, 3 }; using M998 = Mint<MODs[0]>; template<> M998 getroot<M998>(int N) { return M998(primitive[0]).power(preexp[0] * (1LL << explog[0]) / N); } template<typename T> void fft(vector<T>& p, vector<T>& aux, T rt, int idx, int n) { if (n == 1) return; int k = n >> 1, ldx = idx, rdx = idx + k; for (int i = 0, cur = ldx, nxt = rdx; i < n; ++i, swap(cur, nxt)) aux[cur + (i >> 1)] = p[idx + i]; fft(aux, p, rt * rt, ldx, k), fft(aux, p, rt * rt, rdx, k); for (auto [i, xp] = pair(0, T(1)); i < n; ++i, xp *= rt) p[idx + i] = aux[ldx + (i % k)] + xp * aux[rdx + (i % k)]; } // inplace fft, resizes if necessary template<typename T> void fft(vector<T>& p, bool inverse = false) { int N = 1; while ((int)size(p) > N) N <<= 1; p.resize(N); static vector<T> aux; aux.resize(max(size(aux), size(p))); T root = getroot<T>(N); if (inverse) { fft(p, aux, T(1) / root, 0, N); T inv = T(1) / T(N); for (int i = 0; i < N; ++i) p[i] *= inv; } else fft(p, aux, root, 0, N); } template<typename T> vector<T> operator*(vector<T> p, vector<T> q) { int n = (int)size(p), m = (int)size(q), N = n + m - 1; p.resize(N), q.resize(N); fft(p), fft(q); for (size_t i = 0; i < size(p); ++i) p[i] *= q[i]; fft(p, true); p.resize(N); return p; } template<typename T> vector<T>& operator*=(vector<T>& p, const vector<T>& q) { return p = p * q; } template<typename T> vector<T>& operator+=(vector<T>& p, const vector<T>& q) { p.resize(max(size(p), size(q))); for (size_t i = 0; i < size(q); ++i) p[i] += q[i]; return p; } template<typename T> vector<T> operator+(vector<T> p, const vector<T>& q) { return p += q; } template<typename T> vector<T>& operator-=(vector<T>& p, const vector<T>& q) { p.resize(max(size(p), size(q))); for (size_t i = 0; i < size(q); ++i) p[i] -= q[i]; return p; } template<typename T> vector<T> operator-(vector<T> p, const vector<T>& q) { return p -= q; } template<typename T> vector<T>& operator*=(vector<T>& p, T alpha) { for (auto& x : p) x *= alpha; return p; } template<typename T> vector<T> operator*(vector<T> p, T alpha) { return p *= alpha; } template<typename T> vector<T> operator*(T alpha, vector<T> p) { return p *= alpha; } template<typename T> vector<T> operator-(vector<T> p) { return p *= T(-1); } // assumes n = size(p) is power a of 2 // O(n * log(n)) template<typename T> vector<T> inv(const vector<T>& p) { if (size(p) == 1) return {1/p[0]}; size_t K = size(p) / 2; vector<T> q(begin(p), begin(p) + K); auto B = inv(q); auto C = -p * B; C[0] += 2; C.resize(2 * K); auto r = B * C; r.resize(2 * K); return r; } template<typename T> vector<T> D(vector<T> p) { for (size_t i = 1; i < size(p); ++i) p[i] *= i; p.erase(begin(p)); return p; } // log(1 + p(x)) template<typename T> vector<T> log(const vector<T>& p) { auto r = inv(p) * D(p); r.resize(size(p) - 1); r.insert(begin(r), 0); for (size_t i = 1; i < size(r); ++i) r[i] /= i; return r; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int N; cin >> N; vector<mint> A(N); for (auto& x : A) cin >> x; int K = 1; while (K < N) K <<= 1; A.resize(K); auto B = log(A); for (int i = 0; i < N; ++i) { cout << B[i] << "\n "[i + 1 < N]; } exit(0); }