Submit Info #38961

Problem Lang User Status Time Memory
Log of Formal Power Series cpp cjj490168650 AC 593 ms 32.23 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.62 MiB
max_all_zero_00 AC 582 ms 32.23 MiB
max_random_00 AC 591 ms 32.13 MiB
max_random_01 AC 593 ms 32.13 MiB
max_random_02 AC 592 ms 32.13 MiB
max_random_03 AC 590 ms 32.19 MiB
max_random_04 AC 585 ms 32.19 MiB
near_262144_00 AC 231 ms 16.65 MiB
near_262144_01 AC 224 ms 16.66 MiB
near_262144_02 AC 498 ms 28.15 MiB
random_00 AC 575 ms 29.82 MiB
random_01 AC 580 ms 31.39 MiB
random_02 AC 46 ms 4.47 MiB
random_03 AC 574 ms 30.68 MiB
random_04 AC 543 ms 27.56 MiB
small_degree_00 AC 0 ms 0.62 MiB
small_degree_01 AC 1 ms 0.65 MiB
small_degree_02 AC 3 ms 0.68 MiB
small_degree_03 AC 1 ms 0.67 MiB
small_degree_04 AC 1 ms 0.68 MiB
small_degree_05 AC 0 ms 0.62 MiB
small_degree_06 AC 1 ms 0.67 MiB
small_degree_07 AC 1 ms 0.62 MiB
small_degree_08 AC 1 ms 0.67 MiB
small_degree_09 AC 1 ms 0.61 MiB

