Submit Info #680

Problem Lang User Status Time Memory
Bernoulli Number cpp latte0119 AC 148 ms 26.49 MiB

ケース詳細
Name Status Time Memory
0_00 AC 21 ms 16.67 MiB
100000_00 AC 50 ms 18.98 MiB
10000_00 AC 24 ms 17.05 MiB
1000_00 AC 21 ms 16.72 MiB
100_00 AC 25 ms 16.64 MiB
1_00 AC 23 ms 16.68 MiB
200000_00 AC 84 ms 21.26 MiB
300000_00 AC 145 ms 25.01 MiB
400000_00 AC 145 ms 25.77 MiB
500000_00 AC 148 ms 26.49 MiB
example_00 AC 20 ms 16.65 MiB

#include<bits/stdc++.h> #include<unistd.h> using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define all(v) (v).begin(),(v).end() #define fi first #define se second typedef vector<int>vint; typedef pair<int,int>pint; typedef vector<pint>vpint; template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;} template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;} template<uint32_t mod> struct ModInt{ uint32_t a; ModInt& s(uint32_t vv){ a=vv<mod?vv:vv-mod; return *this; } ModInt(int64_t x=0){s(x%mod+mod);} ModInt& operator+=(const ModInt &x){return s(a+x.a);} ModInt& operator-=(const ModInt &x){return s(a+mod-x.a);} ModInt& operator*=(const ModInt &x){ a=uint64_t(a)*x.a%mod; return *this; } ModInt& operator/=(const ModInt &x){ *this*=x.inv(); return *this; } ModInt operator+(const ModInt &x)const{return ModInt(*this)+=x;} ModInt operator-(const ModInt &x)const{return ModInt(*this)-=x;} ModInt operator*(const ModInt &x)const{return ModInt(*this)*=x;} ModInt operator/(const ModInt &x)const{return ModInt(*this)/=x;} bool operator==(const ModInt &x)const{return a==x.a;} bool operator!=(const ModInt &x)const{return a!=x.a;} ModInt operator-()const{return ModInt()-*this;} ModInt pow(int64_t n)const{ ModInt res(1),x(*this); while(n){ if(n&1)res*=x; x*=x; n>>=1; } return res; } ModInt inv()const{return pow(mod-2);} }; template<uint32_t mod> istream& operator>>(istream& in,const ModInt<mod>& a){ return (in>>a.a); } template<uint32_t mod> ostream& operator<<(ostream& out,const ModInt<mod>& a){ return (out<<a.a); } using mint=ModInt<998244353>; template<class Mint,int32_t N> struct ModIntTable{ vector<Mint>facts,finvs,invs; ModIntTable():facts(N),finvs(N),invs(N){ const uint32_t mod=Mint(-1).a+1; invs[1]=1; for(int i=2;i<N;i++)invs[i]=invs[mod%i]*(mod-mod/i); facts[0]=1; finvs[0]=1; for(int i=1;i<N;i++){ facts[i]=facts[i-1]*i; finvs[i]=finvs[i-1]*invs[i]; } } inline Mint fact(int n)const{return facts[n];} inline Mint finv(int n)const{return finvs[n];} inline Mint inv(int n)const{return invs[n];} inline Mint binom(int n,int k)const{return facts[n]*finvs[k]*finvs[n-k];} }; ModIntTable<mint,1<<19>mtable; namespace NTTFriendlyPoly{ const uint32_t mod=998244353; const uint32_t prim_root=3; using Mint=ModInt<mod>; const int LG=19; Mint invs[1<<LG]; Mint roots[1<<LG+1],iroots[1<<LG+1]; struct InitTable{ InitTable(){ invs[1]=1; for(int i=2;i<1<<LG;i++)invs[i]=invs[mod%i]*(mod-mod/i); rep(w,LG+1){ const int s=(1<<w)-1; const Mint g=Mint(prim_root).pow((mod-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; } } } }InitTableDummy; void ntt(vector<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){ const 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 intt(vector<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]; const Mint tmp=f[i+j]-f[i+j+b]; f[i+j]+=f[i+j+b]; f[i+j+b]=tmp; } } } const Mint in=Mint(n).inv(); rep(i,n) f[i]*=in; } vector<Mint> multiply(vector<Mint> x,vector<Mint> y){ int n=x.size()+y.size()-1; int s=1<<__lg(n-1)+1; x.resize(s); y.resize(s); ntt(x);ntt(y); rep(i,s) x[i]*=y[i]; intt(x);x.resize(n); return x; } template<class Mint> struct Poly{ vector<Mint>v; template<class...Args> Poly(Args...args):v(args...){} Poly(const initializer_list<Mint>&in):v(in.begin(),in.end()){} inline int size()const{return v.size();} inline Mint coef(const int i)const{return (i<v.size())?v[i]:Mint(0);} Poly operator+(const Poly &x)const{ int n=max(size(),x.size()); Poly<Mint>res(n); for(int i=0;i<n;i++)res[i]=coef(i)+x.coef(i); return res; } Poly operator-(const Poly &x)const{ int n=max(size(),x.size()); Poly<Mint>res(n); for(int i=0;i<n;i++)res[i]=coef(i)-x.coef(i); return res; } Poly operator*(const Poly& x)const{ return multiply(v,x.v); } Poly operator*(const Mint& x)const{ int n=size(); vector<Mint>res(n); for(int i=0;i<n;i++)res[i]=v[i]*x; return res; } Poly operator/(const Mint& x)const{ return (*this)*x.inv(); } Poly& operator+=(const Poly& x){return *this=(*this)+x;} Poly& operator-=(const Poly& x){return *this=(*this)-x;} Poly& operator*=(const Poly& x){return *this=(*this)*x;} Poly& operator*=(const Mint& x){return *this=(*this)*x;} Poly& operator/=(const Mint& x){return *this=(*this)/x;} Poly operator-(){return Poly()-*this;} Poly pre(int n)const{ Poly<Mint>res(n); for(int i=0;i<n&&i<size();i++)res[i]=v[i]; return res; } Poly rev()const{ vector<Mint>res=v; while(res.size()&&res.back()==0)res.pop_back(); reverse(res.begin(),res.end()); return res; } Poly diff(int n)const{ Poly<Mint>res(n); for(int i=1;i<size()&&i<=n;i++)res[i-1]=v[i]*i; return res; } Poly inte(int n)const{ Poly<Mint>res(n); for(int i=0;i<size()&&i+1<n;i++)res[i+1]=v[i]*invs[i+1]; return res; } Poly inv(int n)const{ vector<Mint>res{coef(0).inv()}; for(int d=1;d<n;d<<=1){ vector<Mint>f(2*d),g(2*d); for(int j=0;j<2*d;j++)f[j]=coef(j); for(int j=0;j<d;j++)g[j]=res[j]; ntt(f);ntt(g); for(int j=0;j<2*d;j++)f[j]*=g[j]; intt(f); for(int j=0;j<d;j++){ f[j]=0; f[j+d]=-f[j+d]; } ntt(f); for(int j=0;j<2*d;j++)f[j]*=g[j]; intt(f); for(int j=0;j<d;j++)f[j]=res[j]; res=f; } return Poly(res).pre(n); } Poly inv2(int n){ Poly res{coef(0).inv()}; for(int i=1;i<n;i*=2){ res=(res*Mint(2)-res*res*pre(2*i)).pre(2*i); } return res.pre(n); } Poly exp(int n){ Poly f0{1},g0{1}; vector<Mint>F0{1}; for(int d=1;d<n;d<<=1){ vector<Mint>G0=g0.v; ntt(G0); vector<Mint>Delta(d); for(int j=0;j<d;j++)Delta[j]=F0[j]*G0[j]; intt(Delta); Delta[0]-=1; Poly delta(2*d); for(int j=0;j<d;j++)delta[d+j]=Delta[j]; Poly epsilon(2*d); vector<Mint>DF0=f0.diff(d-1).v;DF0.push_back(0); ntt(DF0); for(int j=0;j<d;j++)DF0[j]*=G0[j]; intt(DF0); for(int j=0;j<d-1;j++){ epsilon[j]+=coef(j+1)*(j+1); epsilon[j+d]+=DF0[j]-coef(j+1)*(j+1); } epsilon[d-1]+=DF0[d-1]; Delta=delta.v; ntt(Delta); vector<Mint>DH0=diff(d-1).v;DH0.resize(2*d); ntt(DH0); for(int j=0;j<2*d;j++)Delta[j]*=DH0[j]; intt(Delta); for(int j=0;j<d;j++)epsilon[j+d]-=Delta[j+d]; epsilon=epsilon.inte(2*d)-pre(2*d); vector<Mint>Epsilon=epsilon.v; ntt(Epsilon); rep(j,d)DH0[j]=f0[j],DH0[j+d]=0; ntt(DH0); rep(j,2*d)Epsilon[j]*=DH0[j]; intt(Epsilon); f0.v.resize(2*d); rep(j,d)f0[j+d]-=Epsilon[j+d]; //f0=(f0-epsilon*f0).pre(2*d); if(2*d>=n)break; G0.resize(2*d); rep(j,d)G0[j]=g0[j]; ntt(G0); F0=f0.v; ntt(F0); vector<Mint>T(2*d);rep(j,2*d)T[j]=F0[j]*G0[j]; intt(T); rep(j,d){ T[j]=0; T[j+d]=-T[j+d]; } ntt(T); rep(j,2*d)T[j]*=G0[j]; intt(T); rep(j,d)T[j]=g0[j]; g0=T; } return f0.pre(n); } Poly exp2(int n){ Poly f{1}; for(int i=1;i<n;i*=2){ f=(f*(pre(2*i)-f.log(2*i))+f).pre(2*i); } return f.pre(n); } Poly exp3(int n){ Poly f{1},g{1}; for(int d=1;d<n;d<<=1){ g=g*Mint(2)-(g*g*f).pre(d); Poly q=diff(d-1); q=q+g*(f.diff(d-1)-f*q).pre(2*d-1); f=f+(f*(pre(2*d)-q.inte(2*d))).pre(2*d); } return f.pre(n); } Poly log(int n){ return (diff(n-1)*inv(n-1)).inte(n); } Poly pow(int n,Mint k){ auto res=log(n); res*=k; return res.exp(n); } Mint& operator[](const int i){return v[i];} }; template<class Mint> ostream& operator<<(ostream& ost,Poly<Mint>a){ for(int i=0;i<a.size();i++){ if(i)cout<<" "; cout<<a.v[i]; } return ost; } using poly=Poly<Mint>; }; using NTTFriendlyPoly::poly; // \sum{i=0}^{\infty} Bi/i! x^i // \Sk(n)=sum{i=0}^{n-1} i^k = 1/(k+1) \sum{i=0}^{k} binom(k+1,i)Bi n^{k-i+1} poly BernoulliEGF(int n){ poly A(n); for(int i=0;i<n;i++)A[i]=mtable.finv(i+1); return A.inv(n); } #include<unistd.h> struct IO { static const int bufsize=1<<24; char ibuf[bufsize], obuf[bufsize]; char *ip, *op; IO(): ip(ibuf), op(obuf) { for(int t = 0, k = 0; (k = read(STDIN_FILENO, ibuf+t, sizeof(ibuf)-t)) > 0; t+=k); } ~IO(){ for(int t = 0, k = 0; (k = write(STDOUT_FILENO, obuf+t, op-obuf-t)) > 0; t+=k); } long long scan_int(){ long long x=0; bool neg=false; for(;*ip<'+';ip++) ; if(*ip=='-'){ neg=true; ip++;} else if(*ip=='+'){ ip++;} for(;*ip>='0';ip++){ x = 10*x+*ip-'0'; } if(neg) x = -x; return x; } void put_int(long long x, char c=0){ static char tmp[20]; if(x==0){ *op++ = '0'; } else { int i; if(x<0){ *op++ = '-'; x = -x; } for(i=0; x; i++){ tmp[i] = x % 10; x /= 10; } for(i--; i>=0; i--) *op++ = tmp[i]+'0'; } if(c) *op++ = c; } void put_double(double x, char c=0){ unsigned y; const int mask = (1<<24) - 1; put_int(x); *op++ = '.'; x = x - (int) x; if(x < 0) x = -x; y = x * (1<<24); for(int i=0;i<7;i++){ y *= 10; *op++ = '0' + (y>>24); y &= mask; } } inline char scan_char(){ return *ip++; } inline void put_char(char c){ *op++ = c; } inline char *scan_string(){ char *s = ip; while(*ip++!='\n'){} *(ip-1)='\0'; return s;} inline void put_string(char *s, char c=0){ while(*s) *op++=*s++; if(c) *op++=c;} }; IO io; signed main(){ int n;n=io.scan_int(); poly B=BernoulliEGF(n+1); rep(i,n+1){ if(i)io.put_char(' '); io.put_int((B[i]*mtable.fact(i)).a); }io.put_char('\n'); return 0; }