Submit Info #44803

Problem Lang User Status Time Memory
Log of Formal Power Series cpp mnbvmar AC 525 ms 31.41 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.71 MiB
max_all_zero_00 AC 502 ms 30.87 MiB
max_random_00 AC 524 ms 30.91 MiB
max_random_01 AC 523 ms 30.87 MiB
max_random_02 AC 524 ms 30.87 MiB
max_random_03 AC 525 ms 30.87 MiB
max_random_04 AC 523 ms 30.87 MiB
near_262144_00 AC 256 ms 17.92 MiB
near_262144_01 AC 255 ms 17.92 MiB
near_262144_02 AC 489 ms 29.94 MiB
random_00 AC 507 ms 31.41 MiB
random_01 AC 511 ms 30.29 MiB
random_02 AC 57 ms 4.25 MiB
random_03 AC 512 ms 29.77 MiB
random_04 AC 492 ms 29.98 MiB
small_degree_00 AC 2 ms 0.68 MiB
small_degree_01 AC 1 ms 0.64 MiB
small_degree_02 AC 1 ms 0.64 MiB
small_degree_03 AC 1 ms 0.68 MiB
small_degree_04 AC 1 ms 0.68 MiB
small_degree_05 AC 1 ms 0.68 MiB
small_degree_06 AC 1 ms 0.68 MiB
small_degree_07 AC 4 ms 0.68 MiB
small_degree_08 AC 1 ms 0.68 MiB
small_degree_09 AC 3 ms 0.68 MiB

// Follows https://github.com/cuber2460/acmlib07/blob/master/code/finaly/code/FFT.cpp #include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; #define SZ(x) ((int)(x).size()) // If [mod] needs to be variable, move it to the struct and initialize // it in the beginning of the constructor. template <int mod> struct FormalSeries { private: int maxn; int root; static inline void add_mod(int &a, int b) { a += b; if (a >= mod) { a -= mod; } } static inline void sub_mod(int &a, int b) { a -= b; if (a < 0) { a += mod; } } static inline int mul_mod(int a, int b) { return (int)((ll)a * b % mod); } static inline int pow_mod(int a, int n) { int r = 1; while (n) { if (n & 1) { r = mul_mod(r, a); } n >>= 1; a = mul_mod(a, a); } return r; } static inline int inv_mod(int a) { return pow_mod(a, mod - 2); } static inline int div_mod(int a, int b) { return mul_mod(a, inv_mod(b)); } vector<int> FindPrimeFactors(int num) { vector<int> ans; for (int p = 2; p * p <= num; ++p) { if (num % p == 0) { ans.push_back(p); while (num % p == 0) { num /= p; } } } if (num > 1) { ans.push_back(num); } return ans; } void FindGenerator() { vector<int> prime_factors = FindPrimeFactors(mod - 1); while (true) { const int g = rand() % (mod - 1) + 1; bool ok = true; for (int p : prime_factors) { if (pow_mod(g, mod / p) == 1) { ok = false; break; } } if (ok) { root = pow_mod(g, mod / maxn); break; } } } void DFT(vi &a, bool rev) const { const int n = a.size(); for (int i = 1, k = 0; i < n; ++i) { for (int bit = n / 2; (k ^= bit) < bit; bit /= 2);;; if (i < k) { swap(a[i], a[k]); } } for (int len = 1, who = 0; len < n; len *= 2, ++who) { static vi t[32]; vi &om = t[who]; if (om.empty()) { om.resize(2 * len + 1); if (who == 0) { om[0] = 1; om[1] = mod - 1; } else { const int stepg = pow_mod(root, maxn / (2 * len)); for (int i = 0; i < 2 * len; ++i) { om[i] = t[who - 1][i / 2]; if (i & 1) { om[i] = mul_mod(om[i], stepg); } } } om.back() = om[0]; } for (int i = 0; i < n; i += 2 * len) { for (int k = 0; k < len; ++k) { const int x = a[i + k]; const int y = mul_mod(a[i + k + len], om[rev ? 2 * len - k : k]); add_mod(a[i + k], y); a[i + k + len] = x; sub_mod(a[i + k + len], y); } } } if (rev) { const int div = inv_mod(n); for (int &x : a) { x = mul_mod(x, div); } } } public: FormalSeries(int max_terms) { // (max_terms = max_degree + 1) maxn = 1; while (maxn < max_terms) { maxn *= 2; } assert((mod - 1) % maxn == 0 && "Not enough powers of 2 in mod-1"); FindGenerator(); } vi Mul(const vi &a, const vi &b) const { if (a.empty() || b.empty()) { return {}; } int n = a.size() + b.size(); const int ans_size = n - 1; assert(n <= maxn); while (n & (n - 1)) { ++n; } vi X(n), Y(n); copy(a.begin(), a.end(), X.begin()); copy(b.begin(), b.end(), Y.begin()); DFT(X, false); DFT(Y, false); for (int i = 0; i < n; ++i) { X[i] = mul_mod(X[i], Y[i]); } DFT(X, true); X.resize(ans_size); return X; } vi MakeConst(int x) const { assert(x >= 0); return vi{x % mod}; } void NegSelf(vi &A) const { for (int &x : A) { if (x) { x = mod - x; } } } void TrimSelf(vi &A, int num_terms) const { if (SZ(A) > num_terms) { A.resize(num_terms); } } vi Trim(vi A, int num_terms) const { TrimSelf(A, num_terms); return A; } vi Differentiate(vi Q) const { const int n = SZ(Q); for (int i = 1; i < n; ++i) { Q[i - 1] = mul_mod(i, Q[i]); } Q.pop_back(); return Q; } vi Integrate(const vi &Q) const { if (Q.empty()) { return {0}; } const int n = SZ(Q); vi P(n + 1); // Make inverses of 1..n. P[1] = 1; for (int i = 2; i <= n; ++i) { P[i] = mul_mod(mod - mod / i, P[mod % i]); } // Now, multiply them pointwise with Q. for (int i = 1; i <= n; ++i) { P[i] = mul_mod(P[i], Q[i - 1]); } return P; } vi Inv(const vi &Q) const { const int n = SZ(Q); assert(n > 0 && Q[0] != 0); assert(n <= maxn / 2); auto P = MakeConst(inv_mod(Q[0])); while (SZ(P) < n) { const int sz = SZ(P); auto cur = Mul(Trim(Q, sz * 2), P); TrimSelf(cur, sz * 2); NegSelf(cur); add_mod(cur[0], 2); P = Trim(Mul(cur, P), sz * 2); } TrimSelf(P, n); return P; } vi Log(const vi &Q) const { assert(!Q.empty() && Q[0] == 1); const int n = Q.size(); auto Qdif = Differentiate(Q); return Integrate(Trim(Mul(Qdif, Inv(Q)), n - 1)); } // vi Exp(const vi &Q) const { // const int n = SZ(Q); // assert(n > 0 && Q[0] == 0); // // TODO assert on n <= ... // auto P = MakeConst(1); // while (SZ(P) < n) { // const int sz = SZ(P); // } // } }; int main() { ios_base::sync_with_stdio(false); const int p = 998244353; FormalSeries<p> fft(1 << 20); int n; cin >> n; vi A(n); for (int &x : A) { cin >> x; } auto lg_a = fft.Log(A); for (int x : lg_a) { cout << x << " "; } cout << "\n"; }