Submit Info #34967

Problem Lang User Status Time Memory
Bernoulli Number cpp-acl PCT AC 1221 ms 37.94 MiB

ケース詳細
Name Status Time Memory
0_00 AC 2 ms 0.66 MiB
100000_00 AC 281 ms 9.34 MiB
10000_00 AC 31 ms 1.69 MiB
1000_00 AC 2 ms 0.74 MiB
100_00 AC 1 ms 0.67 MiB
1_00 AC 2 ms 0.67 MiB
200000_00 AC 587 ms 18.38 MiB
300000_00 AC 1211 ms 36.88 MiB
400000_00 AC 1214 ms 37.63 MiB
500000_00 AC 1221 ms 37.94 MiB
example_00 AC 2 ms 0.67 MiB

#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using ll = long long; using ld = long double; #define all(s) (s).begin(),(s).end() #define vcin(n) for(ll i=0;i<ll(n.size());i++) cin>>n[i] #define rep2(i, m, n) for (int i = (m); i < (n); ++i) #define rep(i, n) rep2(i, 0, n) #define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i) #define drep(i, n) drep2(i, n, 0) #define rever(vec) reverse(vec.begin(), vec.end()) #define sor(vec) sort(vec.begin(), vec.end()) const ll mod = 998244353; const ll inf = 2000000000000000000ll; static const long double pi = 3.141592653589793; template<class T,class U> void chmax(T& t,const U& u){if(t<u) t=u;} template<class T,class U> void chmin(T& t,const U& u){if(t>u) t=u;} ll modPow(ll a, ll n, ll mod) { ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; } template<class T> struct FormalPowerSeries:vector<T>{ using vector<T>::vector; using vector<T>::operator=; using F=FormalPowerSeries; F operator-() const{ F res(*this); for(auto &e:res) e=-e; return res; } F &operator*=(const T &g){ for(auto &e:*this) e*=g; return *this; } F &operator/=(const T &g){ assert(g!=T(0)); *this*=g.inv(); return *this; } F &operator+=(const F &g){ int n=(*this).size(),m=g.size(); for(int i=0;i<min(n,m);i++){ (*this)[i]+=g[i]; } return *this; } F &operator-=(const F &g){ int n=(*this).size(),m=g.size(); for(int i=0;i<min(n,m);i++){ (*this)[i]-=g[i]; } return *this; } F &operator<<=(const int d) { int n=(*this).size(); (*this).insert((*this).begin(),d,0); (*this).resize(n); return *this; } F &operator>>=(const int d) { int n=(*this).size(); (*this).erase((*this).begin(),(*this).begin()+min(n, d)); (*this).resize(n); return *this; } F inv(int d=-1) const{ int n=(*this).size(); assert(n!=0&&(*this)[0]!=0); if(d==-1) d=n; assert(d>0); F res{(*this)[0].inv()}; while(res.size()<d){ int m=size(res); F f(begin(*this),begin(*this)+min(n,2*m)); F r(res); f.resize(2*m); r.resize(2*m); vector<T> s=convolution(f,r); s.resize(2*m); for(int i=0;i<2*m;i++){ s[i]=-s[i]; } s[0]+=2; vector<T> g=convolution(s,r); g.resize(2*m); res=g; } res.resize(n); return res; } F &operator*=(const F &g){ int n=(*this).size(); *this=convolution(*this,g); (*this).resize(n); return (*this); } F &operator/=(const F &g){ int n=(*this).size(); *this=convolution(*this,g.inv()); (*this).resize(n); return (*this); } void onemultiply(const int d,const T c){ int n=(*this).size(); for(int i=n-d-1;i>=0;i--){ (*this)[i+d]+=(*this)[i]*c; } } void onediv(const int d,const T c){ int n=(*this).size(); for(int i=n-d-1;i>=0;i--){ (*this)[i+d]-=(*this)[i]*c; } } T eval(const T &a) const { T x(1),res(0); for(auto e:*this) res+=e*x,x*=a; return res; } F differential() const { int n=(*this).size(); F res(n); for(int i=0;i<n-1;i++){ res[i]=T(i+1)*(*this)[i+1]; } res[n-1]=0; return res; } F Integral() const { int n=(*this).size(); F res(n); for(int i=1;i<n;i++){ res[i]=(*this)[i-1]/T(i); } res[0]=0; return res; } F log() const{ int n=(*this).size(); F u=(*this).differential(); F d=(*this); u/=d; u=u.Integral(); u.resize(n); return u; } F exp(int d=-1) const{ int n=(*this).size(); assert(n!=0&&(*this)[0]==0); if(d==-1) d=n; assert(d>0); F res{1}; while(int(res.size())<d){ int m=size(res); F f(begin(*this),begin(*this)+min(n,2*m)); F r(res); f.resize(2*m); r.resize(2*m); r=r.log(); f-=r; f[0]++; F g=f*res; g.resize(2*m); res=g; } res.resize(n); return res; } F operator*(const T &g) const { return F(*this)*=g;} F operator-(const T &g) const { return F(*this)-=g;} F operator*(const F &g) const { return F(*this)*=g;} F operator-(const F &g) const { return F(*this)-=g;} F operator+(const F &g) const { return F(*this)+=g;} F operator/(const F &g) const { return F(*this)/=g;} F operator<<(const int d) const { return F(*this)<<=d;} F operator>>(const int d) const { return F(*this)>>=d;} }; using mint=modint998244353; using fps = FormalPowerSeries<mint>; int main() { /* mod は 1e9+7 */ ios::sync_with_stdio(false); std::cin.tie(nullptr); cout<< fixed << setprecision(10); ll n; cin>>n; n++; fps f(n+1); fps g(n+1); for(int i=0;i<n+1;i++){ f[i]=0; g[i]=0; } f[1]=1; f=f.exp(); f>>=1; mint a=1; f=f.inv(); for(int i=0;i<n;i++){ f[i]*=a; cout<<f[i].val()<<" "; a*=i+1; } }