Submit Info #44579

Problem Lang User Status Time Memory
Bernoulli Number cpp ZigZagKmp AC 320 ms 240.66 MiB

ケース詳細
Name Status Time Memory
0_00 AC 108 ms 193.30 MiB
100000_00 AC 153 ms 204.41 MiB
10000_00 AC 112 ms 194.45 MiB
1000_00 AC 111 ms 193.42 MiB
100_00 AC 110 ms 193.34 MiB
1_00 AC 110 ms 193.30 MiB
200000_00 AC 204 ms 215.53 MiB
300000_00 AC 222 ms 226.52 MiB
400000_00 AC 319 ms 237.64 MiB
500000_00 AC 320 ms 240.66 MiB
example_00 AC 109 ms 193.34 MiB

#include<bits/stdc++.h> using namespace std; #define maxn 2100005 #define maxm 2100005 #define inf 0x3f3f3f3f #define LL long long #define ull unsigned long long #define mod 998244353 #define eps 1e-6 #define local void file(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);} template <typename Tp> void read(Tp &x){ int fh=1;char c=getchar();x=0; while(c>'9'||c<'0'){if(c=='-'){fh=-1;}c=getchar();} while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c&15);c=getchar();}x*=fh; } template <typename Tp> void read_(Tp &x,int Mod){ int fh=1;char c=getchar();x=0; while(c>'9'||c<'0'){if(c=='-'){fh=-1;}c=getchar();} while(c>='0'&&c<='9'){x=(x*10ll+c-'0')%Mod;c=getchar();}x*=fh; } mt19937 rnd(time(0)); int ksm(int b,int p=mod-2,int Mod=mod){int ret=1;while(p){if(p&1)ret=1ll*ret*b%Mod;b=1ll*b*b%Mod;p>>=1;}return ret;} int frac[maxm],frinv[maxm]; void prepr(int N){ frac[0]=1; for(int i=1;i<=N;++i)frac[i]=1ll*frac[i-1]*i%mod; frinv[N]=ksm(frac[N],mod-2); for(int i=N;i;--i)frinv[i-1]=1ll*frinv[i]*i%mod; } namespace Math{ struct CP{ int x,y,w,Mod; CP operator *(CP b)const{return (CP){(int)((1ll*x*b.x+1ll*y*b.y%Mod*w)%Mod),(int)((1ll*x*b.y+1ll*y*b.x)%Mod),w,Mod};} }; CP CPksm(CP b,int p){CP ret=(CP){1,0,b.w,b.Mod};while(p){if(p&1)ret=ret*b;b=b*b;p>>=1;}return ret;} bool is_Sqrt(int x,int Mod=mod){return ksm(x,(Mod-1)/2,Mod)==1;} int Sqrt(int x,int Mod=mod){ x%=Mod; if(Mod==2||x==0)return x; if(!is_Sqrt(x,Mod))return -1; int a,w; while(1){ a=rnd()%Mod;w=(1ll*a*a+Mod-x)%Mod; if(!is_Sqrt(w,Mod))break; } CP tmp=CPksm((CP){a,1,w,Mod},(Mod+1)/2); int ans1=tmp.x,ans2=mod-tmp.x; return ans1<ans2?ans1:ans2; } } #define vi vector<int> namespace Poly{ const int Gmod=3; int tr[maxn],Wn[maxn]; int LG[maxn],inv[maxn]; int mxN; void prep(int nmax){ prepr(nmax); for(mxN=1;mxN<nmax;mxN<<=1); LG[0]=-1; for(int i=2;i<=mxN;++i)LG[i]=LG[i>>1]+1; inv[1]=1; for(int i=2;i<=mxN;++i)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod; for(int i=1;i<mxN;++i)tr[i]=((tr[i>>1]>>1)|((i&1)?(mxN>>1):0)); for(int len=1;len<mxN;len<<=1){ Wn[len]=1;int wn=ksm(Gmod,(mod-1)/(len<<1)); for(int j=1;j<len;++j)Wn[len+j]=1ll*Wn[len+j-1]*wn%mod; } } ull tf[maxn]; void ntt(vi &f,int N){ int tn=LG[mxN/N]; for(int i=0;i<N;++i)tf[tr[i]>>tn]=f[i]; for(int len=1;len<N;len<<=1){ for(int i=0;i<N;i+=(len<<1)){ for(int j=0;j<len;++j){ unsigned x=tf[i+j+len]*Wn[len+j]%mod; tf[i+j+len]=(tf[i+j]+mod-x); tf[i+j]=(tf[i+j]+x); } } } for(int i=0;i<N;++i)f[i]=tf[i]%mod; } void dnt(vi &f,int N){ reverse(f.begin()+1,f.end()); ntt(f,N); int invN=inv[N]; for(int i=0;i<N;++i)f[i]=1ll*f[i]*invN%mod; } vi fix(vi a,int n){a.resize(n);return a;} int calcfx(vi a,int x){ int ret=0,nn=a.size(); for(int i=0,t=1;i<nn;++i,t=1ll*t*x%mod){ ret=ret+1ll*a[i]*t%mod; if(ret>=mod)ret-=mod; } return ret; } vi operator + (vi a,vi b){ int nn=max(a.size(),b.size());a.resize(nn); for(int i=0;i<nn;++i){ a[i]=a[i]+b[i]; if(a[i]>=mod)a[i]-=mod; } return a; } vi operator - (vi a,vi b){ int nn=max(a.size(),b.size());a.resize(nn); for(int i=0;i<nn;++i){ a[i]=a[i]-b[i]; if(a[i]<0)a[i]+=mod; } return a; } vi operator *(vi a,int x){ int nn=a.size(); for(int i=0;i<nn;++i)a[i]=1ll*a[i]*x%mod; return a; } vi Der(vi a){ int nn=a.size(); for(int i=0;i<nn-1;++i)a[i]=1ll*a[i+1]*(i+1)%mod; a.pop_back(); return a; } vi Inte(vi a){ int nn=a.size(); a.push_back(0); for(int i=nn;i>0;--i)a[i]=1ll*a[i-1]*inv[i]%mod; a[0]=0; return a; } vi operator * (vi a,vi b){ if(a.empty()||b.empty())return vi(); int nn=a.size()+b.size()-1,N=(1<<(LG[nn-1]+1)); a.resize(N),b.resize(N); ntt(a,N);ntt(b,N); for(int i=0;i<N;++i)a[i]=1ll*a[i]*b[i]%mod; dnt(a,N); return fix(a,nn); } vi Muld(vi a,vi b){ if(a.empty()||b.empty())return vi(); int nn=a.size(),N=(1<<(LG[nn+nn-1-1]+1));//a.size()=b.size() reverse(b.begin(),b.end()); a.resize(N);b.resize(N); ntt(a,N);ntt(b,N); for(int i=0;i<N;++i)a[i]=1ll*a[i]*b[i]%mod; dnt(a,N); for(int i=0;i<nn;++i)a[i]=a[i+nn-1]; return fix(a,nn); } vi Shift(vi a,int c){ if(a.empty())return vi(); int nn=a.size(); vi p,q;p.resize(nn);q.resize(nn); for(int i=0;i<nn;++i)p[i]=1ll*a[i]*frac[i]%mod; for(int i=0,t=1;i<nn;++i,t=1ll*t*c%mod){ q[i]=1ll*t*frinv[i]%mod; } vi ret=Muld(p,q); for(int i=0;i<nn;++i)ret[i]=1ll*ret[i]*frinv[i]%mod; return ret; } void Poly_oup(vi a){ int nn=a.size(); for(int i=0;i<nn;++i)printf("%d%c",a[i]," \n"[i==nn-1]); } vi Inv(vi a){ int nn=a.size(); if(nn==1)return vi(1,ksm(a[0],mod-2)); vi b=Inv(fix(a,(nn+1)>>1)); int len=(1<<(LG[nn+(int)b.size()-1]+1)); vi c=fix(b,len),d=fix(a,len); ntt(c,len);ntt(d,len); for(int i=0;i<len;++i)c[i]=1ll*c[i]*c[i]%mod*d[i]%mod; dnt(c,len); b.resize(nn); for(int i=(nn+1)/2;i<nn;++i){ b[i]=b[i]-c[i]; if(b[i]<0)b[i]+=mod; } return b; } vi operator / (vi a,vi b){ int nn=a.size(),mm=b.size(); reverse(a.begin(),a.end()); reverse(b.begin(),b.end()); a.resize(nn-mm+1);b.resize(nn-mm+1); a=fix(a*Inv(b),nn-mm+1); reverse(a.begin(),a.end()); return a; } vi operator % (vi a,vi b){ if(a.size()<b.size())return a; int mm=b.size(); return fix(a-(a/b)*b,mm-1); } int inv2=((mod+1)>>1); vi Sqrt(vi a){ int nn=a.size(); if(nn==1)return vi(1,Math::Sqrt(a[0])); vi b=fix(Sqrt(fix(a,(nn+1)>>1)),nn); return fix((b+a*Inv(b))*inv2,nn); } vi Sqrt_Norm(vi a){ int nm=-1,nn=a.size(); for(int i=0;i<nn;++i){ if(a[i]!=0){ nm=i;break; } } if(nm<0)nm=nn; if(nm==nn)return a; if(nm&1)return vi(); int a0=a[nm]; if(Math::Sqrt(a0)==-1)return vi(); for(int i=0;i<nn;++i){ if(i+nm>=nn)a[i]=0; else a[i]=a[i+nm]; } vi b=Sqrt(a);nm>>=1; for(int i=nn-1;i>=0;--i){ if(i>=nm)b[i]=b[i-nm]; else b[i]=0; } return b; } vi Ln(vi a){ int nn=a.size(); return fix(Inte(Der(a)*Inv(a)),nn); } vi Exp(vi a){// Newton int nn=a.size(); if(nn==1)return vi(1,1); vi b=Exp(fix(a,(nn+1)>>1)); return fix(b+b*(a-Ln(fix(b,nn))),nn); } vi Ksm(vi a,int p){ return Exp(Ln(a)*p); } vi Ksm_Norm(vi a,int p){ int t=0,nn=a.size(); while(t<a.size()&&a[t]==0)++t; if(1ll*p*t>=nn){ return vi(nn,0); } for(int i=t;i<nn;++i)a[i-t]=a[i]; int a0=a[0],iva0=ksm(a0,mod-2),ksa0=ksm(a0,p); for(int i=0;i<nn-t;++i)a[i]=1ll*a[i]*iva0%mod; a.resize(nn-t); a=Ksm(a,p); for(int i=0;i<nn-t;++i)a[i]=1ll*a[i]*ksa0%mod; a.resize(nn); for(int i=nn-1;i>=p*t;--i)a[i]=a[i-p*t]; for(int i=min(p*t-1,nn-1);i>=0;--i)a[i]=0; return a; } } namespace eval_inter{ using namespace Poly; vi prod[maxn<<2]; vi xx,yy; void getp(int x,int l,int r){ if(l==r){ prod[x]={mod-xx[l],1}; return; } int mid=((l+r)>>1); getp(x<<1,l,mid); getp((x<<1)|1,mid+1,r); prod[x]=prod[x<<1]*prod[(x<<1)|1]; } void gety(vi f,int x,int l,int r){ f=fix(f%prod[x],(int)prod[x].size()-1); if(r-l+1<=128){ for(int i=l;i<=r;++i){ yy[i]=calcfx(f,xx[i]); } return; } int mid=((l+r)>>1); gety(f,x<<1,l,mid); gety(f,(x<<1)|1,mid+1,r); } vi eval(vi f,vi x,int flg=0){ int nn=max(f.size(),x.size());yy.resize(nn); xx.resize(nn);x.resize(nn); for(int i=0;i<nn;++i){ xx[i]=x[i]; } getp(1,0,nn-1); gety(f,1,0,nn-1); return yy; } vi getf(int x,int l,int r){ if(l==r){ return vi(1,yy[l]); } int mid=((l+r)>>1); vi fl=getf(x<<1,l,mid),fr=getf((x<<1)|1,mid+1,r); return fl*prod[(x<<1)|1]+fr*prod[x<<1]; } vi inter(vi x,vi y){ int nn=x.size(); xx=x;yy.resize(nn); getp(1,0,nn-1); vi g=Der(prod[1]); gety(g,1,0,nn-1); for(int i=0;i<nn;++i)yy[i]=1ll*y[i]*ksm(yy[i],mod-2)%mod; return getf(1,0,nn-1); } } namespace Composit{ using namespace Poly; vi g1[150],g2[150]; vi Compf(vi f,vi g){//f(g(x)) int nn=f.size(),mm=g.size(); int blo=sqrt(nn)+1,N=(1<<(LG[nn-1]+1)); g1[0]=vi(1,1);g1[0].resize(N); for(int i=1;i<=blo;++i)g1[i]=fix(g1[i-1]*g,N); g2[0]=vi(1,1);g2[0].resize(N); for(int i=1;i<=blo;++i)g2[i]=fix(g2[i-1]*g1[blo],N); vi ans,tmp; ans.resize(N);tmp.resize(N); for(int i=0;i<N;++i)ans[i]=0; for(int i=0;i<blo;++i){ for(int j=0;j<N;++j)tmp[j]=0; for(int j=0;j<blo&&i*blo+j<nn;++j){ int x=f[i*blo+j]; tmp=tmp+g1[j]*x; } ans=ans+fix(tmp*g2[i],N); } return fix(ans,nn); } vi CompInv(vi f){//fing g, s.t. f(g(x))=x int nn=f.size(); int blo=sqrt(nn)+1,N=(1<<(LG[nn-1]+1)); for(int i=1;i<nn;++i)f[i-1]=f[i];f.pop_back(); f=fix(Inv(f),N); g1[0]=vi(1,1);g1[0].resize(N); for(int i=1;i<=blo;++i)g1[i]=fix(g1[i-1]*f,N); g2[0]=vi(1,1);g2[0].resize(N); for(int i=1;i<=blo;++i)g2[i]=fix(g2[i-1]*g1[blo],N); vi ans; ans.resize(N); for(int i=0;i<N;++i)ans[i]=0; for(int i=0;i<blo;++i){ for(int j=0;j<blo&&i*blo+j<nn;++j){ int x=ksm(i*blo+j,mod-2),sm=0; for(int t=0;t<=i*blo+j-1;++t){ sm=sm+1ll*g2[i][t]*g1[j][i*blo+j-1-t]%mod; if(sm>=mod)sm-=mod; } ans[i*blo+j]=1ll*x*sm%mod; } } return fix(ans,nn); } } namespace DPoly{ using namespace Poly; using namespace eval_inter; void ndt(vi &f){ int nn=f.size(); vi g;g.resize(nn); for(int i=0;i<nn;++i)g[i]=frinv[i]; f=f*g;f.resize(nn); for(int i=0;i<nn;++i)f[i]=1ll*f[i]*frac[i]%mod; } void ddt(vi &f){ int nn=f.size(); vi g;g.resize(nn); for(int i=0;i<nn;++i)f[i]=1ll*f[i]*frinv[i]%mod; for(int i=0;i<nn;++i)g[i]=(i&1)?(mod-frinv[i]):frinv[i]; f=f*g;f.resize(nn); } vi Poly_to_DPoly(vi f){ int nn=f.size(); vi g,Yi;g.resize(nn); for(int i=0;i<nn;++i)g[i]=i; Yi=eval(f,g); ddt(Yi); return Yi; } vi DPoly_to_Poly(vi f){ int nn=f.size(); vi g;g.resize(nn); for(int i=0;i<nn;++i)g[i]=i; ndt(f); return inter(g,f); } } namespace Stirling{ using namespace Poly; vi S2_row(int nn){ vi t1,t2; t1.resize(nn+1),t2.resize(nn+1); for(int i=0;i<=nn;++i)t1[i]=1ll*ksm(i,nn)*frinv[i]%mod; for(int i=0;i<=nn;++i)t2[i]=((i&1)?(mod-frinv[i]):(frinv[i])); t1=t1*t2; return fix(t1,nn+1); } vi S2_col(int nn,int k){ vi t1;t1.resize(nn+1); for(int i=1;i<=nn;++i)t1[i]=frinv[i]; t1=Ksm_Norm(t1,k); for(int i=0;i<=nn;++i)t1[i]=1ll*t1[i]*frinv[k]%mod*frac[i]%mod; return t1; } vi get_S1(int l,int r){ if(l==r){ vi ret;ret.resize(2);ret[0]=(mod-l)%mod,ret[1]=1; return ret; } int mid=((l+r)>>1); return get_S1(l,mid)*get_S1(mid+1,r); } vi S1_row_slow(int nn){ return get_S1(0,nn-1); } vi S1_col(int nn,int k){ vi t1;t1.resize(nn+1); t1[0]=1;t1[1]=mod-1; t1=Ln(t1); for(int i=0;i<=nn;++i)t1[i]=(mod-t1[i])%mod; t1=Ksm_Norm(t1,k); for(int i=0;i<=nn;++i)t1[i]=1ll*t1[i]*frinv[k]%mod*frac[i]%mod; return t1; } vi Bell(int nn){ vi t1;t1.resize(nn+1); for(int i=1;i<=nn;++i)t1[i]=frinv[i]; t1=Exp(t1); for(int i=0;i<=nn;++i)t1[i]=1ll*t1[i]*frac[i]%mod; return t1; } } int n,m; vi a,b,c; int h[maxn]; signed main(){ read(n);Poly::prep((n+1)<<1); a.resize(n+1); for(int i=1;i<=n+1;++i)a[i-1]=frinv[i]; b=Poly::Inv(a); for(int i=0;i<=n;++i)printf("%lld ",1ll*b[i]*frac[i]%mod); return 0; }