Submit Info #40675

Problem Lang User Status Time Memory
Log of Formal Power Series cpp-acl Ebishu AC 261 ms 14.45 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
max_all_zero_00 AC 239 ms 14.38 MiB
max_random_00 AC 260 ms 14.45 MiB
max_random_01 AC 259 ms 14.45 MiB
max_random_02 AC 260 ms 14.45 MiB
max_random_03 AC 260 ms 14.45 MiB
max_random_04 AC 261 ms 14.44 MiB
near_262144_00 AC 128 ms 7.66 MiB
near_262144_01 AC 128 ms 7.66 MiB
near_262144_02 AC 220 ms 11.64 MiB
random_00 AC 241 ms 13.17 MiB
random_01 AC 253 ms 13.98 MiB
random_02 AC 30 ms 2.28 MiB
random_03 AC 250 ms 13.61 MiB
random_04 AC 224 ms 11.79 MiB
small_degree_00 AC 1 ms 0.67 MiB
small_degree_01 AC 1 ms 0.57 MiB
small_degree_02 AC 3 ms 0.68 MiB
small_degree_03 AC 3 ms 0.67 MiB
small_degree_04 AC 0 ms 0.62 MiB
small_degree_05 AC 1 ms 0.67 MiB
small_degree_06 AC 1 ms 0.67 MiB
small_degree_07 AC 2 ms 0.67 MiB
small_degree_08 AC 2 ms 0.67 MiB
small_degree_09 AC 1 ms 0.67 MiB

