Submit Info #11879

Problem Lang User Status Time Memory
Partition Function cpp Bogdan AC 332 ms 13.04 MiB

ケース詳細
Name Status Time Memory
0_00 AC 3 ms 0.67 MiB
100000_00 AC 78 ms 4.03 MiB
10000_00 AC 9 ms 1.12 MiB
1000_00 AC 4 ms 0.75 MiB
100_00 AC 0 ms 0.68 MiB
1_00 AC 1 ms 0.68 MiB
200000_00 AC 157 ms 6.91 MiB
300000_00 AC 320 ms 12.04 MiB
400000_00 AC 327 ms 12.69 MiB
500000_00 AC 332 ms 13.04 MiB
example_00 AC 0 ms 0.67 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; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // freopen("input.txt", "r", stdin); cin >> n; vector < int > ans(n + 1); ans[0] = 1; for (int r = 1; r * (3 * r - 1) <= 2 * n; r++) { for (int iter = -1; iter <= 1; iter += 2) { int c = (r * (3 * r + iter)) / 2; if (c <= n) { if (r & 1) { ans[c] = mod - 1; } else { ans[c] = 1; } } } } auto pans = inversePoly(ans); pans.resize(n + 1); for (int v : pans) cout << v << " "; return 0; }