Submit Info #24135

Problem Lang User Status Time Memory
Polynomial Taylor Shift cpp (anonymous) AC 188 ms 32.79 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.61 MiB
example_01 AC 1 ms 0.64 MiB
fft_killer_00 AC 188 ms 32.73 MiB
fft_killer_01 AC 181 ms 32.79 MiB
max_random_00 AC 183 ms 32.64 MiB
max_random_01 AC 182 ms 32.73 MiB
medium_00 AC 3 ms 0.80 MiB
medium_01 AC 3 ms 1.16 MiB
medium_02 AC 3 ms 1.17 MiB
medium_all_zero_00 AC 2 ms 0.49 MiB
medium_c_zero_00 AC 2 ms 0.80 MiB
random_00 AC 166 ms 30.18 MiB
random_01 AC 173 ms 31.63 MiB
random_02 AC 22 ms 4.51 MiB
small_00 AC 2 ms 0.67 MiB
small_01 AC 2 ms 0.68 MiB
small_02 AC 1 ms 0.66 MiB
small_03 AC 1 ms 0.36 MiB
small_04 AC 1 ms 0.67 MiB
small_05 AC 1 ms 0.68 MiB
small_06 AC 1 ms 0.66 MiB
small_07 AC 1 ms 0.64 MiB
small_08 AC 1 ms 0.67 MiB
small_09 AC 2 ms 0.65 MiB
small_10 AC 1 ms 0.62 MiB
small_11 AC 3 ms 0.61 MiB
small_12 AC 1 ms 0.65 MiB
small_13 AC 0 ms 0.67 MiB
small_14 AC 2 ms 0.67 MiB
small_15 AC 2 ms 0.67 MiB

