Submit Info #2000

Problem Lang User Status Time Memory
Bernoulli Number cpp (anonymous) AC 594 ms 16.63 MiB

ケース詳細
Name Status Time Memory
0_00 AC 1 ms 0.68 MiB
100000_00 AC 126 ms 4.59 MiB
10000_00 AC 16 ms 1.05 MiB
1000_00 AC 0 ms 0.74 MiB
100_00 AC 2 ms 0.71 MiB
1_00 AC 2 ms 0.68 MiB
200000_00 AC 270 ms 8.40 MiB
300000_00 AC 566 ms 15.88 MiB
400000_00 AC 583 ms 16.26 MiB
500000_00 AC 594 ms 16.63 MiB
example_00 AC 2 ms 0.68 MiB

#include <bits/stdc++.h> #define ll long long #define INF 1000000005 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)(n);++i) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i) #define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i) #define each(a,b) for(auto& (a): (b)) #define all(v) (v).begin(),(v).end() #define len(v) (int)(v).size() #define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define cmx(x,y) x=max(x,y) #define cmn(x,y) x=min(x,y) #define fi first #define se second #define pb push_back #define show(x) cout<<#x<<" = "<<(x)<<endl #define sar(a,n) {cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl;} using namespace std; template<typename S,typename T>auto&operator<<(ostream&o,pair<S,T>p){return o<<"{"<<p.fi<<","<<p.se<<"}";} template<typename T>auto&operator<<(ostream&o,set<T>s){for(auto&e:s)o<<e<<" ";return o;} template<typename S,typename T,typename U> auto&operator<<(ostream&o,priority_queue<S,T,U>q){while(!q.empty())o<<q.top()<<" ",q.pop();return o;} template<typename K,typename T>auto&operator<<(ostream&o,map<K,T>&m){for(auto&e:m)o<<e<<" ";return o;} template<typename T>auto&operator<<(ostream&o,vector<T>v){for(auto&e:v)o<<e<<" ";return o;} void ashow(){cout<<endl;}template<typename T,typename...A>void ashow(T t,A...a){cout<<t<<" ";ashow(a...);} template<typename S,typename T,typename U> struct TRI{S fi;T se;U th;TRI(){}TRI(S f,T s,U t):fi(f),se(s),th(t){} bool operator<(const TRI&_)const{return(fi==_.fi)?((se==_.se)?(th<_.th):(se<_.se)):(fi<_.fi);}}; template<typename S,typename T,typename U> auto&operator<<(ostream&o,TRI<S,T,U>&t){return o<<"{"<<t.fi<<","<<t.se<<","<<t.th<<"}";} typedef pair<int, int> P; typedef pair<ll, ll> pll; typedef TRI<int, int, int> tri; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<vi> vvi; typedef vector<vl> vvl; typedef vector<P> vp; typedef vector<double> vd; typedef vector<string> vs; const int MAX_N = 100005; #define MOD 998244353 #define root 3 unsigned int add(const unsigned int x, const unsigned int y) { return (x + y < MOD) ? x + y : x + y - MOD; } unsigned int sub(const unsigned int x, const unsigned int y) { return (x >= y) ? (x - y) : (MOD - y + x); } unsigned int mul(const unsigned int x, const unsigned int y) { return (unsigned long long)x * y % MOD; } unsigned int power(unsigned int x, unsigned int n) { unsigned int res = 1; while(n > 0) { if(n & 1) { res = mul(res, x); } x = mul(x, x); n >>= 1; } return res; } unsigned int inverse(const unsigned int x) { return power(x, MOD - 2); } void ntt(vector<int>& a, const bool rev = false) { unsigned int i,j,k,s,t,v,w,wn; const unsigned int size = a.size(); const unsigned int height = (unsigned int)log2(2 * size - 1); for(i = 0; i < size; i++) { j = 0; for(k = 0; k < height; k++) { j |= (i >> k & 1) << (height - 1 - k); } if(i < j) swap(a[i], a[j]); } for(i = 1; i < size; i *= 2) { w = power(root, (MOD - 1) / (i * 2)); if(rev) w = inverse(w); for(j = 0; j < size; j += i * 2) { wn = 1; for(k = 0; k < i; k++) { s = a[j + k + 0], t = mul(a[j + k + i], wn); a[j + k + 0] = add(s, t); a[j + k + i] = add(s, MOD - t); wn = mul(wn, w); } } } if(rev){ v = inverse(size); for (i = 0; i < size; i++) { a[i] = mul(a[i], v); } } } vector<int> convolute(const vector<int>& a, const vector<int>& b, int asize, int bsize, int _size) { const int size = asize + bsize - 1; int t = 1; while (t < size) { t <<= 1; } vector<int> A(t, 0), B(t, 0); for(int i = 0; i < asize; i++) { A[i] = a[i]; } for(int i = 0; i < bsize; i++) { B[i] = b[i]; } ntt(A), ntt(B); for(int i = 0; i < t; i++) { A[i] = mul(A[i], B[i]); } ntt(A, true); A.resize(_size); return A; } vector<int> polynomial_inverse(const vector<int>& a, int r){ vector<int> h = {(int)inverse(a[0])}; int t = 1; for(int i = 0; t < r; ++i){ t <<= 1; vector<int> res = convolute(a, convolute(h, h, t / 2, t / 2, t), min((int)a.size(), t), t, t); for(int j = 0; j < t; ++j){ res[j] = MOD - res[j]; if(j < t / 2) res[j] = add(res[j], mul(2, h[j])); } swap(h, res); } h.resize(r); return h; } vector<int> bernoulli(const int n) { vector<int> a(n + 1, 0); a[0] = 1; for(int i = 1; i <= n; ++i){ a[i] = mul(a[i - 1], inverse(i + 1)); } a = polynomial_inverse(a, n + 1); int mult = 1; for(int i = 1; i <= n; ++i){ a[i] = mul(a[i], mult = mul(mult, i)); } return a; } #define getchar getchar_unlocked #define putchar putchar_unlocked inline int in() { int n = 0; short c; while ((c = getchar()) >= '0') n = n * 10 + c - '0'; return n; } inline void out(int n) { short res[10], i = 0; do { res[i++] = n % 10, n /= 10; } while (n); while (i) putchar(res[--i] + '0'); putchar(' '); } int main() { cin.tie(0); ios::sync_with_stdio(false); int n = in(); auto ans = bernoulli(n); rep(i,n+1){ out(ans[i]); } putchar('\n'); return 0; }