Submit Info #17732

Problem Lang User Status Time Memory
Partition Function cpp14 Tweetuzki AC 1247 ms 57.32 MiB

ケース詳細
Name Status Time Memory
0_00 AC 1 ms 0.61 MiB
100000_00 AC 272 ms 14.42 MiB
10000_00 AC 28 ms 2.42 MiB
1000_00 AC 2 ms 0.91 MiB
100_00 AC 2 ms 0.68 MiB
1_00 AC 1 ms 0.61 MiB
200000_00 AC 578 ms 27.96 MiB
300000_00 AC 1213 ms 52.41 MiB
400000_00 AC 1234 ms 54.50 MiB
500000_00 AC 1247 ms 57.32 MiB
example_00 AC 1 ms 0.67 MiB

#include <algorithm> #include <cstdio> #include <cstring> const int MaxN = 500000; const int Mod = 998244353, Prt = 114514; int N, M; int A[MaxN + 5]; inline int add(int x, int y) { return (x += y) >= Mod ? x - Mod : x; } inline int sub(int x, int y) { return (x -= y) < 0 ? x + Mod : x; } inline int mul(int x, int y) { return 1LL * x * y % Mod; } inline int pw(int x, int y) { int z = 1; for (; y; y >>= 1, x = mul(x, x)) if (y & 1) z = mul(z, x); return z; } inline int inv(int x) { return pw(x, Mod - 2); } inline int sep(int x, int y) { return mul(x, inv(y)); } inline void inc(int &x, int y = 1) { (x += y) >= Mod ? x -= Mod : 0; } inline void dec(int &x, int y = 1) { (x -= y) < 0 ? x += Mod : 0; } namespace polynomial { const int MaxV = (1 << 20), MaxLog = 20; int rev[MaxLog + 1][MaxV + 5], w[2][MaxV + 5], lg2[MaxV + 5]; inline int get_v(int n) { int v = 1; while (v < n) v <<= 1; return v; } void init(int n) { int v = get_v(n + n - 1); lg2[1] = 0; for (int i = 2; i <= v; i <<= 1) lg2[i] = lg2[i >> 1] + 1; for (int n = 1; n <= v; n <<= 1) { w[0][n] = pw(Prt, (Mod - 1) / (n << 1)); w[1][n] = pw(inv(Prt), (Mod - 1) / (n << 1)); int l = lg2[n]; rev[l][0] = 0; for (int i = 1; i < n; ++i) { rev[l][i] = rev[l][i >> 1] >> 1; if (i & 1) rev[l][i] |= (n >> 1); } } } inline void set(int *a, int val, int begin, int end) { memset(a + begin, val, (end - begin) << 2); } inline void set(int *a, int *b, int begin, int end) { memcpy(a + begin, b, (end - begin) << 2); } inline void ntt(int *a, int n, int f) { for (int i = 0; i < n; ++i) if (i < rev[lg2[n]][i]) std::swap(a[i], a[rev[lg2[n]][i]]); for (int i = 1; i < n; i <<= 1) { int _w = w[f][i]; for (int j = 0; j < n; j += (i << 1)) { int x = 1; for (int k = 0; k < i; ++k, x = mul(x, _w)) { int ls = a[j + k], rs = mul(a[i + j + k], x); a[j + k] = add(ls, rs); a[i + j + k] = sub(ls, rs); } } } if (f == 1) { int invn = inv(n); for (int i = 0; i < n; ++i) a[i] = mul(a[i], invn); } } inline void polyInv(int *a, int *b, int n) { if (n == 1) { b[0] = inv(a[0]); return; } polyInv(a, b, (n + 1) >> 1); static int f[MaxV + 5], g[MaxV + 5], h[MaxV + 5]; int v = get_v(n + n - 1); set(g, a, 0, n), set(g, 0, n, v); set(h, b, 0, n), set(h, 0, n, v); ntt(g, v, 0), ntt(h, v, 0); for (int i = 0; i < v; ++i) f[i] = sub(mul(h[i], 2), mul(g[i], mul(h[i], h[i]))); ntt(f, v, 1); set(b, f, 0, n); } inline void polyDeri(int *a, int *b, int n) { for (int i = 0; i < n - 1; ++i) b[i] = mul(i + 1, a[i + 1]); } inline void polyInt(int *a, int *b, int n) { b[0] = 0; static int mem_inver[MaxV + 5]; mem_inver[1] = 1; for (int i = 2; i < n; ++i) mem_inver[i] = mul(Mod - Mod / i, mem_inver[Mod % i]); for (int i = 0; i < n - 1; ++i) b[i + 1] = mul(a[i], mem_inver[i + 1]); } inline void polyLn(int *a, int *b, int n) { static int f[MaxV + 5], g[MaxV + 5], h[MaxV + 5]; int v = get_v(n + n - 1); set(f, 0, 0, v), set(g, 0, 0, v), set(h, 0, 0, v); polyDeri(a, g, n); polyInv(a, h, n); ntt(g, v, 0), ntt(h, v, 0); for (int i = 0; i < v; ++i) f[i] = mul(g[i], h[i]); ntt(f, v, 1); polyInt(f, b, n); } inline void polyExp(int *a, int *b, int n) { if (n == 1) { b[0] = 1; return; } polyExp(a, b, (n + 1) >> 1); int v = get_v(n + n - 1); static int f[MaxV + 5], g[MaxV + 5], h[MaxV + 5]; set(g, b, 0, n), set(g, 0, n, v); polyLn(g, h, n), set(h, 0, n, v); for (int i = 0; i < n; ++i) h[i] = sub(a[i], h[i]); inc(h[0]); ntt(g, v, 0), ntt(h, v, 0); for (int i = 0; i < v; ++i) f[i] = mul(g[i], h[i]); ntt(f, v, 1); set(b, f, 0, n); } } void init() { scanf("%d", &N); N++; static int inv[MaxN + 5]; inv[1] = 1; for (int i = 2; i < N; ++i) inv[i] = mul(Mod - Mod / i, inv[Mod % i]); for (int i = 1; i < N; ++i) for (int j = 1; i * j < N; ++j) inc(A[i * j], inv[j]); } void solve() { polynomial::init(N); static int b[MaxN + 5]; polynomial::polyExp(A, b, N); for (int i = 0; i < N; ++i) printf("%d%c", b[i], " \n"[i == N - 1]); } int main() { init(); solve(); return 0; }