#pragma GCC optimize(3,"Ofast","inline") #include <bits/stdc++.h> using namespace std; const int MOD = 998244353; struct mod_int { int val; mod_int(long long v = 0) { if (v < 0) v = v % MOD + MOD; if (v >= MOD) v %= MOD; val = v; } static int mod_inv(int a, int m = MOD) { // https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Example int g = m, r = a, x = 0, y = 1; while (r != 0) { int q = g / r; g %= r; swap(g, r); x -= q * y; swap(x, y); } return x < 0 ? x + m : x; } explicit operator int() const { return val; } explicit operator uint64_t()const{ return val; } mod_int& operator+=(const mod_int &other) { val += other.val; if (val >= MOD) val -= MOD; return *this; } mod_int& operator-=(const mod_int &other) { val -= other.val; if (val < 0) val += MOD; return *this; } static unsigned fast_mod(uint64_t x, unsigned m = MOD) { return x % m; /* // Optimized mod for Codeforces 32-bit machines. // x must be less than 2^32 * m for this to work, so that x / m fits in a 32-bit integer. unsigned x_high = x >> 32, x_low = (unsigned) x; unsigned quot, rem; asm("divl %4\n" : "=a" (quot), "=d" (rem) : "d" (x_high), "a" (x_low), "r" (m)); return rem;*/ } mod_int& operator*=(const mod_int &other) { val = fast_mod((uint64_t) val * other.val); return *this; } mod_int& operator/=(const mod_int &other) { return *this *= other.inv(); } friend mod_int operator+(const mod_int &a, const mod_int &b) { return mod_int(a) += b; } friend mod_int operator-(const mod_int &a, const mod_int &b) { return mod_int(a) -= b; } friend mod_int operator*(const mod_int &a, const mod_int &b) { return mod_int(a) *= b; } friend mod_int operator/(const mod_int &a, const mod_int &b) { return mod_int(a) /= b; } mod_int& operator++() { val = val == MOD - 1 ? 0 : val + 1; return *this; } mod_int& operator--() { val = val == 0 ? MOD - 1 : val - 1; return *this; } mod_int operator++(int) { mod_int before = *this; ++*this; return before; } mod_int operator--(int) { mod_int before = *this; --*this; return before; } mod_int operator-() const { return val == 0 ? 0 : MOD - val; } bool operator==(const mod_int &other) const { return val == other.val; } bool operator!=(const mod_int &other) const { return val != other.val; } mod_int inv() const { return mod_inv(val); } mod_int pow(long long p) const { assert(p >= 0); mod_int a = *this, result = 1; while (p > 0) { if (p & 1) result *= a; a *= a; p >>= 1; } return result; } friend ostream& operator<<(ostream &stream, const mod_int &m) { return stream << m.val; } }; //#define mod_int MontgomeryModInt32<MOD> void debug(vector<mod_int> a){ for(auto i:a)cerr<<i<<' '; cerr<<endl; } void r_debug(vector<mod_int> a){ for(auto i:a)cerr<<1/i<<' '; cerr<<endl; } vector<mod_int> inv, factorial, inv_factorial; void prepare_factorials(int maximum) { if(maximum+1<inv.size())return; inv.assign(maximum + 1, 1); // Make sure MOD is prime, which is necessary for the inverse algorithm below. for (int p = 2; p * p <= MOD; p++) assert(MOD % p != 0); for (int i = 2; i <= maximum; i++) inv[i] = inv[MOD % i] * (MOD - MOD / i); factorial.resize(maximum + 1); inv_factorial.resize(maximum + 1); factorial[0] = inv_factorial[0] = 1; for (int i = 1; i <= maximum; i++) { factorial[i] = i * factorial[i - 1]; inv_factorial[i] = inv[i] * inv_factorial[i - 1]; } } inline mod_int C(int n,int m){ assert(n>=m);assert(n<factorial.size()); return factorial[n]*inv_factorial[m]*inv_factorial[n-m]; } namespace NTT { vector<mod_int> roots = {0, 1}; vector<int> bit_reverse; int max_size = -1; mod_int root; bool is_power_of_two(int n) { return (n & (n - 1)) == 0; } int round_up_power_two(int n) { assert(n > 0); while (n & (n - 1)) n = (n | (n - 1)) + 1; return n; } // Given n (a power of two), finds k such that n == 1 << k. int get_length(int n) { assert(is_power_of_two(n)); return __builtin_ctz(n); } // Rearranges the indices to be sorted by lowest bit first, then second lowest, etc., rather than highest bit first. // This makes even-odd div-conquer much easier. void bit_reorder(int n, vector<mod_int> &values) { if ((int) bit_reverse.size() != n) { bit_reverse.assign(n, 0); int length = get_length(n); for (int i = 0; i < n; i++) bit_reverse[i] = (bit_reverse[i >> 1] >> 1) + ((i & 1) << (length - 1)); } for (int i = 0; i < n; i++) if (i < bit_reverse[i]) swap(values[i], values[bit_reverse[i]]); } void find_root() { int order = MOD - 1; max_size = 1; while (order % 2 == 0) { order /= 2; max_size *= 2; } root = 2; // Find a max_size-th primitive root of MOD. while (!((int)root.pow(max_size) == 1 && (int)root.pow(max_size / 2) != 1)) root=root+1; } void prepare_roots(int n) { if (max_size < 0) find_root(); assert(n <= max_size); if ((int) roots.size() >= n) return; int length = get_length(roots.size()); roots.resize(n); // The roots array is set up such that for a given power of two n >= 2, roots[n / 2] through roots[n - 1] are // the first half of the n-th primitive roots of MOD. while (1 << length < n) { // z is a 2^(length + 1)-th primitive root of MOD. mod_int z = root.pow(max_size >> (length + 1)); for (int i = 1 << (length - 1); i < 1 << length; i++) { roots[2 * i] = roots[i]; roots[2 * i + 1] = roots[i] * z; } length++; } } void fft_iterative(int N, vector<mod_int> &values) { assert(is_power_of_two(N)); prepare_roots(N); bit_reorder(N, values); for (int n = 1; n < N; n *= 2) for (int start = 0; start < N; start += 2 * n) for (int i = 0; i < n; i++) { mod_int even = values[start + i]; mod_int odd = values[start + n + i] * roots[n + i]; values[start + n + i] = even - odd; values[start + i] = even + odd; } } const int FFT_CUTOFF = 150; vector<mod_int> mod_multiply(vector<mod_int> left, vector<mod_int> right) { int n = left.size(); int m = right.size(); // Brute force when either n or m is small enough. if (min(n, m) < FFT_CUTOFF) { const uint64_t ULL_BOUND = numeric_limits<uint64_t>::max() - (uint64_t) MOD * MOD; vector<uint64_t> result(n + m - 1); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { result[i + j] += (uint64_t) ((int) left[i]) * ((int) right[j]); if (result[i + j] > ULL_BOUND) result[i + j] %= MOD; } for (uint64_t &x : result) if (x >= MOD) x %= MOD; return vector<mod_int>(result.begin(), result.end()); } int N = round_up_power_two(n + m - 1); left.resize(N); right.resize(N); fft_iterative(N, left); fft_iterative(N, right); mod_int inv_N = mod_int(N).inv(); for (int i = 0; i < N; i++) left[i] *= right[i] * inv_N; reverse(left.begin() + 1, left.end()); fft_iterative(N, left); left.resize(n + m - 1); return left; } vector<mod_int> sub_conv(vector<mod_int>a,vector<mod_int>b){ int n=b.size(); reverse(b.begin(),b.end()); auto res=mod_multiply(a,b); return vector<mod_int>(res.begin()+n-1,res.end()); } vector<mod_int> shift(vector<mod_int> a,mod_int c){ //a(x+c)=\sum x^j 1/j!\sum i!a_i c^{j-i}/(j-i)! int N=round_up_power_two(a.size()); prepare_factorials(N); vector<mod_int>tmp(a.size()); mod_int pc=1; for(int i=0;i<tmp.size();i++,pc*=c){ tmp[i]=pc*inv_factorial[i]; a[i]*=factorial[i]; } tmp=sub_conv(a,tmp); for(int i=0;i<a.size();i++){ tmp[i]*=inv_factorial[i]; } return tmp; } vector<mod_int> mod_power(const vector<mod_int> &v, int exponent) { assert(exponent >= 0); vector<mod_int> result = {1}; if (exponent == 0) return result; for (int k = 31 - __builtin_clz(exponent); k >= 0; k--) { result = mod_multiply(result, result); if (exponent >> k & 1) result = mod_multiply(result, v); } return result; } vector<mod_int> mod_inv(vector<mod_int> a){ int n=a.size(); int N=round_up_power_two(a.size()); a.resize(N*2); vector<mod_int>res={a[0].inv()}; for(int i=2;i<=N;i<<=1){ vector<mod_int>tmp(a.begin(),a.begin()+i); int n=(i<<1); res.resize(n); tmp.resize(n); fft_iterative(n,tmp); fft_iterative(n,res); mod_int inv_n=mod_int(n).inv(); for(int j=0;j<n;j++) res[j]=res[j]*(2-tmp[j]*res[j])*inv_n; reverse(res.begin()+1,res.end()); fft_iterative(n,res); fill(res.begin()+i,res.end(),0); } res.resize(n); return res; } vector<mod_int>integral(vector<mod_int> a){ assert(a.size()<=inv.size()); a.push_back(0); for(int i=(int)a.size()-1;i>=1;i--){ a[i]=a[i-1]*inv[i]; } return a; } vector<mod_int>differential(vector<mod_int> a){ assert(a.size()); for(int i=0;i<(int)a.size()-1;i++){ a[i]=a[i+1]*(i+1); } a.pop_back(); return a; } vector<mod_int>ln(vector<mod_int>a){ assert((int)a[0]==1); auto b=mod_multiply(differential(a),mod_inv(a)); b=integral(b); b[0]=0; return b; } vector<mod_int>exp(vector<mod_int>a){ int N=round_up_power_two(a.size()); int n=a.size(); a.resize(N*2); vector<mod_int>res{1}; for(int i=2;i<=N;i<<=1){ auto tmp=res; tmp.resize(i); tmp=ln(tmp); for(int j=0;j<i;j++)tmp[j]=a[j]-tmp[j]; tmp[0]+=1; res.resize(i); res=mod_multiply(res,tmp); fill(res.begin()+i,res.end(),0); } res.resize(n); return res; } vector<mod_int> poly_div(vector<mod_int>a,vector<mod_int>b){ if(a.size()<b.size()){ return {0}; } reverse(a.begin(),a.end()); reverse(b.begin(),b.end()); b.resize(a.size()-b.size()+1); a.resize(b.size()); auto d=mod_multiply(mod_inv(b),a); d.resize(b.size()); reverse(d.begin(),d.end()); return d; } vector<mod_int> poly_mod(vector<mod_int>a,vector<mod_int>b){ auto res=mod_multiply(b,poly_div(a,b)); a.resize(b.size()-1); res.resize(b.size()-1); for(int i=0;i<a.size();i++){ a[i]-=res[i]; } return a; } mod_int eval(const vector<mod_int>&f,int x){ mod_int ans; for(int i=f.size()-1;i>=0;i--) ans=(ans*x+f[i]); return ans; } vector<mod_int> mod_multiply_all(const vector<vector<mod_int>> &polynomials) { if (polynomials.empty()) return {1}; struct compare_size { bool operator()(const vector<mod_int> &x, const vector<mod_int> &y) { return x.size() > y.size(); } }; priority_queue<vector<mod_int>, vector<vector<mod_int>>, compare_size> pq(polynomials.begin(), polynomials.end()); while (pq.size() > 1) { vector<mod_int> a = pq.top(); pq.pop(); vector<mod_int> b = pq.top(); pq.pop(); pq.push(mod_multiply(a, b)); } return pq.top(); } mod_int linear_seq(const vector<mod_int>& _init, vector<mod_int> seq,long long n){ //a_n=sum seq_i * a_n-i reverse(seq.begin(),seq.end()); for(auto& i:seq)i=-i;seq.push_back(1); vector<mod_int>b=seq; reverse(b.begin(),b.end()); b=mod_inv(b); auto poly_mod=[&](vector<mod_int>a){ if(a.size()<seq.size()){ a.resize(seq.size()-1); return a; } vector<mod_int>tmp=a; reverse(a.begin(),a.end()); b.resize(a.size()-seq.size()+1); a.resize(b.size()); auto d=mod_multiply(b,a); d.resize(b.size()); reverse(d.begin(),d.end()); auto res=mod_multiply(seq,d); tmp.resize(seq.size()-1); res.resize(seq.size()-1); for(int i=0;i<tmp.size();i++){ tmp[i]-=res[i]; } return tmp; }; vector<mod_int>a{0,1}; vector<mod_int>res{1}; for(;n;n>>=1){ if(n&1){ res=poly_mod(mod_multiply(res,a)); } a=poly_mod(mod_multiply(a,a)); } mod_int ans=0; for(int i=0;i<_init.size();i++){ ans+=_init[i]*res[i]; } return ans; } vector<mod_int> multi_eval(vector<mod_int> F,vector<mod_int> x){ vector<vector<mod_int>>base; function<void(int,int,int)> build=[&](int l,int r,int o){ if(r-l==1){ base[o]={1,-x[l]}; return; } int mid=(l+r)>>1; build(l,mid,o<<1); build(mid,r,o<<1|1); base[o]=(mod_multiply(base[o<<1],base[o<<1|1])); }; vector<mod_int>res(x.size()); int n=max(x.size(),F.size()); x.resize(n);F.resize(n+1); base.resize(4*n); build(0,n,1); function<void(vector<mod_int>,int,int,int)>solve=[&](vector<mod_int> f,int l,int r,int o){ if(r-l==1){ if(l<res.size())res[l]=f[0]; return; } int mid=(l+r)>>1; auto L=sub_conv(f,base[o<<1|1]); auto R=sub_conv(f,base[o<<1]); L.resize(mid-l); R.resize(r-mid); solve(L,l,mid,o<<1); solve(R,mid,r,o<<1|1); }; solve(sub_conv(F,mod_inv(base[1])),0,n,1); return res; } vector<mod_int> multi_inter(const vector<mod_int>& y,const vector<mod_int>& x){ assert(y.size()==x.size()); vector<vector<mod_int>>base; function<void(int,int,int)> build=[&](int l,int r,int o){ if(r-l==1){ base[o]={-x[l],1}; return; } int mid=(l+r)>>1; build(l,mid,o<<1); build(mid,r,o<<1|1); base[o]=(mod_multiply(base[o<<1],base[o<<1|1])); }; int n=x.size(); base.resize(4*n); int s=clock(); build(0,n,1); vector<mod_int>pi=differential(base[1]); vector<mod_int>res=multi_eval(pi,x); for(int i=0;i<n;i++)res[i]=y[i]/res[i]; function<vector<mod_int>(int,int,int)>solve2=[&](int l,int r,int o){ if(r-l==1){ return vector<mod_int>({res[l]}); } int mid=(l+r)>>1; vector<mod_int>L=mod_multiply(solve2(l,mid,o<<1),base[o<<1|1]); vector<mod_int>R=mod_multiply(solve2(mid,r,o<<1|1),base[o<<1]); int n=max(L.size(),R.size()); L.resize(n);R.resize(n); for(int i=0;i<n;i++){ L[i]+=R[i]; } return L; }; auto ans=solve2(0,n,1); ans.resize(n); return ans; } } vector<mod_int> gen(int n){ vector<mod_int>v; for(int i=0;i<n;i++)v.push_back(rand()+1); return v; } int main(){ ios::sync_with_stdio(false); int n,c; cin>>n>>c; vector<mod_int>a(n); for(auto& i:a){ cin>>i.val; } for(auto& i:NTT::shift(a,c)){ cout<<i<<' '; } }