Submit Info #572

Problem Lang User Status Time Memory
Bernoulli Number cpp ryuhei AC 239 ms 29.31 MiB

ケース詳細
Name Status Time Memory
0_00 AC 229 ms 23.67 MiB
100000_00 AC 235 ms 24.82 MiB
10000_00 AC 219 ms 23.79 MiB
1000_00 AC 229 ms 23.62 MiB
100_00 AC 230 ms 23.64 MiB
1_00 AC 226 ms 23.67 MiB
200000_00 AC 236 ms 25.90 MiB
300000_00 AC 226 ms 27.13 MiB
400000_00 AC 234 ms 28.25 MiB
500000_00 AC 239 ms 29.31 MiB
example_00 AC 227 ms 23.67 MiB

#include <unistd.h> #include <cassert> 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;} }; template <int MOD> struct Mint { int n; static constexpr int s = __builtin_ctz(MOD - 1); static constexpr int q = MOD >> __builtin_ctz(MOD - 1); static constexpr Mint<MOD> c0 = []() constexpr { int z = 0; for(z = 2; z < MOD; z++){ if(Mint<MOD>(z).pow((MOD - 1) / 2) != 1) break; } return Mint<MOD>(z).pow(MOD >> __builtin_ctz(MOD-1)); }(); constexpr Mint(int n = 0): n(n) {} constexpr Mint<MOD> operator -(){ return n ? MOD - n: 0; } constexpr void operator -= (const Mint<MOD> &rhs){ if(n >= rhs.n) n -= rhs.n; else n = MOD - (rhs.n - n); } constexpr void operator += (const Mint<MOD> &rhs){ n += rhs.n; if(n >= MOD) n -= MOD; } constexpr void operator *= (const Mint<MOD> &rhs){ n = (long long) n * rhs.n % MOD; } constexpr void operator /= (const Mint<MOD> &rhs){ n = (long long) n * rhs.inv().n % MOD; } constexpr bool operator == (const Mint<MOD> &rhs) const { return n == rhs.n; } constexpr bool operator != (const Mint<MOD> &rhs) const { return n != rhs.n; } friend constexpr Mint<MOD> operator - (const Mint<MOD> &lhs, const Mint<MOD> &rhs){ Mint<MOD> r = lhs; r -= rhs; return r; } friend constexpr Mint<MOD> operator + (const Mint<MOD> &lhs, const Mint<MOD> &rhs){ Mint<MOD> r = lhs; r += rhs; return r; } friend constexpr Mint<MOD> operator * (const Mint<MOD> &lhs, const Mint<MOD> &rhs){ Mint<MOD> r = lhs; r *= rhs; return r; } friend constexpr Mint<MOD> operator / (const Mint<MOD> &lhs, const Mint<MOD> &rhs){ Mint<MOD> r = lhs; r /= rhs; return r; } constexpr Mint<MOD> pow(int n) const { Mint<MOD> r = 1; Mint<MOD> x = *this; for(; n; n >>= 1){ if(n & 1) r *= x; x *= x; } return r; } constexpr Mint<MOD> inv() const { return pow(MOD - 2); } Mint<MOD> sqrt() const { if(n == 0) return 0; if(pow((MOD - 1) / 2) != 1){ return MOD; } int m = s; Mint<MOD> c = c0; Mint<MOD> t = pow(q); Mint<MOD> r = pow((q + 1) / 2); while(t != 1){ int i; Mint<MOD> u = t * t; for(i = 1; u != 1; i++) u = u * u; int j = 1; int k = m - i - 1; while(k--){ j = j + j; if(j >= MOD) j -= MOD; } Mint<MOD> b = c.pow(j); m = i; c = b * b; t = t * c; r = r * b; } return r; } }; template <int MOD, int N> struct Minv { Mint<MOD> inv[N+1]; constexpr Minv(): inv() { inv[1] = 1; for(int i = 2; i <= N; i++) inv[i] = (MOD - MOD / i) * inv[MOD % i]; } constexpr Mint<MOD> operator[](int i) const { return inv[i]; } }; template <int MOD, int K> struct FFT { Mint<MOD> w[1<<(K-1)]; Mint<MOD> y[1<<(K-1)]; Mint<MOD> v[1<<(K-2)]; static constexpr Mint<MOD> root = []() constexpr { bool sieve[1<<16] = {}; int factors[1<<16] = {}; int fs = 0; int t = MOD - 1; int i = 0; for(; t % 2 == 0; t /= 2) i++; factors[fs++] = (MOD - 1) / 2; if(i < K) return Mint<MOD>(0); for(int i = 3; (long long) i * i < t; i += 2){ if(!sieve[i]){ for(int j = 3 * i; (long long) j * j < t; j += 2 * i) sieve[j] = true; if(t % i == 0){ factors[fs++] = (MOD - 1) / i; do { t /= i; } while(t % i == 0); } } } if(t != 1) factors[fs++] = (MOD - 1) / t; for(int i = 2; i < MOD; i++){ int j = 0; for(j = 0; j < fs; j++){ if(Mint<MOD>(i).pow(factors[j]) == 1) break; } if(j == fs) return Mint<MOD>(i).pow(MOD >> K); } return Mint<MOD>(0); }(); FFT(): w(), y(), v() { const int m = 1 << K; static_assert(root != 0); Mint<MOD> z = root; Mint<MOD> x = z.pow(MOD-2); for(int j=m/4; j; j>>=1){ w[j] = z; z *= z; y[j] = x; x *= x; } w[0] = y[0] = 1; for(int j = 2; j < m / 2; j <<= 1){ for(int i = 1; i < j; i++){ w[j + i] = w[j] * w[i]; y[j + i] = y[j] * y[i]; } } v[0] = 1; for(long unsigned int i = 1; i < sizeof(v)/sizeof(v[0]); i++) v[i] = root * v[i - 1]; } void fft(Mint<MOD> *A, int k = K) const { int u = 1; int v = 1 << (k-1); for(int i=k;i>0;i--){ for(int jh=0;jh<u;jh++){ Mint<MOD> wj = w[jh]; for(int j = jh << i, je = j+v;j<je; j++){ Mint<MOD> Ajv = wj * A[j+v]; A[j+v] = A[j] - Ajv; A[j] = A[j] + Ajv; } } u <<= 1; v >>= 1; } } void ifft(Mint<MOD> *A, int k = K) const { int u = 1 << (k-1); int v = 1; for(int i=1;i<=k;i++){ for(int jh=0;jh<u;jh++){ Mint<MOD> wj = y[jh]; for(int j = jh << i, je = j+v;j<je; j++){ Mint<MOD> Ajv = A[j] - A[j+v]; A[j] = A[j] + A[j+v]; A[j+v] = wj * Ajv; } } u >>= 1; v <<= 1; } } }; template <int MOD, int K> struct Poly { Mint<MOD> c[1 << (K + 1)]; inline static FFT<MOD, K + 1> fft; inline static Minv<MOD, (1 << K) - 1> minv; // static constexpr auto minv = Minv<MOD, (1 << K) - 1>(); // static constexpr auto fft = FFT<MOD, K + 1>(); void operator += (const Poly<MOD, K>& rhs){ for(int i = 0; i < (1 << K); i++) c[i] += rhs.c[i]; } void operator -= (const Poly<MOD, K>& rhs){ for(int i = 0; i < (1 << K); i++) c[i] -= rhs.c[i]; } void operator *= (const Poly<MOD, K>& rhs){ Mint<MOD> D[1 << (K + 1)] = {}; for(int i = 0; i < (1 << (K + 0)); i++) D[i] = rhs.c[i]; fft.fft(c); fft.fft(D); const Mint<MOD> t = Mint<MOD>((MOD+1)/2).pow(K+1); for(int i = 0; i < (1 << (K + 1)); i++) c[i] *= D[i] * t; fft.ifft(c); } // Graeffe's method: 2 M(n) Poly<MOD, K> inv() const { assert(c[0] != 0); Mint<MOD> d[1 << (K + 2)]; Mint<MOD> c0inv = Mint<MOD>(c[0]).pow(MOD-2); for(int i = 0; i < (1 << K); i++) d[i] = c[i] * c0inv; fft.fft(d); int k = K + 1; Mint<MOD> *Q = d; Mint<MOD> im = Mint<MOD>((1+MOD)/2).pow(k-1); while(k>1){ Mint<MOD> *QQ = Q + (1<<k); for(int i = 0; i < (1 << (k - 1)); i++) QQ[i] = Q[2*i] * Q[2*i+1]; Q = QQ; k--; fft.ifft(Q, k); for(int i = 0; i < (1 << (k - 1)); i++){ Q[i] = Q[i] * im; Q[(1 << (k - 1)) + i] = 0; } im += im; fft.fft(QQ, k); } int normal = 0; while(Q > d){ Mint<MOD> *QQ = Q - (1 << (k + 1)); for(int i = 0; i < (1 << k); i++){ Mint<MOD> tmp0 = QQ[2*i] * Q[i]; Mint<MOD> tmp1 = QQ[2*i+1] * Q[i]; QQ[2*i] = tmp1; QQ[2*i+1] = tmp0; } k++; Q = QQ; fft.ifft(Q, k); for(int i = (1 << (k - 1)); i < (1 << k); i++) Q[i] = 0; fft.fft(Q, k); normal += k; } fft.ifft(Q, k); normal += k; Mint<MOD> iim = Mint<MOD>((1+MOD)/2).pow(normal) * c0inv; Poly<MOD, K> r; for(int i = 0; i < (1 << K); i++) r.c[i] = d[i] * iim; return r; } /* // Newton 1.5 M(n) Poly<MOD, K> invN() const { Mint<MOD> d[4*(1 << K)]; Mint<MOD> e[1 << (K + 1)]; e[0] = 1; for(int i = 0; i < K; i++){ for(int j = 0; j < (1 << (i+1)); j++) d[j] = c[j]; fft.fft(d, 4*(1 << i)); fft.fft(e, 4*(1 << i)); for(int j = 0; j < 4*(1 << i); j++) d[j] *= e[j] * e[j]; fft.ifft(d, 4*(1 << i)); for(int j = 1 << i; j < (1 << (i+1)); j++) e[j] = MOD - d[j]; } Poly<MOD, K> r; for(int i = 0; i < (1 << K); i++) r.c[i] = e[i]; return r; } */ // Newton: 2 M(n) Poly<MOD, K> isqrt() const { assert(c[0] == 1); Mint<MOD> d[1 << (K + 1)] = {}; Mint<MOD> e[1 << K] = {}; Mint<MOD> ee[1 << (K + 1)] = {}; e[0] = 1; int y = (MOD+1)/2; if(y&1) y += MOD; y /= 2; if(y&1) y += MOD; y /= 2; Mint<MOD> im = y; for(int i = 0; i < K; i++){ for(int j = 0; j < (1 << (i+1)); j++) d[j] = c[j]; fft.fft(d, i + 2); for(int j = 0; j < (1 << i); j++) ee[j] = e[j]; for(int j = (1 << i); j < (1 << (i + 1)); j++) ee[j] = 0; fft.fft(ee, i + 2); for(int j = 0; j < (1 << (i + 2)); j++) d[j] *= ee[j] * ee[j] * ee[j] * im; fft.ifft(d, i + 2); for(int j = 1 << i; j < (1 << (i + 1)); j++) e[j] = -d[j]; if(im.n&1) im.n += MOD; im.n /= 2; } Poly<MOD, K> r; for(int i = 0; i < (1 << K); i++) r.c[i] = e[i]; return r; } // Newton: (1 + 1/2 + (1/4)*(2/3) + (1/2)*(2/3)) M(n) = 2 M(n) Poly<MOD, K> sqrt() const { assert(c[0] == 1); Poly<MOD, K-1> g; Mint<MOD> d[1 << K] = {}; Mint<MOD> e[1 << (K-1)] = {}; Mint<MOD> f[1 << K] = {}; for(int i = 0; i < (1 << (K - 1)); i++) g.c[i] = d[i] = c[i]; Poly<MOD, K-1> gg = g.isqrt(); fft.fft(d, K); fft.fft(gg.c, K); for(int i = 0; i < (1 << K); i++) f[i] = gg.c[i]; Mint<MOD> im0 = Mint<MOD>((1+MOD)/2).pow(K + 1); Mint<MOD> im1 = im0 + im0; Mint<MOD> im2 = im1 + im1; for(int i = 0; i < (1 << K); i++) gg.c[i] *= d[i] * im1; fft.ifft(gg.c, K); for(int i = 0; i < (1 << (K - 1)); i++) e[i] = gg.c[i]; fft.fft(e, K - 1); for(int i = 0; i < (1 << (K - 1)); i++) e[i] *= e[i] * im2; fft.ifft(e, K - 1); for(int i = 0; i < (1 << (K - 1)); i++) d[i] = c[i + (1 << (K - 1))] + c[i] - e[i]; for(int i = (1 << (K - 1)); i < (1 << K); i++) d[i] = 0; fft.fft(d, K); for(int i = 0; i < (1 << K); i++) d[i] *= f[i] * im0; fft.ifft(d, K); for(int i = 0; i < (1 << (K - 1)); i++) gg.c[i + (1 << (K - 1))] = d[i]; Poly<MOD, K> r; for(int i = 0; i < (1 << K); i++) r.c[i] = gg.c[i]; return r; } // Newton (5/6 + (1/2)*(2/3) + 1 + 2/3) M(n) = 17/6 M(n) Poly<MOD, K> exp() const { assert(c[0] == 0); Mint<MOD> f[1 << K] = {}; Mint<MOD> g[1 << (K-1)] = {}; Mint<MOD> ff[1 << K] = {}; Mint<MOD> gg[1 << K] = {}; Mint<MOD> G[1 << K] = {}; f[0] = 1; f[1] = c[1]; g[0] = 1; G[0] = G[1] = 1; int y = (MOD+1)/2; if(y&1) y += MOD; y /= 2; Mint<MOD> im = y; for(int i = 1; i < K; i++){ for(int j = 0; j < (1 << i); j++) ff[j] = f[j] * im; fft.fft(ff, i + 1); /* for(int j = 0; j < (1 << (i - 1)); j++) gg[j] = g[j]; for(int j = (1 << (i - 1)); j < (1 << i); j++) gg[j] = 0; fft.fft(gg, i + 1); */ for(int j = 0; j < (1 << i); j++) gg[j] = G[j]; for(int j = 0; j < (1 << (i - 1)); j++) gg[j + (1 << i)] = fft.v[j << (K - i)] * g[j]; fft.fft(gg + (1 << i), i); for(int j = 0; j < (1 << (i + 1)); j++) gg[j] *= gg[j] * ff[j]; fft.ifft(gg, i + 1); for(int j = 1 << (i - 1); j < (1 << i); j++) g[j] = -gg[j]; for(int j = 0; j < (1 << i) - 1; j++) gg[j] = c[j + 1] * (j + 1); gg[(1 << i) - 1] = 0; fft.fft(gg, i); for(int j = 0; j < (1 << i); j++) gg[j] *= ff[j], gg[j] += gg[j]; fft.ifft(gg, i); Mint<MOD> tmp = -gg[(1 << i) - 1]; for(int j = (1 << i) - 1; j; j--) gg[j] = f[j] * j - gg[j - 1]; gg[0] = tmp; for(int j = (1 << i); j < (1 << (i + 1)); j++) gg[j] = 0; fft.fft(gg, i + 1); for(int j = 0; j < (1 << i); j++) G[j] = g[j]; fft.fft(G, i + 1); for(int j = 0; j < (1 << (i + 1)); j++) gg[j] *= G[j] * im; fft.ifft(gg, i + 1); for(int j = 0; j < (1 << i); j++) gg[j] = c[j + (1 << i)] - gg[j] * minv[(1 << i) + j]; for(int j = (1 << i); j < (1 << (i + 1)); j++) gg[j] = 0; fft.fft(gg, i + 1); for(int j = 0; j < (1 << (i + 1)); j++) ff[j] *= gg[j]; fft.ifft(ff, i + 1); for(int j = 0; j < (1 << i); j++) f[j + (1 << i)] = ff[j]; if(im.n&1) im.n += MOD; im.n /= 2; } Poly<MOD, K> r; for(int i = 0; i < (1 << K); i++) r.c[i] = f[i]; return r; } }; /* template <int MOD, int K> FFT<MOD, K + 1> Poly<MOD, K>::fft; template <int MOD, int K> Minv<MOD, (1 << K) - 1> Poly<MOD, K>::minv; */ IO io; constexpr int mod = 998244353; constexpr int K = 19; int main(){ Poly<mod, K> A; int n = io.scan_int(); A.c[0] = 1; for(int i=1;i<=n;i++){ A.c[i] = A.c[i-1] * Poly<mod, K>::minv[i + 1]; } Poly<mod, K> B = A.inv(); Mint<mod> z = 1; for(int i=0;i<=n;i++){ io.put_int((B.c[i] * z).n, ' '); z *= i + 1; } io.put_char('\n'); return 0; }