Submit Info #51201

Problem Lang User Status Time Memory
Partition Function cpp alaneos777 AC 436 ms 26.55 MiB

ケース詳細
Name Status Time Memory
0_00 AC 1 ms 0.61 MiB
100000_00 AC 99 ms 6.86 MiB
10000_00 AC 12 ms 1.36 MiB
1000_00 AC 1 ms 0.70 MiB
100_00 AC 1 ms 0.37 MiB
1_00 AC 1 ms 0.61 MiB
200000_00 AC 213 ms 13.21 MiB
300000_00 AC 424 ms 24.93 MiB
400000_00 AC 430 ms 25.78 MiB
500000_00 AC 436 ms 26.55 MiB
example_00 AC 1 ms 0.61 MiB

#include <bits/stdc++.h> using namespace std; using lli = long long int; int nearestPowerOfTwo(int n){ int ans = 1; while(ans < n) ans <<= 1; return ans; } lli powerMod(lli b, lli e, lli m){ lli ans = 1; e %= m-1; if(e < 0) e += m-1; while(e){ if(e & 1) ans = ans * b % m; e >>= 1; b = b * b % m; } return ans; } template<int p, int g> void ntt(vector<int> & X, int inv){ int n = X.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(X[i], X[j]); } vector<lli> wp(n>>1, 1); for(int k = 1; k < n; k <<= 1){ lli wk = powerMod(g, inv * (p - 1) / (k<<1), p); for(int j = 1; j < k; ++j) wp[j] = wp[j - 1] * wk % p; for(int i = 0; i < n; i += k << 1){ for(int j = 0; j < k; ++j){ int u = X[i + j], v = X[i + j + k] * wp[j] % p; X[i + j] = u + v < p ? u + v : u + v - p; X[i + j + k] = u - v < 0 ? u - v + p : u - v; } } } if(inv == -1){ lli nrev = powerMod(n, p - 2, p); for(int i = 0; i < n; ++i) X[i] = X[i] * nrev % p; } } template<int p, int g> vector<int> convolution(vector<int> A, vector<int> B){ int sz = A.size() + B.size() - 1; int size = nearestPowerOfTwo(sz); A.resize(size), B.resize(size); ntt<p, g>(A, 1), ntt<p, g>(B, 1); for(int i = 0; i < size; i++) A[i] = (lli)A[i] * B[i] % p; ntt<p, g>(A, -1); A.resize(sz); return A; } const int p = 998244353, g = 3; vector<int> inversePolynomial(const vector<int> & A){ vector<int> R(1, powerMod(A[0], p - 2, p)); while(R.size() < A.size()){ size_t c = 2 * R.size(); R.resize(c); vector<int> R2 = R; vector<int> 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(){ int N; cin >> N; vector<int> P(N+1); P[0] = 1; for(int n = 1; n*(3*n+1)/2 <= N; ++n){ if(n & 1) P[n*(3*n+1)/2] -= 1; else P[n*(3*n+1)/2] += 1; } for(int n = 1; n*(3*n-1)/2 <= N; ++n){ if(n & 1) P[n*(3*n-1)/2] -= 1; else P[n*(3*n-1)/2] += 1; } for(int& pi : P){ pi %= p; if(pi < 0) pi += p; } P = inversePolynomial(P); for(int pi : P){ cout << pi << " "; } cout << "\n"; return 0; }