#include <bits/stdc++.h> using namespace std; namespace NTT { const int P=998244353,g=3; const int W=22,S=1<<W; const int J=86583718; inline int add(int a,int b) {int r=a+b; return r<P?r:r-P;} inline int sub(int a,int b) {int r=a-b; return r<0?r+P:r;} inline int mul(long long a,long long b) {return (a*b)%P;} inline int inv(int a) {return a==1?a:mul(inv(P%a),P-P/a);} inline int qpow(int a,long long k) { int r=1; while (k) { if (k&1) r=mul(r,a); k>>=1; a=mul(a,a); } return r; } const int i2=inv(2),ij=inv(J); int r[S],w[2][S]; void init(int lim) { int w0=qpow(g,(P-1)/lim); w[0][0]=w[1][0]=1; for (int i=1;i<lim;i++) w[0][i]=w[1][lim-i]=mul(w[0][i-1],w0); for (int i=0;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)*(lim>>1)); } void ntt(int *a,int lim,int o) { for (int i=0;i<lim;i++) if (i<r[i]) swap(a[i],a[r[i]]); for (int i=1;i<lim;i<<=1) { for (int j=0,t=lim/(i<<1);j<lim;j+=i<<1) { for (int k=j,l=0;k<j+i;k++,l+=t) { int x=a[k],y=mul(w[o][l],a[k+i]); a[k]=add(x,y); a[k+i]=sub(x,y); } } } if (o) { int tmp=NTT::inv(lim); for (int i=0;i<lim;i++) a[i]=mul(a[i],tmp); } } vector<int> poly_add(const vector<int> &a,const vector<int> &b) { int n=a.size(),m=b.size(); vector<int> c; for (int i=0;i<max(n,m);i++) c.push_back(add((i<n?a[i]:0),(i<m?b[i]:0))); return c; } vector<int> poly_sub(const vector<int> &a,const vector<int> &b) { int n=a.size(),m=b.size(); vector<int> c; for (int i=0;i<max(n,m);i++) c.push_back(sub((i<n?a[i]:0),(i<m?b[i]:0))); return c; } vector<int> poly_d(const vector<int> &a) { int n=a.size(); vector<int> b; for (int i=1;i<n;i++) b.push_back(mul(a[i],i)); return b; } vector<int> poly_s(const vector<int> &a) { int n=a.size(); vector<int> b{0}; for (int i=0;i<n;i++) b.push_back(mul(a[i],inv(i+1))); return b; } int p1[S],p2[S]; vector<int> poly_mul(const vector<int> &a,const vector<int> &b) { int n=a.size(),m=b.size(); int lim=1; while (lim<(n<<1)) lim<<=1; while (lim<(m<<1)) lim<<=1; init(lim); copy_n(a.begin(),n,p1); fill(p1+n,p1+lim,0); copy_n(b.begin(),m,p2); fill(p2+m,p2+lim,0); ntt(p1,lim,0); ntt(p2,lim,0); for (int i=0;i<lim;i++) p1[i]=mul(p1[i],p2[i]); ntt(p1,lim,1); return vector<int>(p1,p1+n+m-1); } vector<int> poly_inv(const vector<int> &a) { int n=a.size(); if (n==1) return {inv(a[0])}; auto b=a; b.resize((n+1)>>1); b=poly_inv(b); int m=b.size(); int lim=1; while (lim<(n<<1)) lim<<=1; while (lim<(m<<1)) lim<<=1; init(lim); copy_n(a.begin(),n,p1); fill(p1+n,p1+lim,0); copy_n(b.begin(),m,p2); fill(p2+m,p2+lim,0); ntt(p1,lim,0); ntt(p2,lim,0); for (int i=0;i<lim;i++) p1[i]=mul(p2[i],sub(2,mul(p1[i],p2[i]))); ntt(p1,lim,1); return vector<int>(p1,p1+n); } vector<int> poly_div(const vector<int> &a,const vector<int> &b) { int n=a.size(),m=b.size(); if (m>n) return {0}; auto ar=a,br=b; reverse(ar.begin(),ar.end()); reverse(br.begin(),br.end()); ar.resize(n-m+1); br.resize(n-m+1); br=poly_inv(br); auto q=poly_mul(ar,br); q.resize(n-m+1); reverse(q.begin(),q.end()); return q; } vector<int> poly_mod(const vector<int> &a,const vector<int> &b) { int m=b.size(); auto c=poly_div(a,b); c=poly_mul(b,c); c=poly_sub(a,c); c.resize(m-1); return c; } vector<int> poly_sqrt(const vector<int> &a) { int n=a.size(); if (n==1) return {1}; auto b=a; b.resize((n+1)>>1); b=poly_sqrt(b); b.resize(n); auto c=poly_add(b,poly_mul(poly_inv(b),a)); c.resize(n); for (int &i:c) i=mul(i,i2); return c; } vector<int> poly_ln(const vector<int> &a) { int n=a.size(); auto b=poly_mul(poly_inv(a),poly_d(a)); b.resize(n-1); b=poly_s(b); return b; } vector<int> poly_exp(const vector<int> &a) { int n=a.size(); if (n==1) return {1}; auto b=a; b.resize((n+1)>>1); b=poly_exp(b); b.resize(n); auto c=poly_sub(a,poly_ln(b)); c[0]=add(c[0],1); c=poly_mul(b,c); c.resize(n); return c; } vector<int> poly_sin(const vector<int> &a) { auto b=a; for (int &i:b) i=mul(i,J); auto c=poly_exp(b); c=poly_sub(c,poly_inv(c)); for (int &i:c) i=mul(i,mul(i2,ij)); return c; } vector<int> poly_cos(const vector<int> &a) { auto b=a; for (int &i:b) i=mul(i,J); auto c=poly_exp(b); c=poly_add(c,poly_inv(c)); for (int &i:c) i=mul(i,i2); return c; } vector<int> poly_asin(const vector<int> &a) { int n=a.size(); auto b=poly_d(a),c=poly_mul(a,a); c.resize(n); c=poly_inv(poly_sqrt(poly_sub({1},c))); b=poly_mul(b,c); b.resize(n-1); return poly_s(b); } vector<int> poly_atan(const vector<int> &a) { int n=a.size(); auto b=poly_d(a),c=poly_mul(a,a); c.resize(n); c=poly_inv(poly_add({1},c)); b=poly_mul(b,c); b.resize(n-1); return poly_s(b); } } int read_int() { int re=0; char c=0; bool sgn=false; while (!isdigit(c) && c!='-') c=getchar(); if (c=='-') sgn=true,c=getchar(); while (isdigit(c)) {re=re*10+c-'0'; c=getchar();} return sgn?-re:re; } int main() { int n=read_int(); vector<int> a; for (int i=0;i<n;i++) a.push_back(read_int()); auto b=NTT::poly_ln(a); for (int i:b) printf("%d ",i); getchar(); getchar(); return 0; }