Submit Info #9371

Problem Lang User Status Time Memory
Bernoulli Number cpp (anonymous) AC 555 ms 27.09 MiB

ケース詳細
Name Status Time Memory
0_00 AC 8 ms 4.67 MiB
100000_00 AC 127 ms 10.01 MiB
10000_00 AC 21 ms 5.30 MiB
1000_00 AC 9 ms 4.76 MiB
100_00 AC 10 ms 4.66 MiB
1_00 AC 9 ms 4.67 MiB
200000_00 AC 258 ms 14.68 MiB
300000_00 AC 534 ms 24.79 MiB
400000_00 AC 545 ms 25.97 MiB
500000_00 AC 555 ms 27.09 MiB
example_00 AC 8 ms 4.67 MiB

#include <bits/stdc++.h> using namespace std; constexpr int kMod = 998244353; int fpow(int a, int n) { int res = 1; while (n > 0) { if (n & 1) res = 1LL * res * a % kMod; a = 1LL * a * a % kMod; n >>= 1; } return res; } namespace ntt { constexpr int kN = 1048576; constexpr int kRoot = 3; vector<int> omega; void Init() { omega.resize(kN + 1); long long x = fpow(kRoot, (kMod - 1) / kN); omega[0] = 1; for (int i = 1; i <= kN; ++i) { omega[i] = 1LL * omega[i - 1] * x % kMod; } } void BitReverse(vector<int> &v, int n) { int z = __builtin_ctz(n) - 1; for (int i = 0; i < n; ++i) { int x = 0; for (int j = 0; j <= z; ++j) x ^= (i >> j & 1) << (z - j); if (x > i) swap(v[x], v[i]); } } void Transform(vector<int> &v, int n) { BitReverse(v, n); for (int s = 2; s <= n; s <<= 1) { int z = s >> 1; for (int i = 0; i < n; i += s) { for (int k = 0; k < z; ++k) { int x = 1LL * v[i + k + z] * omega[kN / s * k] % kMod; v[i + k + z] = (v[i + k] + kMod - x) % kMod; (v[i + k] += x) %= kMod; } } } } void InverseTransform(vector<int> &v, int n) { Transform(v, n); for (int i = 1; i < n / 2; ++i) swap(v[i], v[n - i]); const int kInv = fpow(n, kMod - 2); for (int i = 0; i < n; ++i) v[i] = 1LL * v[i] * kInv % kMod; } } // namespace ntt int Jacobi(int a, int m) { int s = 1; for (; m > 1;) { a %= m; if (a == 0) return 0; const int r = __builtin_ctz(a); if ((r & 1) && ((m + 2) & 4)) s = -s; a >>= r; if (a & m & 2) s = -s; swap(a, m); } return s; } int QuadraticResidue(int a, int p) { if (p == 2) return a & 1; const int jc = Jacobi(a, p); if (jc == 0 || jc == -1) return jc; int b, d; for (;;) { b = rand() % p; d = (1LL * b * b + p - a) % p; if (Jacobi(d, p) == -1) break; } int f0 = b, f1 = 1, g0 = 1, g1 = 0, tmp; for (int e = (p + 1) >> 1; e; e >>= 1) { if (e & 1) { tmp = (1LL * g0 * f0 + 1LL * d * (1LL * g1 * f1 % p)) % p; g1 = (1LL * g0 * f1 + 1LL * g1 * f0) % p; g0 = tmp; } tmp = (1LL * f0 * f0 + 1LL * d * (1LL * f1 * f1 % p)) % p; f1 = (2LL * f0 * f1) % p; f0 = tmp; } return g0; } namespace poly { using Poly = vector<int>; Poly Multiply(Poly a, Poly b) { int n = a.size(), m = b.size(), k = 1; while (k < n + m - 1) k <<= 1; a.resize(k); b.resize(k); ntt::Transform(a, k); ntt::Transform(b, k); for (int i = 0; i < k; ++i) { a[i] = 1LL * a[i] * b[i] % kMod; } ntt::InverseTransform(a, k); a.resize(n + m - 1); return a; } Poly Inverse(Poly f) { int n = f.size(); Poly q(1, fpow(f[0], kMod - 2)); for (int s = 2;; s <<= 1) { if (f.size() < s) f.resize(s); Poly fv(f.begin(), f.begin() + s); Poly fq(q.begin(), q.end()); fv.resize(s + s); fq.resize(s + s); ntt::Transform(fv, s + s); ntt::Transform(fq, s + s); for (int i = 0; i < s + s; ++i) { fv[i] = 1LL * fv[i] * fq[i] % kMod * fq[i] % kMod; } ntt::InverseTransform(fv, s + s); Poly res(s); for (int i = 0; i < s; ++i) { res[i] = kMod - fv[i]; if (i < (s >> 1)) { int v = 2 * q[i] % kMod; (res[i] += v) >= kMod ? res[i] -= kMod : 0; } } q = res; if (s >= n) break; } q.resize(n); return q; } Poly Divide(const Poly &a, const Poly &b) { int n = a.size(), m = b.size(), k = 2; while (k < n - m + 1) k <<= 1; Poly ra(k), rb(k); for (int i = 0; i < min(n, k); ++i) ra[i] = a[n - 1 - i]; for (int i = 0; i < min(m, k); ++i) rb[i] = b[m - 1 - i]; auto rbi = Inverse(rb); auto res = Multiply(rbi, ra); res.resize(n - m + 1); reverse(res.begin(), res.end()); return res; } Poly Modulo(const Poly &a, const Poly &b) { if (a.size() < b.size()) return a; auto dv = Multiply(Divide(a, b), b); assert(dv.size() == a.size()); for (int i = 0; i < dv.size(); ++i) { dv[i] = (a[i] + kMod - dv[i]) % kMod; } while (!dv.empty() && dv.back() == 0) dv.pop_back(); return dv; } Poly Derivative(const Poly &f) { int n = f.size(); vector<int> res(n - 1); for (int i = 0; i < n - 1; ++i) { res[i] = 1LL * f[i + 1] * (i + 1) % kMod; } return res; } Poly Integral(const Poly &f) { int n = f.size(); vector<int> res(n + 1); for (int i = 0; i < n; ++i) { res[i + 1] = 1LL * f[i] * fpow(i + 1, kMod - 2) % kMod; } return res; } Poly Evaluate(const Poly &f, const vector<int> &x) { if (x.empty()) return Poly(); int n = x.size(); vector<Poly> up(n * 2); for (int i = 0; i < n; ++i) up[i + n] = {kMod - x[i], 1}; for (int i = n - 1; i > 0; --i) up[i] = Multiply(up[i * 2], up[i * 2 + 1]); vector<Poly> down(n * 2); down[1] = Modulo(f, up[1]); for (int i = 2; i < n * 2; ++i) down[i] = Modulo(down[i >> 1], up[i]); vector<int> y(n); for (int i = 0; i < n; ++i) y[i] = down[i + n][0]; return y; } Poly Interpolate(const vector<int> &x, const vector<int> &y) { int n = x.size(); vector<Poly> up(n * 2); for (int i = 0; i < n; ++i) up[i + n] = {kMod - x[i], 1}; for (int i = n - 1; i > 0; --i) up[i] = Multiply(up[i * 2], up[i * 2 + 1]); vector<int> a = Evaluate(Derivative(up[1]), x); for (int i = 0; i < n; ++i) { a[i] = 1LL * y[i] * fpow(a[i], kMod - 2) % kMod; } vector<Poly> down(n * 2); for (int i = 0; i < n; ++i) down[i + n] = {a[i]}; for (int i = n - 1; i > 0; --i) { auto lhs = Multiply(down[i * 2], up[i * 2 + 1]); auto rhs = Multiply(down[i * 2 + 1], up[i * 2]); assert(lhs.size() == rhs.size()); down[i].resize(lhs.size()); for (int j = 0; j < lhs.size(); ++j) { down[i][j] = (lhs[j] + rhs[j]) % kMod; } } return down[1]; } Poly Log(Poly f) { int n = f.size(); if (n == 1) return {0}; auto d = Derivative(f); f.resize(n - 1); d = Multiply(d, Inverse(f)); d.resize(n - 1); return Integral(d); } Poly Exp(Poly f) { int n = f.size(); Poly q(1, 1); f[0] += 1; for (int s = 1; s < n; s <<= 1) { if (f.size() < s + s) f.resize(s + s); Poly g(f.begin(), f.begin() + s + s); Poly h(q.begin(), q.end()); h.resize(s + s); h = Log(h); for (int i = 0; i < s + s; ++i) { g[i] = (g[i] + kMod - h[i]) % kMod; } g = Multiply(g, q); g.resize(s + s); q = g; } assert(q.size() >= n); q.resize(n); return q; } Poly SquareRootImpl(Poly f) { if (f.empty()) return {0}; int z = QuadraticResidue(f[0], kMod), n = f.size(); constexpr int kInv2 = (kMod + 1) >> 1; if (z == -1) return {-1}; vector<int> q(1, z); for (int s = 1; s < n; s <<= 1) { if (f.size() < s + s) f.resize(s + s); vector<int> fq(q.begin(), q.end()); fq.resize(s + s); vector<int> f2 = Multiply(fq, fq); f2.resize(s + s); for (int i = 0; i < s + s; ++i) { f2[i] = (f2[i] + kMod - f[i]) % kMod; } f2 = Multiply(f2, Inverse(fq)); f2.resize(s + s); for (int i = 0; i < s + s; ++i) { fq[i] = (fq[i] + kMod - 1LL * f2[i] * kInv2 % kMod) % kMod; } q = fq; } q.resize(n); return q; } Poly SquareRoot(Poly f) { int n = f.size(), m = 0; while (m < n && f[m] == 0) m++; if (m == n) return vector<int>(n); if (m & 1) return {-1}; auto s = SquareRootImpl(vector<int>(f.begin() + m, f.end())); if (s[0] == -1) return {-1}; vector<int> res(n); for (int i = 0; i < s.size(); ++i) res[i + m / 2] = s[i]; return res; } vector<int> Bernoulli(int n) { vector<int> fc(n + 2, 1), iv(n + 2); for (int i = 1; i <= n + 1; ++i) { fc[i] = 1LL * fc[i - 1] * i % kMod; } iv[n + 1] = fpow(fc[n + 1], kMod - 2); for (int i = n; i >= 0; --i) { iv[i] = 1LL * iv[i + 1] * (i + 1) % kMod; } Poly ex(iv.begin() + 1, iv.end()); ex = Inverse(ex); for (int i = 1; i <= n; ++i) { ex[i] = 1LL * ex[i] * fc[i] % kMod; } return ex; } } // namespace poly int main() { ios_base::sync_with_stdio(false); cin.tie(0); ntt::Init(); int n; cin >> n; auto b = poly::Bernoulli(n); for (int i = 0; i <= n; ++i) cout << b[i] << " "; cout << "\n"; }