#include <algorithm> #include <array> #include <bitset> #include <cassert> #include <climits> #include <cmath> #include <cstring> #include <deque> #include <functional> #include <iostream> #include <map> #include <numeric> #include <optional> #include <queue> #include <set> #include <stack> #include <string> #include <tuple> #include <unordered_map> #include <unordered_set> #include <vector> using namespace std; using lint = long long; using P = pair<lint, lint>; #define rep(i, n) for (lint i = 0; i < (n); ++i) #define rep1(i, n) for (lint i = 1; i < (n); ++i) #define repn(i, a, b) for(lint i = (a); i < (b); ++i) #define rep_inv(i, n) for (lint i = (n); i >= 0; --i) #define all(vec) begin(vec), end(vec) constexpr lint Mod = /** 1000'000'007LL /*/ 998244353LL /**/; constexpr lint Inf = 1'000'000'000'000'000'010LL; constexpr int IntInf = 1000'000'010; constexpr double Pi = 3.141592653589793238; constexpr double InvPi = 0.318309886183790671; const int di[4] = { 0,1,0,-1 }, dj[4] = { 1,0,-1,0 }; #if __has_include(<atcoder/all>) #include <atcoder/all> using namespace atcoder; using mint = static_modint<Mod>; inline istream& operator>>(istream & is, mint & rhs) { long long tmp; is >> tmp; rhs = tmp; return is; } inline ostream& operator<<(ostream & os, const mint & rhs) { return os << rhs.val(); } #endif template<typename T> using prique = priority_queue<T>; template<typename T> using prique_inv = priority_queue<T, vector<T>, greater<T>>; template<typename T> inline istream& operator>>(istream& is, vector<T>& v) { for (auto&& e : v) is >> e; return is; } template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { size_t i = 0, n = v.size(); for (const auto& e : v) { os << e; if (++i < n) os << " "; } return os; } template<typename T, typename U> inline bool chmin(T& a, const U b) { return a > b ? a = b, true : false; } template<typename T, typename U> inline bool chmax(T& a, const U b) { return a < b ? a = b, true : false; } template<typename T, typename U> inline istream& operator>>(istream& is, pair<T, U>& rhs) { return is >> rhs.first >> rhs.second; } template<typename T, typename U> inline ostream& operator<<(ostream& os, const pair<T, U>& rhs) { return os << "{" << rhs.first << ", " << rhs.second << "}"; } template<typename T> T gcd(const vector<T>& vec) { T res = vec.front(); for (T e : vec) { res = gcd(res, e); if (res == 1) return 1; } return res; } template<typename T> T lcm(const vector<T>& vec) { T res = vec.front(); for (T e : vec) res = lcm(res, e); return res; } template<typename T> T pow(T x, lint n) { T res = 1; while (n > 0) { if (n & 1) res *= x; x *= x; n >>= 1; } return res; } bool is_prime(lint x) { for (lint i = 2; i * i <= x; ++i) { if (x % i == 0) return false; } return 1 < x; } constexpr lint fact_size = 3'000'010; lint fact[fact_size], fact_inv[fact_size]; void fact_init(lint n, lint m = Mod) { if (fact_size <= n) return; vector<lint> inv(n + 1); inv[1] = 1; fact[0] = fact[1] = 1; fact_inv[0] = 1; for (lint i = 2; i <= n; ++i) { fact[i] = i * fact[i - 1] % m; inv[i] = m - m / i * inv[m % i] % m; } for (lint i = 1; i <= n; ++i) { fact_inv[i] = fact_inv[i - 1] * inv[i] % m; } } lint modinv(lint a, lint m = Mod) { lint b = m, u = 1, v = 0; while (b != 0) { lint t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; if (u < 0) u += m; return u; } lint modpow(lint x, lint n, lint m = Mod) { lint res = 1; while (n > 0) { if (n & 1) res = res * x % m; x = x * x % m; n >>= 1; } return res; } lint intpow(lint x, lint n) { lint res = 1; while (n > 0) { if (n & 1) res *= x; x *= x; n >>= 1; } return res; } lint comb(lint n, lint r) { if (n < 0 || r < 0 || n < r) return 0; if (r == 0 || r == n) return 1; return fact[n] * fact_inv[n - r] % Mod * fact_inv[r] % Mod; } lint perm(lint n, lint r) { if (n < 0 || r < 0 || n < r) return 0; return fact[n] * fact_inv[n - r] % Mod; } class Factring { private: const lint max_n; vector<lint> sieve; public: explicit Factring(lint max_n) noexcept : max_n{ max_n } , sieve{ max_n } { iota(sieve.begin(), sieve.end(), 0); for (lint i = 2; i * i < max_n; ++i) { if (sieve[i] < i) continue; for (lint j = i * i; j < max_n; j += i) { if (sieve[j] == j) sieve[j] = i; } } } unordered_map<lint, lint> calc(lint x) const noexcept { unordered_map<lint, lint> res; while (x > 1) { ++res[sieve[x]]; x /= sieve[x]; } return res; } }; struct UnionFind { vector<int> par, rank, siz, es; explicit UnionFind(int n) noexcept : par(n) , rank(n) , siz(n, 1) , es(n) { iota(par.begin(), par.end(), 0); } int root(int x) noexcept { if (par[x] == x) return x; return par[x] = root(par[x]); } bool same(int x, int y) noexcept { return root(x) == root(y); } void unite(int x, int y) noexcept { x = root(x); y = root(y); if (x == y) ++es[x]; else if (rank[x] < rank[y]) { par[x] = y; siz[y] += siz[x]; es[y] += es[x] + 1; } else { par[y] = x; if (rank[x] == rank[y]) ++rank[x]; siz[x] += siz[y]; es[x] += es[y] + 1; } } int count(int x) noexcept { return siz[root(x)]; } vector<vector<int>> disjoint_sets() noexcept { vector<vector<int>> cnt(par.size()); for (int i = 0; i < (int)par.size(); ++i) { cnt[root(i)].push_back(i); } vector<vector<int>> res; for (const auto& v : cnt) { if (!v.empty()) { res.emplace_back(v); } } return res; } }; template<typename T> class CumulativeSum { private: vector<T> dat; public: CumulativeSum(const vector<T>& vec) noexcept { const size_t n = vec.size(); dat.resize(n + 1); for (size_t i = 0; i < n; ++i) { dat[i + 1] += dat[i] + vec[i]; } } // [l, r) T sum(int l, int r) const noexcept { return dat[r] - dat[l]; } }; template<typename T> class CumulativeSum2D { private: vector<vector<T>> dat; public: CumulativeSum2D() = default; CumulativeSum2D(const vector<vector<T>>& vec) noexcept { const size_t h = vec.size(), w = vec.front().size(); dat.resize(h + 1, vector<T>(w + 1)); for (size_t i = 0; i < h; ++i) { for (size_t j = 0; j < w; ++j) { dat[i + 1][j + 1] = dat[i][j + 1] + dat[i + 1][j] - dat[i][j] + vec[i][j]; } } } void set(const vector<vector<T>>& vec) noexcept { *this = CumulativeSum2D(vec); } // [0, h) × [0, w) T sum(int h, int w) const noexcept { return sum(0, 0, h, w); } // [h1, h2) × [w1, w2) T sum(int h1, int w1, int h2, int w2) const noexcept { return dat[h2][w2] - dat[h1][w2] - dat[h2][w1] + dat[h1][w1]; } }; template<typename T> class BinaryIndexedTree { private: const int size; vector<T> dat; public: explicit BinaryIndexedTree(int size) noexcept : size(size) , dat(size + 1) {} explicit BinaryIndexedTree(const vector<T>& vec) noexcept : size(vec.size()) , dat(size + 1) { for (int i = 0; i < size; ++i) { add(i + 1, vec[i]); } } // 1-indexed void add(int a, T w) noexcept { for (int x = a; x <= size; x += (x & -x)) dat[x] += w; } // [1, a) T sum(int a) const noexcept { T res = T(); for (int x = a - 1; x > 0; x -= (x & -x)) res += dat[x]; return res; } // [a, b) T sum(int a, int b) const noexcept { return sum(b) - sum(a); } // 1-indexed const T& operator[](int x) const noexcept { return dat[x]; } }; template<typename T> struct FormalPowerSeries : vector<T> { using vector<T>::vector; using vector<T>::operator=; using F = FormalPowerSeries; void shrink() { while (!this->empty() && this->back() == T(0)) this->pop_back(); } F operator+() const noexcept { return *this; } F operator-() const noexcept { F res(*this); for (auto&& e : res) e = -e; return res; } F operator*(const T& k) const noexcept { return F(*this) *= k; } F operator/(const T& k) const { return F(*this) /= k; } F operator+(const F& g) const noexcept { return F(*this) += g; } F operator-(const F& g) const noexcept { return F(*this) -= g; } F operator<<(const int d) const noexcept { return F(*this) <<= d; } F operator>>(const int d) const noexcept { return F(*this) >>= d; } F& operator*=(const T& k) noexcept { for (auto&& e : *this) e *= k; return *this; } F& operator/=(const T& k) { assert(k != T(0)); *this *= 1 / k; return *this; } F& operator+=(const F& g) noexcept { const int n = this->size(), m = g.size(); for (int i = 0; i < min(n, m); ++i) (*this)[i] += g[i]; return *this; } F& operator-=(const F& g) noexcept { const int n = this->size(), m = g.size(); for (int i = 0; i < min(n, m); ++i) (*this)[i] -= g[i]; return *this; } F& operator<<=(const int d) { const int n = this->size(); this->insert(this->begin(), d, T(0)); this->resize(n); return *this; } F& operator>>=(const int d) { const int n = this->size(); if (n <= d) return {}; this->erase(this->begin(), this->begin() + d); this->resize(n); return *this; } T operator()(T x) const noexcept { T res = this->back(); for (auto itr = ++this->rbegin(), itr_rend = this->rend(); itr != itr_rend; ++itr) { res *= x; res += *itr; } return res; } F inv(int d = -1) const { int n = this->size(); assert(n != 0 && this->front() != T(0)); if (d == -1) d = n; assert(d > 0); F res = { 1 / this->front() }; res.reserve(2 * d); int m = res.size(); while (m < d) { F f(this->begin(), this->begin() + min(n, 2 * m)); F r(res); f.resize(2 * m); r.resize(2 * m); atcoder::internal::butterfly(f); atcoder::internal::butterfly(r); for (int i = 0; i < 2 * m; ++i) f[i] *= r[i]; atcoder::internal::butterfly_inv(f); f.erase(f.begin(), f.begin() + m); f.resize(2 * m); atcoder::internal::butterfly(f); for (int i = 0; i < 2 * m; ++i) f[i] *= r[i]; atcoder::internal::butterfly_inv(f); T iz = T(1) / (2 * m); iz *= -iz; for (int i = 0; i < m; ++i) f[i] *= iz; res.insert(res.end(), f.begin(), f.begin() + m); m <<= 1; } return { res.begin(), res.begin() + d }; } F& multiply_inplace(const F& g, int d = -1) { if (d == -1) d = this->size(); assert(d >= 0); *this = atcoder::convolution(move(*this), g); this->resize(d); return *this; } F multiply(const F& g, int d = -1) const { return F(*this).multiply_inplace(g, d); } F& diff_inplace() noexcept { const int n = this->size(); for (int i = 1; i < n; ++i) (*this)[i - 1] = (*this)[i] * i; return *this; } F diff() const noexcept { return F(*this).diff_inplace(); } F& integral_inplace() noexcept { constexpr int p = T::mod(); const int n = this->size(); vector<T> inv(n); inv[1] = 1; for (int i = 2; i < n; ++i) inv[i] = -inv[p % i] * (p / i); for (int i = n - 1; i > 0; --i) { (*this)[i] = (*this)[i - 1] * inv[i]; } this->front() = 0; return *this; } F integral() const noexcept { return F(*this)->integral_inplace(); } F& log_inplace(int d = -1) { const int n = this->size(); assert(this->front() == 1); if (d == -1) d = n; assert(d >= 0); if (d < n) this->resize(d); const F f_inv = this->inv(); this->diff_inplace().multiply_inplace(f_inv).integral_inplace(); return *this; } F log(int d = -1) const { return F(*this).log_inplace(d); } }; using FPS = FormalPowerSeries<mint>; int main() { int n; scanf("%d", &n); FPS f(n); for(mint& e : f) { int a; scanf("%d", &a); e = mint::raw(a); } const auto& inv = f.log(); for (const mint& e : inv) printf("%u ", e.val()); }