Submit Info #1989

Problem Lang User Status Time Memory
Partition Function cpp (anonymous) AC 596 ms 16.55 MiB

ケース詳細
Name Status Time Memory
0_00 AC 2 ms 0.72 MiB
100000_00 AC 125 ms 4.53 MiB
10000_00 AC 17 ms 1.05 MiB
1000_00 AC 2 ms 0.71 MiB
100_00 AC 0 ms 0.67 MiB
1_00 AC 1 ms 0.67 MiB
200000_00 AC 275 ms 8.39 MiB
300000_00 AC 571 ms 15.79 MiB
400000_00 AC 571 ms 16.26 MiB
500000_00 AC 596 ms 16.55 MiB
example_00 AC 1 ms 0.72 MiB

#include <bits/stdc++.h> #define ll long long #define INF 1000000005 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)(n);++i) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i) #define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i) #define each(a,b) for(auto& (a): (b)) #define all(v) (v).begin(),(v).end() #define len(v) (int)(v).size() #define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define cmx(x,y) x=max(x,y) #define cmn(x,y) x=min(x,y) #define fi first #define se second #define pb push_back #define show(x) cout<<#x<<" = "<<(x)<<endl #define sar(a,n) {cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl;} using namespace std; template<typename S,typename T>auto&operator<<(ostream&o,pair<S,T>p){return o<<"{"<<p.fi<<","<<p.se<<"}";} template<typename T>auto&operator<<(ostream&o,set<T>s){for(auto&e:s)o<<e<<" ";return o;} template<typename S,typename T,typename U> auto&operator<<(ostream&o,priority_queue<S,T,U>q){while(!q.empty())o<<q.top()<<" ",q.pop();return o;} template<typename K,typename T>auto&operator<<(ostream&o,map<K,T>&m){for(auto&e:m)o<<e<<" ";return o;} template<typename T>auto&operator<<(ostream&o,vector<T>v){for(auto&e:v)o<<e<<" ";return o;} void ashow(){cout<<endl;}template<typename T,typename...A>void ashow(T t,A...a){cout<<t<<" ";ashow(a...);} template<typename S,typename T,typename U> struct TRI{S fi;T se;U th;TRI(){}TRI(S f,T s,U t):fi(f),se(s),th(t){} bool operator<(const TRI&_)const{return(fi==_.fi)?((se==_.se)?(th<_.th):(se<_.se)):(fi<_.fi);}}; template<typename S,typename T,typename U> auto&operator<<(ostream&o,TRI<S,T,U>&t){return o<<"{"<<t.fi<<","<<t.se<<","<<t.th<<"}";} typedef pair<int, int> P; typedef pair<ll, ll> pll; typedef TRI<int, int, int> tri; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<vi> vvi; typedef vector<vl> vvl; typedef vector<P> vp; typedef vector<double> vd; typedef vector<string> vs; const int MAX_N = 100005; #define MOD 998244353 #define root 3 template <unsigned int mod> class ModInt { private: static unsigned int norm(const unsigned int& x){ return x < mod ? x : x - mod; } static ModInt make(const unsigned int& x){ ModInt m; return m.v = x, m; } static ModInt inv(const ModInt& x){ return make(inverse(x.v, mod)); } static unsigned int inverse(int a, int m){ int u[] = {a, 1, 0}, v[] = {m, 0, 1}, t; while(*v){ t = *u / *v; swap(u[0] -= t * v[0], v[0]), swap(u[1] -= t * v[1], v[1]), swap(u[2] -= t * v[2], v[2]); } return (u[1] % m + m) % m; } public: unsigned int v; ModInt() : v{0}{} ModInt(const long long val) : v{norm(val % mod + mod)} {} ModInt(const ModInt<mod>& n) : v{n()} {} explicit operator bool() const noexcept { return v != 0; } bool operator!() const noexcept { return !static_cast<bool>(*this); } ModInt& operator=(const ModInt& n){ return v = n(), (*this); } ModInt& operator=(const long long val){ return v = norm(val % mod + mod), (*this); } ModInt operator+() const { return *this; } ModInt operator-() const { return v == 0 ? make(0) : make(mod - v); } ModInt operator+(const ModInt& val) const { return make(norm(v + val())); } ModInt operator-(const ModInt& val) const { return make(norm(v + mod - val())); } ModInt operator*(const ModInt& val) const { return make((long long)v * val() % mod); } ModInt operator/(const ModInt& val) const { return *this * inv(val); } ModInt& operator+=(const ModInt& val){ return *this = *this + val; } ModInt& operator-=(const ModInt& val){ return *this = *this - val; } ModInt& operator*=(const ModInt& val){ return *this = *this * val; } ModInt& operator/=(const ModInt& val){ return *this = *this / val; } ModInt operator+(const long long val) const { return ModInt{v + val}; } ModInt operator-(const long long val) const { return ModInt{v - val}; } ModInt operator*(const long long val) const { return ModInt{(long long)v * (val % mod)}; } ModInt operator/(const long long val) const { return ModInt{(long long)v * inv(val)}; } ModInt& operator+=(const long long val){ return *this = *this + val; } ModInt& operator-=(const long long val){ return *this = *this - val; } ModInt& operator*=(const long long val){ return *this = *this * val; } ModInt& operator/=(const long long val){ return *this = *this / val; } bool operator==(const ModInt& val) const { return v == val.v; } bool operator!=(const ModInt& val) const { return !(*this == val); } bool operator==(const long long val) const { return v == norm(val % mod + mod); } bool operator!=(const long long val) const { return !(*this == val); } unsigned int operator()() const { return v; } friend ModInt operator+(const long long val, const ModInt& n) { return n + val; } friend ModInt operator-(const long long val, const ModInt& n) { return ModInt{val - n()}; } friend ModInt operator*(const long long val, const ModInt& n) { return n * val; } friend ModInt operator/(const long long val, const ModInt& n) { return ModInt{val} / n; } friend bool operator==(const long long val, const ModInt& n) { return n == val; } friend bool operator!=(const long long val, const ModInt& n) { return !(val == n); } friend istream& operator>>(istream& is, ModInt& n){ unsigned int v; return is >> v, n = v, is; } friend ostream& operator<<(ostream& os, const ModInt& n){ return (os << n()); } friend ModInt mod_pow(ModInt x, long long n){ ModInt ans = 1; while(n){ if(n & 1) ans *= x; x *= x, n >>= 1; } return ans; } }; using mod = ModInt<MOD>; void ntt(vector<mod>& a, const bool rev = false) { unsigned int i,j,k; mod s,t,v,w,wn; const unsigned int size = a.size(); const unsigned int height = (unsigned int)log2(2 * size - 1); for(i = 0; i < size; i++) { j = 0; for(k = 0; k < height; k++) { j |= (i >> k & 1) << (height - 1 - k); } if(i < j) swap(a[i], a[j]); } for(i = 1; i < size; i *= 2) { w = mod_pow((mod)root, (MOD - 1) / (i * 2)); if(rev) w = 1 / w; for(j = 0; j < size; j += i * 2) { wn = 1; for(k = 0; k < i; k++) { s = a[j + k + 0], t = a[j + k + i] * wn; a[j + k + 0] = s + t; a[j + k + i] = s + MOD - t; wn *= w; } } } if(rev){ v = 1 / (mod)size; for (i = 0; i < size; i++) { a[i] *= v; } } } vector<mod> convolute (const vector<mod>& a, const vector<mod>& b, int asize, int bsize, int _size) { const int size = asize + bsize - 1; int t = 1; while (t < size) { t <<= 1; } vector<mod> A(t, 0), B(t, 0); for(int i = 0; i < asize; i++) { A[i] = a[i]; } for(int i = 0; i < bsize; i++) { B[i] = b[i]; } ntt(A), ntt(B); for(int i = 0; i < t; i++) { A[i] *= B[i]; } ntt(A, true); A.resize(_size); return A; } vector<mod> polynomial_inverse(const vector<mod>& a, int r){ vector<mod> h = {1 / a[0]}; int t = 1; for(int i = 0; t < r; ++i){ t <<= 1; vector<mod> res = convolute(a, convolute(h, h, t / 2, t / 2, t), min((int)a.size(), t), t, t); for(int j = 0; j < t; ++j){ res[j] = MOD - res[j]; if(j < t / 2) res[j] += 2 * h[j]; } swap(h, res); } h.resize(r); return h; } vector<mod> partition_function(const int n){ vector<mod> a(n + 1, 0); a[0] = 1; for(long long i = 1; i <= n; ++i){ const ll p = i * (3 * i + 1) / 2, q = i * (3 * i - 1) / 2; if(p <= n) a[p] += ((i % 2) ? -1 : 1); if(q <= n) a[q] += ((i % 2) ? -1 : 1); } return polynomial_inverse(a, n + 1); } #define getchar getchar_unlocked #define putchar putchar_unlocked inline int in() { int n = 0; short c; while ((c = getchar()) >= '0') n = n * 10 + c - '0'; return n; } inline void out(int n) { short res[10], i = 0; do { res[i++] = n % 10, n /= 10; } while (n); while (i) putchar(res[--i] + '0'); putchar(' '); } int main() { int n = in(); const vector<mod> ans = partition_function(n); rep(i,n+1){ out(ans[i].v); } putchar('\n'); return 0; }