Submit Info #15860

Problem Lang User Status Time Memory
Partition Function cpp AlphaQ AC 1684 ms 33.90 MiB

ケース詳細
Name Status Time Memory
0_00 AC 1 ms 0.67 MiB
100000_00 AC 317 ms 8.15 MiB
10000_00 AC 20 ms 1.33 MiB
1000_00 AC 4 ms 0.82 MiB
100_00 AC 3 ms 0.72 MiB
1_00 AC 0 ms 0.73 MiB
200000_00 AC 707 ms 15.55 MiB
300000_00 AC 777 ms 19.09 MiB
400000_00 AC 1593 ms 30.50 MiB
500000_00 AC 1684 ms 33.90 MiB
example_00 AC 1 ms 0.72 MiB

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int G = 3; const int MOD = 998244353; const int N = (1 << 20) + 5; int rev[N], w[N], inv_n; int bigMod (int a, int e, int mod) { if (e == -1) e = mod - 2; int ret = 1; while (e) { if (e & 1) ret = (ll) ret * a % mod; a = (ll) a * a % mod; e >>= 1; } return ret; } void prepare (int &n) { int sz = abs(31 - __builtin_clz(n)); int r = bigMod(G, (MOD - 1) / n, MOD); inv_n = bigMod(n, MOD - 2, MOD), w[0] = w[n] = 1; for (int i = 1; i < n; ++i) w[i] = (ll) w[i - 1] * r % MOD; for (int i = 1; i < n; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (sz - 1)); } void ntt (int *a, int n, int dir) { for (int i = 1; i < n - 1; ++i) { if (i < rev[i]) swap(a[i], a[rev[i]]); } for (int m = 2; m <= n; m <<= 1) { for (int i = 0; i < n; i += m) { for (int j = 0; j < (m >> 1); ++j) { int &u = a[i + j], &v = a[i + j + (m >> 1)]; int t = (ll) v * w[dir ? n - n / m * j : n / m * j] % MOD; v = u - t < 0 ? u - t + MOD : u - t; u = u + t >= MOD ? u + t - MOD : u + t; } } } if (dir) for (int i = 0; i < n; ++i) a[i] = (ll) a[i] * inv_n % MOD; } int f_a[N], f_b[N]; vector <int> multiply (vector <int> a, vector <int> b) { int sz = 1, n = a.size(), m = b.size(); while (sz < n + m - 1) sz <<= 1; prepare(sz); for (int i = 0; i < sz; ++i) f_a[i] = i < n ? a[i] : 0; for (int i = 0; i < sz; ++i) f_b[i] = i < m ? b[i] : 0; ntt(f_a, sz, 0); ntt(f_b, sz, 0); for (int i = 0; i < sz; ++i) f_a[i] = (ll) f_a[i] * f_b[i] % MOD; ntt(f_a, sz, 1); return vector <int> (f_a, f_a + n + m - 1); } inline int add (int x, int y) { return x + y < MOD ? x + y : x + y - MOD; } inline int sub (int x, int y) { return x < y ? x - y + MOD : x - y; } int n, sig[N], p[N], inv[N]; void solve (int l, int r) { if (l == r) return void(p[l] = (ll) p[l] * inv[l] % MOD); int mid = l + r >> 1; solve(l, mid); vector <int> a(p + l, p + mid + 1), b(sig, sig + r - l + 1); vector <int> c = multiply(a, b); for (int i = mid - l + 1; i < min((int) c.size(), r - l + 1); ++i) { p[l + i] = add(p[l + i], c[i]); } solve(mid + 1, r); } int main() { cin >> n; inv[0] = 1; for (int i = 1; i <= n; ++i) { inv[i] = (i > 1) ? ((MOD - (ll) (MOD / i) * inv[MOD % i] % MOD) % MOD) : 1; for (int j = i; j <= n; j += i) sig[j] += i; } p[0] = 1; solve(0, n); for (int i = 0; i <= n; ++i) printf("%d ", p[i]); puts(""); return 0; }