Submit Info #11880

Problem Lang User Status Time Memory
Partition Function cpp Bogdan AC 863 ms 7.30 MiB

ケース詳細
Name Status Time Memory
0_00 AC 833 ms 2.55 MiB
100000_00 AC 838 ms 3.55 MiB
10000_00 AC 840 ms 2.68 MiB
1000_00 AC 837 ms 2.55 MiB
100_00 AC 841 ms 2.53 MiB
1_00 AC 832 ms 2.55 MiB
200000_00 AC 847 ms 4.50 MiB
300000_00 AC 855 ms 5.42 MiB
400000_00 AC 859 ms 6.30 MiB
500000_00 AC 863 ms 7.30 MiB
example_00 AC 832 ms 2.61 MiB

#ifdef DEBUG #define _GLIBCXX_DEBUG #endif //#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; typedef long double ld; typedef long long ll; const int mod = 998244353; const int root = 646; const int root_1 = 208611436; const int root_pw = 1 << 20; int mult(int a, int b) { return (1LL * a * b) % mod; } int pw(int a, int b) { if (b == 0) return 1; if (b & 1) return mult(a, pw(a, b - 1)); int res = pw(a, b / 2); return mult(res, res); } int sub(int a, int b) { int s = a - b; if (s < 0) s += mod; return s; } int sum(int a, int b) { int s = a + b; if (s >= mod) s -= mod; return s; } void fft(vector<int> &a, bool invert) { int n = (int) a.size(); for (int i = 1, j = 0; i < n; ++i) { int bit = n >> 1; for (; j >= bit; bit >>= 1) j -= bit; j += bit; if (i < j) swap(a[i], a[j]); } for (int len = 2; len <= n; len <<= 1) { int wlen = invert ? root_1 : root; for (int i = len; i < root_pw; i <<= 1) wlen = int(wlen * 1ll * wlen % mod); for (int i = 0; i < n; i += len) { int w = 1; for (int j = 0; j < len / 2; ++j) { int u = a[i + j], v = int(a[i + j + len / 2] * 1ll * w % mod); a[i + j] = u + v < mod ? u + v : u + v - mod; a[i + j + len / 2] = u - v >= 0 ? u - v : u - v + mod; w = int(w * 1ll * wlen % mod); } } } if (invert) { int nrev = pw(n, mod - 2); for (int i = 0; i < n; ++i) a[i] = int(a[i] * 1ll * nrev % mod); } } void poly_mult(vector<int> &a, vector<int> b) { if (min(a.size(), b.size()) < 128) { vector<int> c = a; a.assign(a.size() + b.size() - 1, 0); for (int i = 0; i < c.size(); ++i) { for (int j = 0; j < b.size(); ++j) { a[i + j] = sum(a[i + j], mult(c[i], b[j])); } } return; } int s = a.size() + b.size(); int r = 1; while (r < s) r *= 2; a.resize(r); b.resize(r); fft(a, false); fft(b, false); for (int j = 0; j < r; j++) { a[j] = mult(a[j], b[j]); } fft(a, true); a.resize(s - 1); } vector<int> inversePoly(vector<int> a) { int n = a.size(), m = (n + 1) >> 1; if (n == 1) { return vector<int>(1, pw(a[0], mod -2)); } else { vector<int> b = inversePoly(vector<int>(a.begin(), a.begin() + m)); int need = n << 1, nbase = 0; while (1 << nbase < need) { ++nbase; } int sz = 1 << nbase; assert(a.size() + 2 * b.size() <= sz); a.resize(sz); b.resize(sz); fft(a, false); fft(b, false); for (int i = 0; i < sz; ++i) { a[i] = mult(sub(2, mult(a[i], b[i])), b[i]); } fft(a, true); a.resize(n); return a; } } int n; const int maxN = 5e5 + 10; int p[maxN]; void count_partitions() { p[0] = 1; for (int i = 1; i < maxN; i++) { for (int r = 1; (r * (3 * r - 1)) <= 2 * i; r++) { for (int iter = -1; iter <= 1; iter += 2) { int c = (r * (3 * r + iter)) / 2; if (c <= i) { if (r & 1) p[i] = sum(p[i], p[i - c]); else p[i] = sub(p[i], p[i - c]); } } } } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // freopen("input.txt", "r", stdin); cin >> n; count_partitions(); for (int i = 0; i <= n; i++) { cout << p[i] << " "; } return 0; }