Submit Info #36713

Problem Lang User Status Time Memory
Stirling Number of the First Kind cpp amusement AC 435 ms 26.19 MiB

ケース詳細
Name Status Time Memory
0_00 AC 2 ms 0.67 MiB
1_00 AC 1 ms 0.62 MiB
262143_00 AC 189 ms 13.73 MiB
262144_00 AC 398 ms 17.21 MiB
2_00 AC 1 ms 0.67 MiB
491519_00 AC 433 ms 25.76 MiB
499999_00 AC 435 ms 26.19 MiB
500000_00 AC 433 ms 24.11 MiB
5000_00 AC 5 ms 0.98 MiB
example_00 AC 1 ms 0.66 MiB

//#pragma GCC target("avx512f,avx512dq,avx512cd,avx512bw,avx512vl") /*#pragma GCC target("avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops")*/ #include <bits/stdc++.h> using namespace std; #define LL long long #define DB double #define LD long double #define ST string #define BS bitset #define PA pair<LL,LL> #define VE vector #define VL VE<LL> #define VP VE<PA> #define VVL VE<VL> #define VVVL VE<VVL> #define PQ priority_queue #define PQS priority_queue<LL,vector<LL>,greater<LL>> #define FI first #define SE second #define PB push_back #define POB pop_back #define PF push_front #define POF pop_front #define MP make_pair #define TS to_string #define TU to_ullong #define BPL __builtin_popcountll #define FOR(i,a,n) for(i=a;i<n;++i) #define FORR(i,a,n) for(i=n-1;i>=a;--i) #define rep(i,n) FOR(i,0,n) #define repr(i,n) FORR(i,0,n) #define ALL(a) a.begin(),a.end() #define RALL(a) a.rbegin(),a.rend() #define SORT(a) sort(ALL(a)) #define REV(a) reverse(ALL(a)) #define UB(a,n) *upper_bound(ALL(a),n) #define UBn(a,n) upper_bound(ALL(a),n)-a.begin() #define LB(a,n) *lower_bound(ALL(a),n) #define LBn(a,n) lower_bound(ALL(a),n)-a.begin() #define INF 1000000000000000003 #define PI 3.14159265358979323846264338327950288 //#define MOD 1000000007 #define MOD 998244353 #define ERR 1e-10 #define coutl cout<<fixed<<setprecision(15) #define FAST cin.tie(0);ios::sync_with_stdio(false) void Yn(LL a){if(a)cout<<"Yes"<<endl;else cout<<"No"<<endl;} void YN(LL a){if(a)cout<<"YES"<<endl;else cout<<"NO"<<endl;} LL pwmn(LL a,LL n){LL ans=1;while(ans<a)ans*=n;return ans;} LL dig(LL n){LL ret=0;while(n)n/=10,++ret;return ret;} LL GCD(LL a,LL b){LL c=1,tmp=max(a,b);b=min(a,b);a=tmp;while(c!=0){c=a%b;a=b;b=c;}return a;} LL LCM(LL a,LL b){return a*b/GCD(a,b);} LL cmod(LL a,LL m){if(a%m<0)return a%m+abs(m);else return a%m;} LL DIV(LL a,LL d,LL m){LL l=m,x=1,y=0,k;while(l){k=d/l;d-=k*l;swap(l,d);x-=k*y;swap(x,y);}return cmod(a*cmod(x,m),m);} LL POW(LL a,LL n,LL m){LL ans=1;while(n>0){if(n&1)ans=ans*a%m;a=a*a%m;n>>=1;}return ans;} VL fact,finv,inv; void comi(LL n){LL i;fact.resize(max(2LL,n+1));finv.resize(max(2LL,n+1));inv.resize(max(2LL,n+1));fact[0]=fact[1]=1;finv[0]=finv[1]=1;inv[0]=inv[1]=1;FOR(i,2,n+1){fact[i]=fact[i-1]*i%MOD;inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;finv[i]=finv[i-1]*inv[i]%MOD;}} LL com(LL n,LL k){if(n<k||n<0||k<0)return 0;return fact[n]*(finv[k]*finv[n-k]%MOD)%MOD;} bool cmps(PA a,PA b){if(a.SE!=b.SE)return a.SE<b.SE;return a.FI<b.FI;} template<typename T>bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;} template<typename T>bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;} template<typename T>void vout(VE<T> &v){LL i;rep(i,v.size()){cout<<v[i];if(i<v.size()-1)cout<<" ";}cout<<endl;} template<typename T>void v2out(VE<VE<T>> &v){for(auto a:v)vout(a);} #define MI modint<MOD> #define VM VE<MI> template<int mod>struct modint{ int x; modint():x(0){} modint(LL n):x(n>=0?n%mod:(mod-(-n)%mod)%mod){} modint &operator+=(const modint &n){if((x+=n.x-mod)<0)x+=mod;return *this;} modint &operator-=(const modint &n){if((x-=n.x)<0)x+=mod;return *this;} modint &operator++(){*this+=1;return *this;} modint &operator--(){*this-=1;return *this;} modint &operator*=(const modint &n){x=(int)((LL)x*n.x%mod);return *this;} modint &operator/=(const modint &n){*this*=n.inv();return *this;} modint operator-()const{return modint(-x);} modint operator+(const modint &n)const{return modint(*this)+=n;} modint operator-(const modint &n)const{return modint(*this)-=n;} modint operator++(int){modint ret(*this);*this+=1;return ret;} modint operator--(int){modint ret(*this);*this-=1;return ret;} modint operator*(const modint &n)const{return modint(*this)*=n;} modint operator/(const modint &n)const{return modint(*this)/=n;} bool operator<(const modint &n)const{return x<n.x;} bool operator>(const modint &n)const{return x>n.x;} bool operator<=(const modint &n)const{return x<=n.x;} bool operator>=(const modint &n)const{return x>=n.x;} bool operator!=(const modint &n)const{return x!=n.x;} bool operator==(const modint &n)const{return x==n.x;} friend istream &operator>>(istream &is,modint &n){LL l;is>>l;n=modint<mod>(l);return is;} friend ostream &operator<<(ostream &os,const modint &n){return os<<n.x;} int getmod()const{return mod;} modint inv()const{int a=x,b=mod,c=1,d=0,n;while(b){n=a/b;swap(a-=n*b,b);swap(c-=n*d,d);}return modint(c);} modint pow(LL n)const{modint ret(1),m(x);while(n){if(n&1)ret*=m;m*=m;n>>=1;}return ret;} modint log(LL n)const{n%=mod;modint e;e.x=-1;if(!n)return x==1?0:x==0?1:e;LL i,s=sqrt(mod)+ERR,k,A=POW(DIV(1,n,mod),s,mod);unordered_map<LL,LL> p;k=1;rep(i,s+1){if(!p.count(k))p[k]=i;(k*=n)%=mod;}k=x;rep(i,s+1){if(p.count(k))return i*s+p[k];(k*=A)%=mod;}return e;} modint sqrt()const{modint e;e.x=-1;if(mod==2||x<2)return x;if(pow((mod-1)/2)==mod-1)return e;if(mod%4==3)return pow((mod+1)/4);LL q=mod-1,s=0;modint k,z=1;while(q%2==0)q/=2,++s;while(++z.x)if(z.pow((mod-1)/2)==mod-1)break;LL m=s,nm;modint c=z.pow(q),t=pow(q),r=pow((q+1)/2);while(t!=1){for(nm=1,k=t*t;k!=1;k*=k,++nm);t=t*c.pow(1<<(m-nm));r=r*c.pow(1<<(m-nm-1));c=c.pow(1<<(m-nm));m=nm;}return r>-r?-r:r;} }; #define P poly<MOD> template<int mod,int root>struct NTT{ using mint=modint<mod>;using vmint=VE<mint>; vmint zeta;VE<pair<int,int>> bitrev; int getmod(){return mod;} void init(int n){int i=0,j,k;bitrev.resize(n,MP(0,0));FOR(j,1,n-1){for(k=n>>1;k>(i^=k);k>>=1);if(j<i)bitrev[j]=MP(i,j);}mint z=root;z=z.pow((mod-1)/n);zeta.resize(n>>1,1);rep(i,(n>>1)-1)zeta[i+1]=zeta[i]*z;} void ntt(vmint &f){int n=f.size(),i=0,j,k;mint a;FOR(i,1,n-1)swap(f[bitrev[i].FI],f[bitrev[i].SE]);for(i=1;i<n;i<<=1)rep(j,i)for(k=j;k<n;k+=(i<<1)){a=f[k+i]*zeta[(n>>1)/i*j];f[k+i]=f[k]-a;f[k]+=a;}} VE<int> conv(VE<int> &F,VE<int> &G,int sz){int i,sf=F.size(),sg=G.size(),s=sf+sg-1,n=pwmn(s,2);vmint f(n),g(n);rep(i,sf)f[i]=F[i];rep(i,sg)g[i]=G[i];mint d=1;d/=n;init(n);ntt(f);ntt(g);rep(i,n)f[i]*=g[i]*d;reverse(f.begin()+1,f.end());ntt(f);VE<int> ret(sz==-1?s:sz);sz=min((int)ret.size(),s);rep(i,sz)ret[i]=f[i].x;return ret;} }; template<typename mint>VE<mint> AMC(const VE<mint> &F,const VE<mint> &G,int sz=-1){VE<mint> ret;if(sz>=0)ret.resize(sz);if(F.size()==0||G.size()==0)return ret;int i,m=F[0].getmod();if(m==998244353){NTT<998244353,3> n;VE<int> f(sz==-1?F.size():min(sz,(int)F.size())),g(sz==-1?G.size():min(sz,(int)G.size()));rep(i,f.size())f[i]=F[i].x;rep(i,g.size())g[i]=G[i].x;f=n.conv(f,g,sz);if(!ret.size())ret.resize(f.size());rep(i,f.size())ret[i]=f[i];return ret;}NTT<167772161,3> n1;NTT<469762049,3> n2;NTT<595591169,3> n3; VE<int> f(sz==-1?F.size():min(sz,(int)F.size())),g(sz==-1?G.size():min(sz,(int)G.size()));rep(i,f.size())f[i]=F[i].x;rep(i,g.size())g[i]=G[i].x;VE<int> p=n1.conv(f,g,sz),q=n2.conv(f,g,sz),r=n3.conv(f,g,sz);if(!ret.size())ret.resize(p.size());LL t1,t2,m1=n1.getmod(),m2=n2.getmod(),m3=n3.getmod();LL i1_2=DIV(1,m1,m2),i12_3=DIV(1,m1*m2,m3),m12_m=m1*m2%m;rep(i,p.size()){t1=(q[i]-p[i])*i1_2%m2;if(t1<0)t1+=m2;t2=(r[i]-(p[i]+m1*t1)%m3)*i12_3%m3;if(t2<0)t2+=m3;ret[i]=(p[i]+m1*t1+m12_m*t2)%m;}return ret;} template<int mod>struct poly{ using mint=modint<mod>; using vmint=VE<mint>; vmint vec; poly(LL n=0,LL k=0){vec.resize(n,k);} poly(VL &v){LL i,n=v.size();vec.resize(n);rep(i,n)vec[i]=v[i];} poly(vmint &v):vec(v){} size_t size()const{return vec.size();} void resize(LL n=0,LL k=0){vec.resize(n,k);} void assign(LL n=0,LL k=0){vec.assign(n,k);} mint &operator[](LL i){return vec[i];} poly &operator=(const VL &v){LL i,n=v.size();vec.resize(n);rep(i,n)vec[i]=v[i];return *this;} poly &operator=(const vmint &v){vec=v;return *this;} poly &operator=(const poly &p){vec=p.vec;return *this;} poly &operator+=(const poly &p){LL i;if(vec.size()<p.size())vec.resize(p.size());rep(i,p.size())vec[i]+=p.vec[i];return *this;} poly &operator-=(const poly &p){LL i;if(vec.size()<p.size())vec.resize(p.size());rep(i,p.size())vec[i]-=p.vec[i];return *this;} poly &operator*=(const mint m){for(auto &n:vec)n*=m;return *this;} poly &operator*=(const poly &p){vec=AMC(vec,p.vec);return *this;} poly &operator/=(const mint m){for(auto &n:vec)n/=m;return *this;} poly &operator/=(const poly &p){vec=AMC(vec,p.inv().vec,p.size());return *this;} poly operator+(const poly &p)const{return poly(*this)+=p;} poly operator-(const poly &p)const{return poly(*this)-=p;} poly operator*(const mint m)const{return poly(*this)*=m;} poly operator*(const poly &p)const{return poly(*this)*=p;} poly operator/(const mint m)const{return poly(*this)/=m;} poly operator/(const poly &p)const{return poly(*this)/=p;} bool operator==(const poly &p)const{if(vec.size()!=p.size())return 0;LL i;rep(i,vec.size())if(vec[i]!=p.vec[i])return 0;return 1;} bool operator!=(const poly &p)const{return !(*this==p);} LL zsize()const{LL i;rep(i,vec.size())if(vec[i]!=0)break;return i;} poly sub(LL l,LL r)const{LL i;poly ret;if(l>=r||l<0)return ret;ret.resize(r-l);FOR(i,l,min((LL)vec.size(),r))ret[i-l]=vec[i];return ret;} mint val(LL m)const{LL i;mint ret=0,k=1;rep(i,vec.size())ret+=vec[i]*k,k*=m;return ret;} poly dif(LL n)const{if(n==0)return *this;if(n<0)return integral(-n);LL i,s=vec.size()-n;poly ret;if(s<=0)return ret;ret.resize(s);if(fact.size()<s+n)comi(s+n-1);rep(i,s)ret.vec[i]=vec[i+n]*fact[i+n]*finv[i];return ret;} poly integral(LL n)const{if(n==0)return *this;if(n<0)return dif(-n);LL i,s=vec.size()+n;poly ret(s);if(fact.size()<=s)comi(s);rep(i,s-n)ret.vec[i+n]=vec[i]*fact[i]*finv[i+n];return ret;} poly inv()const{LL i,a,k=2,n=vec.size();poly ret;if(n==0||vec[0]==0)return ret;ret.resize(n);vmint f,g,h;g.PB(vec[0].inv());f.PB(vec[0]);while(k<n*2){a=min(n,k);f.resize(a);copy(vec.begin()+k/2,vec.begin()+a,f.begin()+k/2);h=AMC(f,g,a);for(auto &j:h)j=-j;h[0]+=2;g=AMC(g,h,a);k*=2;}copy(g.begin(),g.begin()+n,ret.vec.begin());return ret;} poly log()const{poly p;if(vec.size()==0||vec[0]!=1)return p;p=dif(1);p/=(*this);p.vec.POB();return p.integral(1);} poly exp()const{LL i,a,k=2,n=vec.size();poly ret;if(n==0||vec[0]!=0)return ret;ret.resize(n);poly f,g,h;g.vec.PB(1);f.vec.PB(vec[0]);while(k<n*2){a=min(n,k);f.resize(a);g.resize(a);copy(vec.begin()+k/2,vec.begin()+a,f.vec.begin()+k/2);h=f-g.log();++h[0];g.vec=AMC(g.vec,h.vec,a);k*=2;}copy(g.vec.begin(),g.vec.begin()+n,ret.vec.begin());return ret;} poly pow(LL n)const{LL i,z=zsize(),s=vec.size();mint k=1;poly ret(s);if(n<=0||z*n>=s)return ret;poly p=sub(z,s-z*(n-1));if(p[0]!=1)k=p[0].pow(n),p/=p[0];p=p.log()*(mint)n;p=p.exp()*k;copy(ALL(p.vec),ret.vec.begin()+z*n);return ret;} poly sqrt()const{LL i,z=zsize(),n=vec.size(),s=n-z/2,k=2,a;poly ret;if(n==z){ret.resize(n);return ret;}if(n==0||z%2==1)return ret;mint r=vec[z].sqrt();if(r.x==-1)return ret;ret.resize(n);poly f,g;g.vec.PB(r);f.vec.PB(vec[z]);z/=2,n-=z;while(k<n*2){a=min(n,k);f.resize(a);g.resize(a);if(z*2+k/2<n+z)copy(vec.begin()+z*2+k/2,vec.begin()+z*2+min(a,n-z),f.vec.begin()+k/2);g=(g+f/g)/(mint)2;k*=2;}copy(ALL(g.vec),ret.vec.begin()+z);return ret;} poly shift(LL n)const{LL i,s=vec.size();poly ret(s);mint k=1;vmint a(s),c(s);if(fact.size()<s)comi(s);rep(i,s)a[i]=vec[i]*fact[i],c[s-i-1]=k*finv[i],k*=n;a=AMC(a,c);rep(i,s)ret[i]=a[s-1+i]*finv[i];return ret;} void poly_div(const poly &p,poly &q,poly &r)const{LL i,n=vec.size(),m=p.size(),k;q.resize(n),r.resize(max(n,m));rep(i,n)q[n-1-i]=vec[i];rep(i,m)r[m-1-i]=p.vec[i];q/=r;q.vec.resize(max(0LL,n-m+1));REV(q.vec);r=(*this)-p*q;for(k=0;k<n&&r[n-1-k]==0;++k);r.resize(n-k);} }; P StirlingF(LL n,bool f=0){ LL i; P p,q; if(n==0)p.vec.PB(1); else if(n&1){ p.resize(n+1); q=StirlingF(n-1); rep(i,n-1)p[i+1]=q[i]+q[i+1]*(n-1); p[n]=1; }else{ q=StirlingF(n/2); p=q*q.shift(n/2); } if(f){ if(n&1)rep(i,n/2+1)p[i*2]=-p[i*2]; else rep(i,n/2)p[i*2+1]=-p[i*2+1]; } return p; } int main(){ FAST; LL i,N; cin>>N; P p=StirlingF(N,1); vout(p.vec); }