Submit Info #16831

Problem Lang User Status Time Memory
Polynomial Taylor Shift cpp opt AC 198 ms 24.78 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.68 MiB
example_01 AC 1 ms 0.71 MiB
fft_killer_00 AC 198 ms 24.71 MiB
fft_killer_01 AC 189 ms 24.78 MiB
max_random_00 AC 191 ms 24.78 MiB
max_random_01 AC 191 ms 24.78 MiB
medium_00 AC 3 ms 0.81 MiB
medium_01 AC 6 ms 0.96 MiB
medium_02 AC 4 ms 0.99 MiB
medium_all_zero_00 AC 3 ms 0.80 MiB
medium_c_zero_00 AC 3 ms 0.80 MiB
random_00 AC 170 ms 22.08 MiB
random_01 AC 184 ms 23.49 MiB
random_02 AC 22 ms 3.50 MiB
small_00 AC 4 ms 0.72 MiB
small_01 AC 3 ms 0.67 MiB
small_02 AC 3 ms 0.67 MiB
small_03 AC 2 ms 0.71 MiB
small_04 AC 2 ms 0.68 MiB
small_05 AC 0 ms 0.68 MiB
small_06 AC 2 ms 0.68 MiB
small_07 AC 1 ms 0.68 MiB
small_08 AC 1 ms 0.72 MiB
small_09 AC 0 ms 0.72 MiB
small_10 AC 5 ms 0.67 MiB
small_11 AC 2 ms 0.67 MiB
small_12 AC 3 ms 0.69 MiB
small_13 AC 4 ms 0.67 MiB
small_14 AC 1 ms 0.68 MiB
small_15 AC 1 ms 0.67 MiB

#include <bits/stdc++.h> // #include <boost/multiprecision/cpp_int.hpp> // using i128 = boost::multiprecision::int128_t; #define _GLIBCXX_DEBUG using namespace std; using ll = long long; using ld = long double; using V = vector<int>; using Vll = vector<ll>; using Vld = vector<ld>; using Vbo = vector<bool>; using VV = vector<V>; using VVll = vector<Vll>; using VVld = vector<Vld>; using VVbo = vector<Vbo>; using VVV = vector<VV>; using VVVll = vector<VVll>; using P = pair<int, int>; using Pll = pair<ll, ll>; using Pld = pair<ld, ld>; #define rep2(i, m, n) for(int i=int(m); i<int(n); ++i) #define drep2(i, m, n) for(int i=int(m)-1; i>=int(n); --i) #define rep(i, n) rep2(i, 0, n) #define drep(i, n) drep2(i, n, 0) #define all(a) a.begin(), a.end() struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_; template<typename T> inline int sz(T &x) { return x.size(); } template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } template<typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; } template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { os << "(" << p.first << ", " << p.second << ")"; return os; } template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &e : v) is >> e; return is; } template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << " "; return os; } template<typename T> inline int count_between(vector<T> &a, T l, T r) { return lower_bound(all(a), r) - lower_bound(all(a), l); } // [l, r) inline int fLog2(const int x) { return 31-__builtin_clz(x); } // floor(log2(x)) inline int fLog2(const ll x) { return 63-__builtin_clzll(x); } inline int cLog2(const int x) { return (x == 1) ? 0 : 32-__builtin_clz(x-1); } // ceil(log2(x)) inline int cLog2(const ll x) { return (x == 1) ? 0 : 64-__builtin_clzll(x-1); } inline int popcount(const int x) { return __builtin_popcount(x); } inline int popcount(const ll x) { return __builtin_popcountll(x); } const int INF = 1<<30; const ll INFll = 1ll<<62; const ld EPS = 1e-10; const ld PI = acos(-1.0); // const int MOD = int(1e9)+7; const int MOD = 998244353; const int root = 3; int add(const int x, const int y) { return (x + y < MOD) ? x + y : x + y - MOD; } int sub(const int x, const int y) { return (x >= y) ? (x - y) : (MOD - y + x); } int mul(const int x, const int y) { return ll(x) * y % MOD; } int mod_pow(int x, int n) { int res = 1; for (; n > 0; n >>= 1){ if (n&1) res = mul(res, x); x = mul(x, x); } return res; } int inverse(const int x) { return mod_pow(x, MOD - 2); } void ntt(V &a, const bool rev = false) { int i, j, k, l, p, q, r, s; const int size = a.size(); if (size == 1) return; V b(size); r = rev ? (MOD - 1 - (MOD - 1) / size) : (MOD - 1) / size; s = mod_pow(root, r); V kp(size / 2 + 1, 1); for (i = 0; i < size / 2; ++i) kp[i + 1] = mul(kp[i], s); for (i = 1, l = size / 2; i < size; i <<= 1, l >>= 1) { for (j = 0, r = 0; j < l; ++j, r += i) { for (k = 0, s = kp[i * j]; k < i; ++k) { p = a[k + r], q = a[k + r + size / 2]; b[k + 2 * r] = add(p, q); b[k + 2 * r + i] = mul(sub(p, q), s); } } swap(a, b); } if (rev) { s = inverse(size); for(i = 0; i < size; i++){ a[i] = mul(a[i], s); } } } void conv(V &a, V b) { const int size = sz(a) + sz(b) - 1; int t = 1<<cLog2(size); a.resize(t); ntt(a); b.resize(t); ntt(b); rep(i, t) a[i] = mul(a[i], b[i]); ntt(a, true); a.resize(size); } V shift(V poly, int c) { int n = poly.size(); V inv(n + 1), fact(n + 1), invfact(n + 1); inv[1] = invfact[1] = invfact[0] = fact[0] = fact[1] = 1; for (int i = 2; i <= n; i++) { fact[i] = mul(fact[i - 1], i); inv[i] = mul(inv[MOD % i], MOD - MOD / i); invfact[i] = mul(invfact[i - 1], inv[i]); } for (int i = 0; i < poly.size(); i++) { poly[i] = mul(poly[i], fact[i]); } int val = 1; V shifting(n); for (int i = 0; i < n; i++) { shifting[n - i - 1] = mul(val, invfact[i]); val = mul(val, c); } conv(poly, shifting); V ans(n); for (int i = 0; i < n; i++) { ans[i] = mul(poly[n - 1 + i], invfact[i]); } return ans; } int main() { int n, c; cin >> n >> c; V poly(n); cin >> poly; auto ans = shift(poly, c); cout << ans << '\n'; return 0; }