Submit Info #1815

Problem Lang User Status Time Memory
Bernoulli Number cpp firiexp AC 551 ms 87.34 MiB

ケース詳細
Name Status Time Memory
0_00 AC 2 ms 0.68 MiB
100000_00 AC 127 ms 21.88 MiB
10000_00 AC 16 ms 3.21 MiB
1000_00 AC 0 ms 0.80 MiB
100_00 AC 3 ms 0.68 MiB
1_00 AC 2 ms 0.67 MiB
200000_00 AC 263 ms 43.06 MiB
300000_00 AC 530 ms 83.86 MiB
400000_00 AC 538 ms 85.67 MiB
500000_00 AC 551 ms 87.34 MiB
example_00 AC 0 ms 0.67 MiB

#include <iostream> #include <algorithm> #include <iomanip> #include <map> #include <set> #include <queue> #include <stack> #include <numeric> #include <bitset> #include <cmath> static const int MOD = 998244353; using ll = long long; using u32 = unsigned; using u64 = unsigned long long; using namespace std; template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208; constexpr int ntt_mod = 998244353, ntt_root = 3; // 1012924417 -> 5, 924844033 -> 5 // 998244353 -> 3, 897581057 -> 3 // 645922817 -> 3; template<u32 M = 1000000007> struct modint{ u32 val; modint(): val(0){} template<typename T> explicit modint(T t){t %= (T)M; if(t < 0) t += (T)M; val = t;} modint pow(ll k) const { modint res(1), x(val); while(k){ if(k&1) res *= x; x *= x; k >>= 1; } return res; } template<typename T> modint& operator=(T t){t %= (T)M; if(t < 0) t += (T)M; val = t; return *this; } modint inv() const {return pow(M-2);} modint& operator+=(modint a){ val += a.val; if(val >= M) val -= M; return *this;} modint& operator-=(modint a){ if(val < a.val) val += M-a.val; else val -= a.val; return *this;} modint& operator*=(modint a){ val = (u64)val*a.val%M; return *this;} modint& operator/=(modint a){ return (*this) *= a.inv();} modint operator+(modint a) const {return modint(val) +=a;} modint operator-(modint a) const {return modint(val) -=a;} modint operator*(modint a) const {return modint(val) *=a;} modint operator/(modint a) const {return modint(val) /=a;} modint operator-(){ return modint(M-val);} bool operator==(const modint a) const {return val == a.val;} bool operator!=(const modint a) const {return val != a.val;} bool operator<(const modint a) const {return val < a.val;} }; using mint = modint<ntt_mod>; template<int M, int proot> class NTT { vector<vector<mint>> rts, rrts; public: NTT() = default; void ensure_base(int N) { if(rts.size() >= N) return; rts.resize(N), rrts.resize(N); for(int i = 1; i < N; i <<= 1) { if(!rts[i].empty()) continue; mint w = mint(proot).pow((M-1) / (i << 1)); mint rw = w.inv(); rts[i].resize(i), rrts[i].resize(i); rts[i][0] = 1, rrts[i][0] = 1; for(int k = 1; k < i; k++) { rts[i][k] = rts[i][k-1]*w; rrts[i][k] = rrts[i][k-1]*rw; } } } void ntt(vector<mint> &a, int sign){ int n = a.size(); ensure_base(n); for (int i = 0, j = 1; j < n-1; ++j) { for (int k = n >> 1; k > (i ^= k); k >>= 1); if(j < i) swap(a[i], a[j]); } for (int i = 1; i < n; i <<= 1) { for (int j = 0; j < n; j += i << 1) { for (int k = 0; k < i; ++k) { mint y = a[j+k+i]*(sign ? rrts[i][k] : rts[i][k]); a[j+k+i] = a[j+k]-y, a[j+k] += y; } } } if(sign) { mint temp = mint(n).inv(); for (int i = 0; i < n; ++i) a[i] *= temp; } } }; NTT<ntt_mod, ntt_root> ntt; struct poly { vector<mint> v; poly() = default; explicit poly(int n) : v(n) {}; explicit poly(vector<mint> vv) : v(std::move(vv)) {}; int size() const {return (int)v.size(); } poly cut(int len){ if(len < v.size()) v.resize(static_cast<unsigned long>(len)); return *this; } inline mint& operator[] (int i) {return v[i]; } poly operator+(const poly &a) const { return poly(*this) += a; } poly operator-(const poly &a) const { return poly(*this) -= a; } poly operator*(const poly &a) const { return poly(*this) *= a; } poly inv() const { int n = size(); poly r(1); r[0] = (this->v[0]).inv(); int k = 1; while(k < n){ k *= 2; poly ff(k); for (int i = 0; i < min(k, n); ++i) { ff[i] = this->v[i]; } poly nr = r*r*ff; nr.cut(k); for (int i = 0; i < k/2; ++i) { nr[i] = (r[i]+r[i]-nr[i]); nr[i+k/2] = -nr[i+k/2]; } r = nr; } r.v.resize(n); return r; } poly& operator+=(const poly &a) { this->v.resize(max(size(), a.size())); for (int i = 0; i < a.size(); ++i) { (this->v[i] += a.v[i]); } return *this; } poly& operator-=(const poly &a) { this->v.resize(max(size(), a.size())); for (int i = 0; i < a.size(); ++i) { (this->v[i] -= a.v[i]); } return *this; } poly& operator*=(poly a) { int N = size()+a.size()-1; int sz = 1; while(sz < N) sz <<= 1; ntt.ensure_base(sz); this->v.resize(sz); a.v.resize(sz); ntt.ntt(this->v, 0); ntt.ntt(a.v, 0); for(int i = 0; i < sz; ++i) this->v[i] *= a.v[i]; ntt.ntt(this->v, 1); return *this; } poly& operator/=(const poly &a){ return (*this *= a.inv()); } }; class Factorial { vector<mint> facts, factinv; public: explicit Factorial(int n) : facts(static_cast<u32>(n+1)), factinv(static_cast<u32>(n+1)) { facts[0] = 1; for (int i = 1; i < n+1; ++i) facts[i] = facts[i-1]*mint(i); factinv[n] = facts[n].inv(); for (int i = n-1; i >= 0; --i) factinv[i] = factinv[i+1] * mint(i+1); } mint fact(int k) const { if(k >= 0) return facts[k]; else return factinv[-k]; } mint operator[](const int &k) const { if(k >= 0) return facts[k]; else return factinv[-k]; } mint C(int p, int q) const { if(q < 0 || p < q) return mint(0); return facts[p] * factinv[q] * factinv[p-q]; } mint P(int p, int q) const { if(q < 0 || p < q) return mint(0); return facts[p] * factinv[p-q]; } mint H(int p, int q) const { if(p < 0 || q < 0) return mint(0); return q == 0 ? mint(1) : C(p+q-1, q); } }; using mint = modint<MOD>; int main() { int n; cin >> n; n++; Factorial f(n); poly a(n); for (int i = 0; i < n; ++i) { a[i] = f[-(i+1)]; } poly c = a.inv(); for (int i = 0; i < n; ++i) { if(i) printf(" "); printf("%d", (c[i]*f[i]).val); } puts(""); return 0; }