Submit Info #958

Problem Lang User Status Time Memory
Bernoulli Number cpp maroonrk AC 233 ms 68.55 MiB

Name Status Time Memory
0_00 AC 65 ms 56.81 MiB
100000_00 AC 102 ms 59.59 MiB
10000_00 AC 68 ms 57.23 MiB
1000_00 AC 67 ms 56.81 MiB
100_00 AC 64 ms 56.80 MiB
1_00 AC 66 ms 56.78 MiB
200000_00 AC 145 ms 62.33 MiB
300000_00 AC 223 ms 67.06 MiB
400000_00 AC 227 ms 67.81 MiB
500000_00 AC 233 ms 68.55 MiB
example_00 AC 64 ms 56.80 MiB

#include <bits/stdc++.h> using namespace std; using ll=long long; #define int ll #define rng(i,a,b) for(int i=int(a);i<int(b);i++) #define rep(i,b) rng(i,0,b) #define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--) #define per(i,b) gnr(i,0,b) #define pb push_back #define eb emplace_back #define a first #define b second #define bg begin() #define ed end() #define all(x),x.ed #ifdef LOCAL #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl #else #define dmp(x) void(0) #endif template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;} template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;} template<class t> using vc=vector<t>; template<class t> using vvc=vc<vc<t>>; using pi=pair<int,int>; using vi=vc<int>; template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p){ return os<<"{"<<p.a<<","<<p.b<<"}"; } template<class t> ostream& operator<<(ostream& os,const vc<t>& v){ os<<"{"; for(auto e:v)os<<e<<","; return os<<"}"; } using uint=unsigned; using ull=unsigned long long; const uint mod=998244353; //const uint mod=1000000007; //uint mod=1; struct mint{ uint v; mint(ll vv=0){s(vv%mod+mod);} mint& s(uint vv){ v=vv<mod?vv:vv-mod; return *this; } mint operator-()const{return mint()-*this;} mint& operator+=(const mint&rhs){return s(v+rhs.v);} mint&operator-=(const mint&rhs){return s(v+mod-rhs.v);} mint&operator*=(const mint&rhs){ v=ull(v)*rhs.v%mod; return *this; } mint&operator/=(const mint&rhs){return *this*=rhs.inv();} mint operator+(const mint&rhs)const{return mint(*this)+=rhs;} mint operator-(const mint&rhs)const{return mint(*this)-=rhs;} mint operator*(const mint&rhs)const{return mint(*this)*=rhs;} mint operator/(const mint&rhs)const{return mint(*this)/=rhs;} mint pow(int n)const{ mint res(1),x(*this); while(n){ if(n&1)res*=x; x*=x; n>>=1; } return res; } mint inv()const{return pow(mod-2);} /*mint inv()const{ int x,y; int g=extgcd(v,mod,x,y); assert(g==1); if(x<0)x+=mod; return mint(x); }*/ friend ostream& operator<<(ostream&os,const mint&m){ return os<<m.v; } bool operator<(const mint&r)const{return v<r.v;} bool operator==(const mint&r)const{return v==r.v;} }; const int vmax=(1<<21)+10; mint fact[vmax],finv[vmax],invs[vmax]; void initfact(){ fact[0]=1; rng(i,1,vmax){ fact[i]=fact[i-1]*i; } finv[vmax-1]=fact[vmax-1].inv(); for(int i=vmax-2;i>=0;i--){ finv[i]=finv[i+1]*(i+1); } for(int i=vmax-1;i>=1;i--){ invs[i]=finv[i]*fact[i-1]; } } mint choose(int n,int k){ return fact[n]*finv[n-k]*finv[k]; } mint binom(int a,int b){ return fact[a+b]*finv[a]*finv[b]; } mint catalan(int n){ return binom(n,n)-(n-1>=0?binom(n-1,n+1):0); } #define USE_FMT //998244353 const mint prim_root=3; /* //in-place fft //size of input must be a power of 2 void inplace_fmt(vector<mint>&f,const bool inv){ const int n=f.size(); const mint root=inv?prim_root.inv():prim_root; vc<mint> g(n); for(int b=n/2;b>=1;b/=2){ mint w=root.pow((mint::base-1)/(n/b)),p=1; for(int i=0;i<n;i+=b*2){ rep(j,b){ f[i+j+b]*=p; g[i/2+j]=f[i+j]+f[i+b+j]; g[n/2+i/2+j]=f[i+j]-f[i+b+j]; } p*=w; } swap(f,g); } if(inv)rep(i,n) f[i]*=inv[n]; }*/ static const int LG=21; mint roots[1<<(LG+1)],iroots[1<<(LG+1)]; struct PrepareRoots{ PrepareRoots(){ rep(w,LG+1){ const int s=(1<<w)-1; const mint g=prim_root.pow((mod-1)/(1<<w)),ig=g.inv(); mint p=1,ip=1; rep(i,1<<w){ roots[s+i]=p;p*=g; iroots[s+i]=ip;ip*=ig; } } } } PrepareRootsDummy; void broken_fmt(vc<mint>&f){ const int n=f.size(); for(int b=n/2;b>=1;b/=2){ for(int i=0;i<n;i+=b*2){ rep(j,b){ mint tmp=f[i+j]-f[i+j+b]; f[i+j]+=f[i+j+b]; f[i+j+b]=tmp*roots[b*2-1+j]; } } } } void broken_ifmt(vc<mint>&f){ const int n=f.size(); for(int b=1;b<=n/2;b*=2){ for(int i=0;i<n;i+=b*2){ rep(j,b){ f[i+j+b]*=iroots[b*2-1+j]; mint tmp=f[i+j]-f[i+j+b]; f[i+j]+=f[i+j+b]; f[i+j+b]=tmp; } } } rep(i,n) f[i]*=invs[n]; } void inplace_fmt(vector<mint>&f,const bool i){ if(!i)broken_fmt(f); else broken_ifmt(f); } vc<mint> multiply(vc<mint> x,vc<mint> y,bool same=false){ int n=x.size()+y.size()-1; int s=1; while(s<n)s*=2; x.resize(s);inplace_fmt(x,false); if(!same){ y.resize(s);inplace_fmt(y,false); }else y=x; rep(i,s) x[i]*=y[i]; inplace_fmt(x,true);x.resize(n); return x; } template<class D> struct Poly:public vc<D>{ template<class...Args> Poly(Args...args):vc<D>(args...){} Poly(initializer_list<D>init):vc<D>(all(init)){} int size()const{ return vc<D>::size(); } void ups(int s){ if(size()<s)this->resize(s,0); } Poly low(int s)const{ return Poly(this->bg,this->bg+min(max(s,int(1)),size())); } Poly rev()const{ auto r=*this; reverse(all(r)); return r; } Poly& operator+=(const Poly&r){ ups(r.size()); rep(i,r.size()) (*this)[i]+=r[i]; return *this; } Poly& operator-=(const Poly&r){ ups(r.size()); rep(i,r.size()) (*this)[i]-=r[i]; return *this; } template<class T> Poly& operator*=(T t){ for(auto&v:*this) v*=t; return *this; } Poly& operator*=(const Poly&r){ return *this=multiply(*this,r); } Poly square()const{ return multiply(*this,*this,true); } #ifndef USE_FMT Poly inv(int s)const{ Poly r{D(1)/(*this)[0]}; for(int n=1;n<s;n*=2) r=r*2-(r.square()*low(2*n)).low(2*n); return r.low(s); } #else Poly inv(int s)const{ Poly r{D(1)/(*this)[0]}; for(int n=1;n<s;n*=2){ r.resize(n*4); inplace_fmt(r,false); vc<D> f=low(2*n); f.resize(n*4); inplace_fmt(f,false); rep(i,n*4) r[i]=r[i]*2-r[i]*r[i]*f[i]; inplace_fmt(r,true); r.resize(2*n); } return r.low(s); } #endif template<class T> Poly& operator/=(T t){ return *this*=D(1)/D(t); } Poly quotient(const Poly&r,const Poly&rri)const{ int m=r.size(); assert(r[m-1].v); int n=size(); int s=n-m+1; if(s<=0) return {0}; return (rev().low(s)*rri.low(s)).low(s).rev(); } Poly& operator/=(const Poly&r){ return *this=quotient(r,r.rev().inv(max(size()-r.size(),int(0))+1)); } Poly& operator%=(const Poly&r){ *this-=*this/r*r; return *this=low(r.size()-1); } Poly operator+(const Poly&r)const{return Poly(*this)+=r;} Poly operator-(const Poly&r)const{return Poly(*this)-=r;} template<class T> Poly operator*(T t)const{return Poly(*this)*=t;} Poly operator*(const Poly&r)const{return Poly(*this)*=r;} template<class T> Poly operator/(T t)const{return Poly(*this)/=t;} Poly operator/(const Poly&r)const{return Poly(*this)/=r;} Poly operator%(const Poly&r)const{return Poly(*this)%=r;} Poly dif()const{ Poly r(max(int(0),size()-1)); rep(i,r.size()) r[i]=(*this)[i+1]*(i+1); return r; } Poly inte()const{ Poly r(size()+1,0); rep(i,size()) r[i+1]=(*this)[i]*invs[i+1]; return r; } //opencupXvcIII GP of Peterhof H Poly log(int s)const{ return (low(s).dif()*inv(s-1)).low(s-1).inte(); } //Petrozavodsk 2019w Day1 G //yosupo judge Poly exp(int s)const{ return exp2(s).a; } //2つほしいときはコメントアウトの位置ずらす pair<Poly,Poly> exp2(int s)const{ assert((*this)[0]==mint(0)); Poly f{1},g{1}; for(int n=1;;n*=2){ if(n>=s)break; g=g*2-(g.square()*f).low(n); //if(n>=s)break; Poly q=low(n).dif(); q=q+g*(f.dif()-f*q).low(2*n-1); f=f+(f*(low(2*n)-q.inte())).low(2*n); } return make_pair(f.low(s),g.low(s)); } //CF250 E Poly sqrt(int s)const{ assert((*this)[0]==1); Poly r{1}; for(int n=1;n<s;n*=2) r=(r+(r.inv(n*2)*low(n*2)).low(n*2))*inv[2]; return r.low(s); } pair<Poly,Poly> divide(const Poly&r,const Poly&rri)const{ Poly a=quotient(r,rri); Poly b=*this-a*r; return make_pair(a,b.low(r.size()-1)); } //Yukicoder No.215 Poly pow_mod(int n,const Poly&r)const{ Poly rri=r.rev().inv(r.size()); Poly cur{1},x=*this%r; while(n){ if(n%2) cur=(cur*x).divide(r,rri).b; x=(x*x).divide(r,rri).b; n/=2; } return cur; } D eval(D x)const{ D r=0,w=1; for(auto v:*this){ r+=w*v; w*=x; } return r; } }; signed main(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20); initfact(); int n;cin>>n; n++; Poly<mint> f(n); rep(i,n) f[i]=finv[i+1]; auto g=f.inv(n); rep(i,n) cout<<g[i]*fact[i]<<(i<n-1?" ":"\n"); }