Submit Info #33141

Problem Lang User Status Time Memory
Polynomial Taylor Shift cpp-acl opt AC 107 ms 16.85 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.80 MiB
example_01 AC 0 ms 0.75 MiB
fft_killer_00 AC 107 ms 16.85 MiB
fft_killer_01 AC 102 ms 16.61 MiB
max_random_00 AC 104 ms 16.79 MiB
max_random_01 AC 105 ms 16.79 MiB
medium_00 AC 2 ms 0.80 MiB
medium_01 AC 4 ms 1.02 MiB
medium_02 AC 2 ms 1.01 MiB
medium_all_zero_00 AC 1 ms 0.78 MiB
medium_c_zero_00 AC 1 ms 0.87 MiB
random_00 AC 100 ms 14.81 MiB
random_01 AC 101 ms 15.90 MiB
random_02 AC 14 ms 2.59 MiB
small_00 AC 1 ms 0.73 MiB
small_01 AC 0 ms 0.73 MiB
small_02 AC 1 ms 0.80 MiB
small_03 AC 2 ms 0.75 MiB
small_04 AC 3 ms 0.51 MiB
small_05 AC 1 ms 0.80 MiB
small_06 AC 1 ms 0.82 MiB
small_07 AC 1 ms 0.81 MiB
small_08 AC 1 ms 0.74 MiB
small_09 AC 1 ms 0.79 MiB
small_10 AC 1 ms 0.77 MiB
small_11 AC 1 ms 0.77 MiB
small_12 AC 1 ms 0.80 MiB
small_13 AC 2 ms 0.80 MiB
small_14 AC 2 ms 0.80 MiB
small_15 AC 0 ms 0.80 MiB

