Submit Info #51227

Problem Lang User Status Time Memory
Bernoulli Number cpp alaneos777 AC 439 ms 36.31 MiB

ケース詳細
Name Status Time Memory
0_00 AC 1 ms 0.37 MiB
100000_00 AC 99 ms 9.16 MiB
10000_00 AC 11 ms 1.66 MiB
1000_00 AC 1 ms 0.71 MiB
100_00 AC 1 ms 0.71 MiB
1_00 AC 1 ms 0.71 MiB
200000_00 AC 212 ms 17.71 MiB
300000_00 AC 428 ms 33.31 MiB
400000_00 AC 434 ms 34.82 MiB
500000_00 AC 439 ms 36.31 MiB
example_00 AC 1 ms 0.61 MiB

#include <bits/stdc++.h> using namespace std; using lli = long long int; using poly = vector<int>; template<lli mod> lli powerMod(lli a, lli b){ lli ans = 1; while(b){ if(b & 1) ans = ans * a % mod; b >>= 1; a = a * a % mod; } return ans; } int nearestPowerOfTwo(int n){ int ans = 1; while(ans < n) ans <<= 1; return ans; } template<int mod, int g> void ntt(poly& a, int inv = 1){ int n = a.size(); for(int i = 1, j = 0; i < n-1; ++i){ for(int k = n>>1; (j^=k) < k; k >>= 1); if(i < j) swap(a[i], a[j]); } for(int sz = 2; sz <= n; sz <<= 1){ lli w_1 = powerMod<mod>(g, (mod-1)/sz); if(inv == -1) w_1 = powerMod<mod>(w_1, mod-2); vector<lli> w(sz/2, 1); for(int j = 1; j < sz/2; ++j){ w[j] = w_1 * w[j-1] % mod; } for(int start = 0; start < n; start += sz){ for(int j = 0; j < sz/2; ++j){ int u = a[start + j], v = w[j] * a[start + sz/2 + j] % mod; a[start + j] = (u+v >= mod ? u+v-mod : u+v); a[start + sz/2 + j] = (u-v < 0 ? u-v+mod : u-v); } } } if(inv == -1){ lli n_rev = powerMod<mod>(n, mod-2); for(int& ai : a){ ai = ai * n_rev % mod; } } } template<int mod, int g> poly convolution(poly a, poly b){ int sz = a.size() + b.size() - 1; int SZ = nearestPowerOfTwo(sz); a.resize(SZ), b.resize(SZ); ntt<mod, g>(a, 1), ntt<mod, g>(b, 1); poly c(SZ); for(int i = 0; i < SZ; ++i){ c[i] = (lli)a[i] * b[i] % mod; } ntt<mod, g>(c, -1); c.resize(sz); return c; } const int p = 998244353, g = 3; poly inversePolynomial(const poly & A){ poly R(1, powerMod<p>(A[0], p - 2)); while(R.size() < A.size()){ size_t c = 2 * R.size(); R.resize(c); poly R2 = R; poly a(min(c, A.size())); for(int i = 0; i < a.size(); ++i) a[i] = A[i]; R2 = convolution<p, g>(R2, R2); R2.resize(c); R2 = convolution<p, g>(R2, a); for(int i = 0; i < c; ++i){ R[i] = R[i] + R[i] - R2[i]; if(R[i] < 0) R[i] += p; if(R[i] >= p) R[i] -= p; } } R.resize(A.size()); return R; } int main(){ ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; poly fact(n+2, 1), inv(n+2, 1), invfact(n+2, 1); for(lli i = 2; i <= n+1; ++i){ fact[i] = i * fact[i-1] % p; inv[i] = p - (p / i) * inv[p % i] % p; invfact[i] = (lli)inv[i] * invfact[i-1] % p; } poly ans(n+1); for(int i = 0; i <= n; ++i){ ans[i] = invfact[i+1]; if(i&1) ans[i] = p - ans[i]; } ans = inversePolynomial(ans); for(int i = 0; i <= n; ++i){ ans[i] = (lli)ans[i] * fact[i] % p; } if(n >= 1) ans[1]--; for(int ai : ans){ cout << ai << " "; } cout << "\n"; return 0; }