Submit Info #58392

Problem Lang User Status Time Memory
Polynomial Taylor Shift cpp-acl Kude AC 149 ms 20.47 MiB

ケース詳細
Name Status Time Memory
example_00 AC 6 ms 4.45 MiB
example_01 AC 6 ms 4.45 MiB
fft_killer_00 AC 149 ms 20.43 MiB
fft_killer_01 AC 148 ms 20.46 MiB
max_random_00 AC 149 ms 20.47 MiB
max_random_01 AC 149 ms 20.44 MiB
medium_00 AC 7 ms 4.45 MiB
medium_01 AC 8 ms 4.70 MiB
medium_02 AC 7 ms 4.70 MiB
medium_all_zero_00 AC 7 ms 4.45 MiB
medium_c_zero_00 AC 7 ms 4.44 MiB
random_00 AC 130 ms 18.31 MiB
random_01 AC 140 ms 19.43 MiB
random_02 AC 21 ms 6.24 MiB
small_00 AC 6 ms 4.45 MiB
small_01 AC 6 ms 4.45 MiB
small_02 AC 6 ms 4.45 MiB
small_03 AC 6 ms 4.44 MiB
small_04 AC 6 ms 4.32 MiB
small_05 AC 6 ms 4.41 MiB
small_06 AC 6 ms 4.45 MiB
small_07 AC 6 ms 4.45 MiB
small_08 AC 6 ms 4.45 MiB
small_09 AC 6 ms 4.45 MiB
small_10 AC 6 ms 4.45 MiB
small_11 AC 6 ms 4.42 MiB
small_12 AC 6 ms 4.45 MiB
small_13 AC 6 ms 4.45 MiB
small_14 AC 6 ms 4.44 MiB
small_15 AC 6 ms 4.40 MiB

#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; #define rep(i,n)for (int i = 0; i < int(n); ++i) #define rrep(i,n)for (int i = int(n)-1; i >= 0; --i) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() template<class T> void chmax(T& a, const T& b) {a = max(a, b);} template<class T> void chmin(T& a, const T& b) {a = min(a, b);} using ll = long long; using P = pair<int,int>; using VI = vector<int>; using VVI = vector<VI>; using VL = vector<ll>; using VVL = vector<VL>; using mint = modint998244353; constexpr int FACT_SIZE = 524288; mint Fact[FACT_SIZE + 1]; mint iFact[FACT_SIZE + 1]; const auto fact_init = [] { Fact[0] = mint::raw(1); for(int i = 1; i <= FACT_SIZE; ++i) { Fact[i] = Fact[i-1] * i; } iFact[FACT_SIZE] = Fact[FACT_SIZE].inv(); for(int i = FACT_SIZE; i; --i) { iFact[i-1] = iFact[i] * i; } return false; }(); vector<mint> Taylor_Shift(vector<mint> f, mint c) { const int n = f.size(); for(int k = 0; k < n; k++) f[k] *= Fact[k]; vector<mint> g(n); mint ck = 1; for(int k = 0; k < n; k++, ck *= c) { g[n - 1 - k] = ck * iFact[k]; } auto h = convolution(f, g); for(int k = 0; k < n; k++) h[k] = h[n - 1 + k] * iFact[k]; h.resize(n); return h; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, c; cin >> n >> c; vector<mint> a(n); rep(i, n) { int x; cin >> x; a[i] = x; } auto ac = Taylor_Shift(a, c); rep(i, n) cout << ac[i].val() << " \n"[i + 1 == n]; }