#include<bits/stdc++.h> using namespace std; #include<atcoder/all> using namespace atcoder; istream &operator>>(istream &is, modint998244353 &a) { long long v; is >> v; a = v; return is; } ostream &operator<<(ostream &os, const modint998244353 &a) { return os << a.val(); } istream &operator>>(istream &is, modint1000000007 &a) { long long v; is >> v; a = v; return is; } ostream &operator<<(ostream &os, const modint1000000007 &a) { return os << a.val(); } template<int m> istream &operator>>(istream &is, static_modint<m> &a) { long long v; is >> v; a = v; return is; } template<int m> istream &operator>>(istream &is, dynamic_modint<m> &a) { long long v; is >> v; a = v; return is; } template<int m> ostream &operator<<(ostream &os, const static_modint<m> &a) { return os << a.val(); } template<int m> ostream &operator<<(ostream &os, const dynamic_modint<m> &a) { return os << a.val(); } #define rep2(i, m, n) for (int i = (m); i < (n); ++i) #define rep(i, n) rep2(i, 0, n) #define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i) #define drep(i, n) drep2(i, n, 0) using ll = long long; template<class T> istream &operator>>(istream &is, vector<T> &v) { for (auto &e : v) is >> e; return is; } template<class T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << ' '; return os; } struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_; // verified by: // https://judge.yosupo.jp/problem/convolution_mod // https://judge.yosupo.jp/problem/inv_of_formal_power_series // https://judge.yosupo.jp/problem/log_of_formal_power_series // https://judge.yosupo.jp/problem/exp_of_formal_power_series // https://judge.yosupo.jp/problem/pow_of_formal_power_series using mint = modint998244353; template<typename T> struct Factorial { int MAX; vector<T> fac, finv; Factorial(int m = 0) : MAX(m), fac(m+1, 1), finv(m+1, 1) { rep2(i, 2, MAX+1) fac[i] = fac[i-1] * i; finv[MAX] /= fac[MAX]; drep2(i, MAX+1, 3) finv[i-1] = finv[i] * i; } T binom(int n, int k) { if (k < 0 || n < k) return 0; return fac[n] * finv[k] * finv[n-k]; } T perm(int n, int k) { if (k < 0 || n < k) return 0; return fac[n] * finv[n-k]; } }; Factorial<mint> fc; template<class T> struct FormalPowerSeries : vector<T> { using vector<T>::vector; using vector<T>::operator=; using F = FormalPowerSeries; F operator-() const { F res(*this); for (auto &e : res) e = -e; return res; } F &operator*=(const T &g) { for (auto &e : *this) e *= g; return *this; } F &operator/=(const T &g) { assert(g != T(0)); *this *= g.inv(); return *this; } F &operator+=(const F &g) { int n = this->size(), m = g.size(); rep(i, min(n, m)) (*this)[i] += g[i]; return *this; } F &operator-=(const F &g) { int n = this->size(), m = g.size(); rep(i, min(n, m)) (*this)[i] -= g[i]; return *this; } F &operator<<=(const int d) { int n = this->size(); if (d >= n) *this = F(n); this->insert(this->begin(), d, 0); this->resize(n); return *this; } F &operator>>=(const int d) { int n = this->size(); this->erase(this->begin(), this->begin() + min(n, d)); this->resize(n); return *this; } // O(n log n) F inv(int d = -1) const { int n = this->size(); assert(n != 0 && (*this)[0] != 0); if (d == -1) d = n; assert(d >= 0); F res{(*this)[0].inv()}; for (int m = 1; m < d; m *= 2) { F f(this->begin(), this->begin() + min(n, 2*m)); F g(res); f.resize(2*m), internal::butterfly(f); g.resize(2*m), internal::butterfly(g); rep(i, 2*m) f[i] *= g[i]; internal::butterfly_inv(f); f.erase(f.begin(), f.begin() + m); f.resize(2*m), internal::butterfly(f); rep(i, 2*m) f[i] *= g[i]; internal::butterfly_inv(f); T iz = T(2*m).inv(); iz *= -iz; rep(i, m) f[i] *= iz; res.insert(res.end(), f.begin(), f.begin() + m); } res.resize(d); return res; } // fast: FMT-friendly modulus only // O(n log n) F &multiply_inplace(const F &g, int d = -1) { int n = this->size(); if (d == -1) d = n; assert(d >= 0); *this = convolution(move(*this), g); this->resize(d); return *this; } F multiply(const F &g, const int d = -1) const { return F(*this).multiply_inplace(g, d); } // O(n log n) F &divide_inplace(const F &g, int d = -1) { int n = this->size(); if (d == -1) d = n; assert(d >= 0); *this = convolution(move(*this), g.inv(d)); this->resize(d); return *this; } F divide(const F &g, const int d = -1) const { return F(*this).divide_inplace(g, d); } // // naive // // O(n^2) // F &multiply_inplace(const F &g) { // int n = this->size(), m = g.size(); // drep(i, n) { // (*this)[i] *= g[0]; // rep2(j, 1, min(i+1, m)) (*this)[i] += (*this)[i-j] * g[j]; // } // return *this; // } // F multiply(const F &g) const { return F(*this).multiply_inplace(g); } // // O(n^2) // F &divide_inplace(const F &g) { // assert(g[0] != T(0)); // T ig0 = g[0].inv(); // int n = this->size(), m = g.size(); // rep(i, n) { // rep2(j, 1, min(i+1, m)) (*this)[i] -= (*this)[i-j] * g[j]; // (*this)[i] *= ig0; // } // return *this; // } // F divide(const F &g) const { return F(*this).divide_inplace(g); } // sparse // O(nk) F &multiply_inplace(vector<pair<int, T>> g) { int n = this->size(); auto [d, c] = g.front(); if (d == 0) g.erase(g.begin()); else c = 0; drep(i, n) { (*this)[i] *= c; for (auto &[j, b] : g) { if (j > i) break; (*this)[i] += (*this)[i-j] * b; } } return *this; } F multiply(const vector<pair<int, T>> &g) const { return F(*this).multiply_inplace(g); } // O(nk) F &divide_inplace(vector<pair<int, T>> g) { int n = this->size(); auto [d, c] = g.front(); assert(d == 0 && c != T(0)); T ic = c.inv(); g.erase(g.begin()); rep(i, n) { for (auto &[j, b] : g) { if (j > i) break; (*this)[i] -= (*this)[i-j] * b; } (*this)[i] *= ic; } return *this; } F divide(const vector<pair<int, T>> &g) const { return F(*this).divide_inplace(g); } // multiply and divide (1 + cz^d) // O(n) void multiply_inplace(const int d, const T c) { int n = this->size(); if (c == T(1)) drep(i, n-d) (*this)[i+d] += (*this)[i]; else if (c == T(-1)) drep(i, n-d) (*this)[i+d] -= (*this)[i]; else drep(i, n-d) (*this)[i+d] += (*this)[i] * c; } // O(n) void divide_inplace(const int d, const T c) { int n = this->size(); if (c == T(1)) rep(i, n-d) (*this)[i+d] -= (*this)[i]; else if (c == T(-1)) rep(i, n-d) (*this)[i+d] += (*this)[i]; else rep(i, n-d) (*this)[i+d] -= (*this)[i] * c; } // O(n) T eval(const T &a) const { T x(1), res(0); for (auto e : *this) res += e * x, x *= a; return res; } // O(n) F &integ_inplace() { int n = this->size(); assert(n > 0); if (n == 1) return *this = F{0}; this->insert(this->begin(), 0); this->pop_back(); vector<T> inv(n); inv[1] = 1; int p = T::mod(); rep2(i, 2, n) inv[i] = - inv[p%i] * (p/i); rep2(i, 2, n) (*this)[i] *= inv[i]; return *this; } F integ() const { return F(*this).integ_inplace(); } // O(n) F &deriv_inplace() { int n = this->size(); assert(n > 0); rep2(i, 2, n) (*this)[i] *= i; this->erase(this->begin()); this->push_back(0); return *this; } F deriv() const { return F(*this).deriv_inplace(); } // O(n log n) F &log_inplace(int d = -1) { int n = this->size(); assert(n > 0 && (*this)[0] == 1); if (d == -1) d = n; assert(d >= 0); if (d < n) this->resize(d); F f_inv = this->inv(); this->deriv_inplace(); this->multiply_inplace(f_inv); this->integ_inplace(); return *this; } F log(const int d = -1) const { return F(*this).log_inplace(d); } // O(n log n) // https://arxiv.org/abs/1301.5804 (Figure 1, right) F &exp_inplace(int d = -1) { int n = this->size(); assert(n > 0 && (*this)[0] == 0); if (d == -1) d = n; assert(d >= 0); F g{1}, g_fft{1, 1}; (*this)[0] = 1; this->resize(d); F h_drv(this->deriv()); for (int m = 2; m < d; m *= 2) { // prepare F f_fft(this->begin(), this->begin() + m); f_fft.resize(2*m), internal::butterfly(f_fft); // Step 2.a' { F _g(m); rep(i, m) _g[i] = f_fft[i] * g_fft[i]; internal::butterfly_inv(_g); _g.erase(_g.begin(), _g.begin() + m/2); _g.resize(m), internal::butterfly(_g); rep(i, m) _g[i] *= g_fft[i]; internal::butterfly_inv(_g); _g.resize(m/2); _g /= T(-m) * m; g.insert(g.end(), _g.begin(), _g.begin() + m/2); } // Step 2.b'--d' F t(this->begin(), this->begin() + m); t.deriv_inplace(); { // Step 2.b' F r{h_drv.begin(), h_drv.begin() + m-1}; // Step 2.c' r.resize(m); internal::butterfly(r); rep(i, m) r[i] *= f_fft[i]; internal::butterfly_inv(r); r /= -m; // Step 2.d' t += r; t.insert(t.begin(), t.back()); t.pop_back(); } // Step 2.e' if (2*m < d) { t.resize(2*m); internal::butterfly(t); g_fft = g; g_fft.resize(2*m); internal::butterfly(g_fft); rep(i, 2*m) t[i] *= g_fft[i]; internal::butterfly_inv(t); t.resize(m); t /= 2*m; } else { // この場合分けをしても数パーセントしか速くならない F g1(g.begin() + m/2, g.end()); F s1(t.begin() + m/2, t.end()); t.resize(m/2); g1.resize(m), internal::butterfly(g1); t.resize(m), internal::butterfly(t); s1.resize(m), internal::butterfly(s1); rep(i, m) s1[i] = g_fft[i] * s1[i] + g1[i] * t[i]; rep(i, m) t[i] *= g_fft[i]; internal::butterfly_inv(t); internal::butterfly_inv(s1); rep(i, m/2) t[i+m/2] += s1[i]; t /= m; } // Step 2.f' F v(this->begin() + m, this->begin() + min<int>(d, 2*m)); v.resize(m); t.insert(t.begin(), m-1, 0); t.push_back(0); t.integ_inplace(); rep(i, m) v[i] -= t[m+i]; // Step 2.g' v.resize(2*m); internal::butterfly(v); rep(i, 2*m) v[i] *= f_fft[i]; internal::butterfly_inv(v); v.resize(m); v /= 2*m; // Step 2.h' rep(i, min(d-m, m)) (*this)[m+i] = v[i]; } return *this; } F exp(const int d = -1) const { return F(*this).exp_inplace(d); } // O(n log n) F &pow_inplace(const ll k, int d = -1) { int n = this->size(); if (d == -1) d = n; assert(d >= 0 && k >= 0); if (k == 0) { *this = F(d); if (d > 0) (*this)[0] = 1; return *this; } int l = 0; while (l < n && (*this)[l] == 0) ++l; if (l > (d-1)/k || l == n) return *this = F(d); T c = (*this)[l]; this->erase(this->begin(), this->begin() + l); *this /= c; this->log_inplace(d - l*k); *this *= k; this->exp_inplace(); *this *= c.pow(k); this->insert(this->begin(), l*k, 0); return *this; } F pow(const ll k, const int d = -1) const { return F(*this).pow_inplace(k, d); } // O(n log n) F &shift_inplace(const T c) { int n = this->size(); fc = Factorial<T>(n); rep(i, n) (*this)[i] *= fc.fac[i]; reverse(this->begin(), this->end()); F g(n); T cp = 1; rep(i, n) g[i] = cp * fc.finv[i], cp *= c; this->multiply_inplace(g, n); reverse(this->begin(), this->end()); rep(i, n) (*this)[i] *= fc.finv[i]; return *this; } F shift(const T c) const { return F(*this).shift_inplace(c); } F operator*(const T &g) const { return F(*this) *= g; } F operator/(const T &g) const { return F(*this) /= g; } F operator+(const F &g) const { return F(*this) += g; } F operator-(const F &g) const { return F(*this) -= g; } F operator<<(const int d) const { return F(*this) <<= d; } F operator>>(const int d) const { return F(*this) >>= d; } }; using fps = FormalPowerSeries<mint>; /** * @brief Scanner(高速入力) */ struct Scanner { public: explicit Scanner(FILE *fp) : fp(fp) {} template< typename T, typename... E > void read(T &t, E &... e) { read_single(t); read(e...); } private: static constexpr size_t line_size = 1 << 16; static constexpr size_t int_digits = 20; char line[line_size + 1] = {}; FILE *fp = nullptr; char *st = line; char *ed = line; void read() {} static inline bool is_space(char c) { return c <= ' '; } void reread() { ptrdiff_t len = ed - st; memmove(line, st, len); char *tmp = line + len; ed = tmp + fread(tmp, 1, line_size - len, fp); *ed = 0; st = line; } void skip_space() { while(true) { if(st == ed) reread(); while(*st && is_space(*st)) ++st; if(st != ed) return; } } template< typename T, enable_if_t< is_integral< T >::value, int > = 0 > void read_single(T &s) { skip_space(); if(st + int_digits >= ed) reread(); bool neg = false; if(is_signed< T >::value && *st == '-') { neg = true; ++st; } typename make_unsigned< T >::type y = *st++ - '0'; while(*st >= '0') { y = 10 * y + *st++ - '0'; } s = (neg ? -y : y); } template< typename T, enable_if_t< is_same< T, string >::value, int > = 0 > void read_single(T &s) { s = ""; skip_space(); while(true) { char *base = st; while(*st && !is_space(*st)) ++st; s += string(base, st); if(st != ed) return; reread(); } } template< typename T > void read_single(vector< T > &s) { for(auto &d : s) read(d); } }; /** * @brief Printer(高速出力) */ struct Printer { public: explicit Printer(FILE *fp) : fp(fp) {} ~Printer() { flush(); } template< bool f = false, typename T, typename... E > void write(const T &t, const E &... e) { if(f) write_single(' '); write_single(t); write< true >(e...); } template< typename... T > void writeln(const T &...t) { write(t...); write_single('\n'); } void flush() { fwrite(line, 1, st - line, fp); st = line; } private: FILE *fp = nullptr; static constexpr size_t line_size = 1 << 16; static constexpr size_t int_digits = 20; char line[line_size + 1] = {}; char small[32] = {}; char *st = line; template< bool f = false > void write() {} void write_single(const char &t) { if(st + 1 >= line + line_size) flush(); *st++ = t; } template< typename T, enable_if_t< is_integral< T >::value, int > = 0 > void write_single(T s) { if(st + int_digits >= line + line_size) flush(); if(s == 0) { write_single('0'); return; } if(s < 0) { write_single('-'); s = -s; } char *mp = small + sizeof(small); typename make_unsigned< T >::type y = s; size_t len = 0; while(y > 0) { *--mp = y % 10 + '0'; y /= 10; ++len; } memmove(st, mp, len); st += len; } void write_single(const string &s) { for(auto &c : s) write_single(c); } void write_single(const char *s) { while(*s != 0) write_single(*s++); } template< typename T > void write_single(const vector< T > &s) { for(size_t i = 0; i < s.size(); i++) { if(i) write_single(' '); write_single(s[i]); } } }; Scanner input(stdin); Printer output(stdout); // int main() { // int n, m; cin >> n >> m; // fps a(n), b(m); cin >> a >> b; // cout << a.multiply_inplace(b, n+m-1) << '\n'; // } // int main() { // int n; cin >> n; // fps a(n); cin >> a; // // cout << a.log() << '\n'; // // cout << a.inv() << '\n'; // cout << a.exp_inplace() << '\n'; // } // https://judge.yosupo.jp/problem/polynomial_taylor_shift void yosupo_shift() { int n; input.read(n); int c; input.read(c); fps a(n); for (auto &e : a) { int x; input.read(x); e = x; } a.shift_inplace(c); vector<int> ans(n); rep(i, n) ans[i] = a[i].val(); output.writeln(ans); } int main() { // yosupo_inv(); // yosupo_log(); // yosupo_exp(); // yosupo_pow(); yosupo_shift(); // yosupo_bernoulli(); // yosupo_count_subset_sum(); } // int main() { // int n; input.read(n); // int m; input.read(m); // fps a(n); // for (auto &e : a) { int x; input.read(x); e = x; } // // a = a.inv(); // // a.log_inplace(); // // a.exp_inplace(); // a.pow_inplace(m, n); // vector<int> ans(n); // rep(i, n) ans[i] = a[i].val(); // output.writeln(ans); // } // int main() { // int n, m; cin >> n >> m; // fps a(n); cin >> a; // cout << a.pow_inplace(m, n) << '\n'; // } // int main() { // // fps f = {3, 1, 4, 1, 5}; // fps f = {1, 1, 0, 0, 0}; // // sfps g = {{0, 1}, {1, -1}}; // // f /= g; // // f.integ(); // // f.deriv(); // f.log(); // cout << f << '\n'; // fps f = {3, 1, 4, 1, 5}; // fps g = {2, 7, 1}; // fps h = (f * g + g * 2) / g; // cout << f << '\n'; // cout << "(1): " << f << '\n'; // f *= 3; // cout << "(2): " << f << '\n'; // f = -f; // cout << "(3): " << f << '\n'; // f = f / -3; // cout << "(4): " << f << '\n'; // f += g; // cout << "(5): " << f << '\n'; // f = f - g; // cout << "(6): " << f << '\n'; // f = f * g; // cout << "(7): " << f << '\n'; // f /= g; // cout << "(8): " << f << '\n'; // f <<= 3; // cout << "(9): " << f << '\n'; // f = f >> 3; // cout << "(10): " << f << '\n'; // sfps h = {{0, 1}, {1, -1}, {2, -1}}; // f /= h; // cout << "(11): " << f << '\n'; // f = f * h; // cout << "(12): " << f << '\n'; // f.multiply(2, 10); // cout << "(13): " << f << '\n'; // f.divide(2, 10); // cout << "(14): " << f << '\n'; // cout << "(15): " << f.eval(-1) << '\n'; // }