Submit Info #18549

Problem Lang User Status Time Memory
Polynomial Taylor Shift cpp opt AC 183 ms 22.72 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.36 MiB
example_01 AC 1 ms 0.67 MiB
fft_killer_00 AC 183 ms 22.71 MiB
fft_killer_01 AC 182 ms 22.72 MiB
max_random_00 AC 180 ms 22.72 MiB
max_random_01 AC 180 ms 22.72 MiB
medium_00 AC 2 ms 0.75 MiB
medium_01 AC 3 ms 0.94 MiB
medium_02 AC 3 ms 0.92 MiB
medium_all_zero_00 AC 1 ms 0.67 MiB
medium_c_zero_00 AC 1 ms 0.79 MiB
random_00 AC 160 ms 20.16 MiB
random_01 AC 170 ms 21.50 MiB
random_02 AC 21 ms 3.13 MiB
small_00 AC 1 ms 0.67 MiB
small_01 AC 2 ms 0.67 MiB
small_02 AC 1 ms 0.61 MiB
small_03 AC 1 ms 0.64 MiB
small_04 AC 1 ms 0.67 MiB
small_05 AC 1 ms 0.67 MiB
small_06 AC 2 ms 0.67 MiB
small_07 AC 1 ms 0.67 MiB
small_08 AC 2 ms 0.67 MiB
small_09 AC 1 ms 0.62 MiB
small_10 AC 1 ms 0.62 MiB
small_11 AC 1 ms 0.66 MiB
small_12 AC 1 ms 0.67 MiB
small_13 AC 0 ms 0.64 MiB
small_14 AC 2 ms 0.67 MiB
small_15 AC 1 ms 0.67 MiB

#include <bits/stdc++.h> 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 MOD = 998244353; const int proot = 3; // pairs of mod and root // (924844033, 5) // (998244353, 3) // (1012924417, 5) // (167772161, 3) // (469762049, 3) // (1224736769, 3) template<int MOD> struct ModInt { int x; ModInt(int _x = 0) : x( (0 <= _x && _x < MOD) ? _x : (_x%MOD+MOD)%MOD) {} constexpr int &value() noexcept { return x; } constexpr ModInt operator-() const noexcept { return ModInt(MOD-x); } constexpr ModInt operator+(const ModInt y) const noexcept { return ModInt(*this) += y; } constexpr ModInt operator-(const ModInt y) const noexcept { return ModInt(*this) -= y; } constexpr ModInt operator*(const ModInt y) const noexcept { return ModInt(*this) *= y; } constexpr ModInt operator/(const ModInt y) const noexcept { return ModInt(*this) /= y; } constexpr ModInt &operator+=(const ModInt y) noexcept { x += y.x; if (x >= MOD) x -= MOD; return *this; } constexpr ModInt &operator-=(const ModInt y) noexcept { x -= y.x; if (x < 0) x += MOD; return *this; } constexpr ModInt &operator*=(const ModInt y) noexcept { x = ll(x) * y.x % MOD; return *this; } constexpr ModInt &operator/=(const ModInt y) noexcept { x = ll(x) * y.inv().x % MOD; return *this; } constexpr ModInt inv() const noexcept { int a = x, b = MOD, u = 1, v = 0; while (b) { int t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } return (u < 0 ? (u + MOD) : u); } }; using mint = ModInt<MOD>; using Vm = vector<mint>; using VVm = vector<Vm>; using VVVm = vector<VVm>; istream &operator>>(istream &is, mint &a) { return is >> a.x; } ostream &operator<<(ostream &os, const mint &a) { return os << a.x; } mint pow(mint a, ll n) { mint x(1); for (; n > 0; n /= 2, a *= a) if (n&1) x *= a; return x; } void ntt(Vm &f, const bool is_inv = false) { const int n = sz(f); const mint root = is_inv ? mint(proot).inv() : proot; Vm g(n); for (int b = n/2; b > 0; b /= 2) { mint a = pow(root, (MOD-1) / (n/b)); mint p = 1; for (int i = 0; i < n; i += 2*b) { rep(j, b) { f[i+j+b] *= p; g[(i>>1)+j] = f[i+j] + f[i+j+b]; g[(n>>1)+(i>>1)+j] = f[i+j] - f[i+j+b]; } p *= a; } swap(f, g); } if (is_inv) { mint in = mint(n).inv(); rep(i, n) f[i] *= in; } } void conv(Vm &a, Vm 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] = a[i] * b[i]; ntt(a, true); a.resize(size); } Vm shift(Vm poly, int c) { int n = poly.size(); Vm 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] = fact[i - 1] * i; inv[i] = inv[MOD % i] * (MOD - MOD / i); invfact[i] = invfact[i - 1] * inv[i]; } for (int i = 0; i < poly.size(); i++) { poly[i] = poly[i] * fact[i]; } mint val = 1; Vm shifting(n); for (int i = 0; i < n; i++) { shifting[n - i - 1] = invfact[i] * val; val *= c; } conv(poly, shifting); Vm ans(n); for (int i = 0; i < n; i++) { ans[i] = poly[n - 1 + i] * invfact[i]; } return ans; } int main() { int n, c; cin >> n >> c; Vm poly(n); cin >> poly; auto ans = shift(poly, c); cout << ans << '\n'; return 0; }