Submit Info #266

Problem Lang User Status Time Memory
Partition Function cpp ei1333 AC 392 ms 97.35 MiB

ケース詳細
Name Status Time Memory
0_00 AC 2 ms 0.72 MiB
100000_00 AC 94 ms 24.67 MiB
10000_00 AC 13 ms 3.57 MiB
1000_00 AC 2 ms 0.91 MiB
100_00 AC 2 ms 0.67 MiB
1_00 AC 3 ms 0.67 MiB
200000_00 AC 193 ms 47.64 MiB
300000_00 AC 378 ms 92.24 MiB
400000_00 AC 387 ms 95.83 MiB
500000_00 AC 392 ms 97.35 MiB
example_00 AC 2 ms 0.72 MiB

#include<bits/stdc++.h> using namespace std; using int64 = long long; const int mod = 998244353; const int64 infll = (1LL << 62) - 1; const int inf = (1 << 30) - 1; struct IoSetup { IoSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } } iosetup; template< typename T1, typename T2 > ostream &operator<<(ostream &os, const pair< T1, T2 > &p) { os << p.first << " " << p.second; return os; } template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; } template< typename T > ostream &operator<<(ostream &os, const vector< T > &v) { for(int i = 0; i < (int) v.size(); i++) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } template< typename T > istream &operator>>(istream &is, vector< T > &v) { for(T &in : v) is >> in; return is; } template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } template< typename T = int64 > vector< T > make_v(size_t a) { return vector< T >(a); } template< typename T, typename... Ts > auto make_v(size_t a, Ts... ts) { return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...)); } template< typename T, typename V > typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) { t = v; } template< typename T, typename V > typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) { for(auto &e : t) fill_v(e, v); } template< typename F > struct FixPoint : F { FixPoint(F &&f) : F(forward< F >(f)) {} template< typename... Args > decltype(auto) operator()(Args &&... args) const { return F::operator()(*this, forward< Args >(args)...); } }; template< typename F > inline decltype(auto) MFP(F &&f) { return FixPoint< F >{forward< F >(f)}; } template< int mod, int primitiveroot > struct NumberTheoreticTransform { vector< vector< int > > rts, rrts; void ensure_base(int N) { if(rts.size() >= N) return; rts.resize(N), rrts.resize(N); for(int i = 1; i < N; i <<= 1) { if(rts[i].size()) continue; int w = mod_pow(primitiveroot, (mod - 1) / (i * 2)); int rw = inverse(w); rts[i].resize(i), rrts[i].resize(i); rts[i][0] = 1, rrts[i][0] = 1; for(int k = 1; k < i; k++) { rts[i][k] = mul(rts[i][k - 1], w); rrts[i][k] = mul(rrts[i][k - 1], rw); } } } inline int mod_pow(int x, int n) { int ret = 1; while(n > 0) { if(n & 1) ret = mul(ret, x); x = mul(x, x); n >>= 1; } return ret; } inline int inverse(int x) { return mod_pow(x, mod - 2); } inline unsigned add(unsigned x, unsigned y) { x += y; if(x >= mod) x -= mod; return x; } inline unsigned mul(unsigned a, unsigned b) { return 1ull * a * b % mod; } void ntt(vector< int > &a, bool rev) { const int N = (int) a.size(); ensure_base(N); for(int i = 0, j = 1; j + 1 < N; j++) { for(int k = N >> 1; k > (i ^= k); k >>= 1); if(i > j) swap(a[i], a[j]); } for(int i = 1; i < N; i <<= 1) { for(int j = 0; j < N; j += i * 2) { for(int k = 0; k < i; k++) { int s = a[j + k], t = mul(a[j + k + i], rev ? rrts[i][k] : rts[i][k]); a[j + k] = add(s, t), a[j + k + i] = add(s, mod - t); } } } if(rev) { int temp = inverse(N); for(int i = 0; i < N; i++) a[i] = mul(a[i], temp); } } vector< int > multiply(vector< int > a, vector< int > b) { int need = a.size() + b.size() - 1; int sz = 1; while(sz < need) sz <<= 1; a.resize(sz, 0); b.resize(sz, 0); ntt(a, false); ntt(b, false); for(int i = 0; i < sz; i++) a[i] = mul(a[i], b[i]); ntt(a, true); return a; } }; template< typename T > struct FormalPowerSeries : vector< T > { using vector< T >::vector; using P = FormalPowerSeries; using MULT = function< P(P, P) >; static MULT &get_mult() { static MULT mult = nullptr; return mult; } static void set_fft(MULT f) { get_mult() = f; } FormalPowerSeries(const vector< T > &v) : FormalPowerSeries(v.begin(), v.end()) {} P operator+(const P &r) const { return P(*this) += r; } P operator-(const P &r) const { return P(*this) -= r; } P operator*(const P &r) const { return P(*this) *= r; } P operator*(const T &v) const { return P(*this) *= v; } P operator/(const P &r) const { return P(*this) /= r; } P &operator+=(const P &r) { if(r.size() > this->size()) this->resize(r.size()); for(int i = 0; i < r.size(); i++) (*this)[i] += r[i]; return *this; } P &operator-=(const P &r) { if(r.size() > this->size()) this->resize(r.size()); for(int i = 0; i < r.size(); i++) (*this)[i] -= r[i]; return *this; } P &operator*=(const T &v) { const int n = (int) this->size(); for(int k = 0; k < n; k++) (*this)[k] *= v; return *this; } P &operator*=(const P &r) { if(this->empty() || r.empty()) { this->clear(); return *this; } assert(get_mult() != nullptr); auto ret = get_mult()(*this, r); this->resize(ret.size()); for(int k = 0; k < ret.size(); k++) (*this)[k] = ret[k]; return *this; } P operator-() const { P ret(this->size()); for(int i = 0; i < this->size(); i++) ret[i] = -(*this)[i]; return ret; } P &operator/=(const P &r) { return *this *= r.inverse(); } P pre(int sz) const { return P(begin(*this), begin(*this) + min((int) this->size(), sz)); } P rev() const { P ret(*this); reverse(begin(ret), end(ret)); return ret; } P diff() const { const int n = (int) this->size(); P ret(max(0, n - 1)); for(int i = 1; i < n; i++) ret[i - 1] = (*this)[i] * T(i); return ret; } P integral() const { const int n = (int) this->size(); P ret(n + 1); ret[0] = T(0); for(int i = 0; i < n; i++) ret[i + 1] = (*this)[i] / T(i + 1); return ret; } // F(0) must not be 0 P inv(int deg = -1) const { assert(((*this)[0]) != T(0)); const int n = (int) this->size(); if(deg == -1) deg = n; P ret({T(1) / (*this)[0]}); for(int i = 1; i < deg; i <<= 1) { ret = (ret * T(2) - ret * ret * pre(i << 1)).pre(i << 1); } return ret.pre(deg); } // F(0) must be 1 P log(int deg = -1) const { assert((*this)[0] == 1); const int n = (int) this->size(); if(deg == -1) deg = n; auto vv = this->diff() * this->inv(deg); return (this->diff() * this->inv(deg)).integral().pre(deg); } // F(0) must be 1 P sqrt(int deg = -1) const { assert((*this)[0] == T(1)); const int n = (int) this->size(); if(deg == -1) deg = n; P ret({T(1)}); T inv2 = T(1) / T(2); for(int i = 1; i < deg; i <<= 1) { ret = (ret + pre(i << 1) * ret.inv(i << 1)) * inv2; } return ret.pre(deg); } // F(0) must be 0 P exp(int deg = -1) const { assert((*this)[0] == T(0)); const int n = (int) this->size(); if(deg == -1) deg = n; P ret({T(1)}), g({T(1)}); for(int i = 1; i < deg; i <<= 1) { ret = (ret * (pre(i << 1) + g - ret.log(i << 1))).pre(i << 1); } return ret.pre(deg); } }; template< int mod > struct ModInt { int x; ModInt() : x(0) {} ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} ModInt &operator+=(const ModInt &p) { if((x += p.x) >= mod) x -= mod; return *this; } ModInt &operator-=(const ModInt &p) { if((x += mod - p.x) >= mod) x -= mod; return *this; } ModInt &operator*=(const ModInt &p) { x = (int) (1LL * x * p.x % mod); return *this; } ModInt &operator/=(const ModInt &p) { *this *= p.inverse(); return *this; } ModInt operator-() const { return ModInt(-x); } ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; } ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; } ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; } ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; } bool operator==(const ModInt &p) const { return x == p.x; } bool operator!=(const ModInt &p) const { return x != p.x; } ModInt inverse() const { int a = x, b = mod, u = 1, v = 0, t; while(b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return ModInt(u); } ModInt pow(int64_t n) const { ModInt ret(1), mul(x); while(n > 0) { if(n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; } friend istream &operator>>(istream &is, ModInt &a) { int64_t t; is >> t; a = ModInt< mod >(t); return (is); } }; using modint = ModInt< mod >; template< typename T > FormalPowerSeries< T > partition(int N) { FormalPowerSeries< T > po(N + 1); po[0] = 1; for(int k = 1; k <= N; k++) { if(1LL * k * (3 * k + 1) / 2 <= N) po[k * (3 * k + 1) / 2] += (k % 2 ? -1 : 1); if(1LL * k * (3 * k - 1) / 2 <= N) po[k * (3 * k - 1) / 2] += (k % 2 ? -1 : 1); } return po.inv(); } int main() { NumberTheoreticTransform< mod, 3 > ntt; using FPS = FormalPowerSeries< modint >; auto mult = [&](const FPS::P &a, const FPS::P &b) { vector< int > x(a.size()), y(b.size()); for(int i = 0; i < a.size(); i++) x[i] = a[i].x; for(int i = 0; i < b.size(); i++) y[i] = b[i].x; auto ret = ntt.multiply(x, y); vector< modint > z(begin(ret), end(ret)); return z; }; FPS::set_fft(mult); int N; cin >> N; cout << partition< modint >(N) << endl; }