Submit Info #55108

Problem Lang User Status Time Memory
Partition Function cpp-acl PCTprobability AC 130 ms 10.64 MiB

ケース詳細
Name Status Time Memory
0_00 AC 1 ms 0.61 MiB
100000_00 AC 30 ms 3.07 MiB
10000_00 AC 4 ms 1.01 MiB
1000_00 AC 1 ms 0.70 MiB
100_00 AC 1 ms 0.71 MiB
1_00 AC 1 ms 0.61 MiB
200000_00 AC 62 ms 5.42 MiB
300000_00 AC 120 ms 9.89 MiB
400000_00 AC 125 ms 10.27 MiB
500000_00 AC 130 ms 10.64 MiB
example_00 AC 1 ms 0.61 MiB

#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("Ofast") #include <bits/stdc++.h> #include <unistd.h> using namespace std; #if __has_include(<atcoder/all>) #include <atcoder/all> using namespace atcoder; #endif using ll = long long; using ld = long double; using ull = unsigned long long; #define endl "\n" typedef pair<int, int> Pii; #define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i)) #define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define ALL(x) begin(x), end(x) #define all(s) (s).begin(),(s).end() //#define rep2(i, m, n) for (int i = (m); i < (n); ++i) //#define rep(i, n) rep2(i, 0, n) #define PB push_back #define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i) #define drep(i, n) drep2(i, n, 0) #define rever(vec) reverse(vec.begin(), vec.end()) #define sor(vec) sort(vec.begin(), vec.end()) //#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++) #define fi first #define se second #define pb push_back #define P pair<ll,ll> #define NP next_permutation //const ll mod = 1000000009; //const ll mod = 998244353; const ll mod = 1000000007; const ll inf = 9100000000000000000ll; const ld eps = ld(0.0000000000001); static const long double pi = 3.141592653589793; template<class T>void vcin(vector<T> &n){for(int i=0;i<int(n.size());i++) cin>>n[i];} template<class T,class K>void vcin(vector<T> &n,vector<K> &m){for(int i=0;i<int(n.size());i++) cin>>n[i]>>m[i];} template<class T>void vcout(vector<T> &n){for(int i=0;i<int(n.size());i++){cout<<n[i]<<" ";}cout<<endl;} template<class T>void vcin(vector<vector<T>> &n){for(int i=0;i<int(n.size());i++){for(int j=0;j<int(n[i].size());j++){cin>>n[i][j];}}} template<class T>void vcout(vector<vector<T>> &n){for(int i=0;i<int(n.size());i++){for(int j=0;j<int(n[i].size());j++){cout<<n[i][j]<<" ";}cout<<endl;}cout<<endl;} void yes(bool a){cout<<(a?"yes":"no")<<endl;} void YES(bool a){cout<<(a?"YES":"NO")<<endl;} void Yes(bool a){cout<<(a?"Yes":"No")<<endl;} void possible(bool a){ cout<<(a?"possible":"impossible")<<endl; } void Possible(bool a){ cout<<(a?"Possible":"Impossible")<<endl; } void POSSIBLE(bool a){ cout<<(a?"POSSIBLE":"IMPOSSIBLE")<<endl; } template<class T>auto min(const T& a){ return *min_element(all(a)); } template<class T>auto max(const T& a){ return *max_element(all(a)); } template<class T,class F>void print(pair<T,F> a){cout<<a.fi<<" "<<a.se<<endl;} template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0;} template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0;} template<class T> void ifmin(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}} template<class T> void ifmax(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}} template<typename T,typename ...Args>auto make_vector(T x,int arg,Args ...args){if constexpr(sizeof...(args)==0)return vector<T>(arg,x);else return vector(arg,make_vector<T>(x,args...));} ll fastgcd(ll u,ll v){ll shl=0;while(u&&v&&u!=v){bool eu=!(u&1);bool ev=!(v&1);if(eu&&ev){++shl;u>>=1;v>>=1;}else if(eu&&!ev){u>>=1;}else if(!eu&&ev){v>>=1;}else if(u>=v){u=(u-v)>>1;}else{ll tmp=u;u=(v-u)>>1;v=tmp;}}return !u?v<<shl:u<<shl;} ll modPow(ll a, ll n, ll mod) { if(mod==1) return 0;ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; } vector<ll> divisor(ll x){ vector<ll> ans; for(ll i = 1; i * i <= x; i++){ if(x % i == 0) {ans.push_back(i); if(i*i!=x){ ans.push_back(x / ans[i]);}}}sor(ans); return ans; } ll pop(ll a){ll res=0;while(a){res+=a%2;a/=2;}return res;} template<class T> struct Sum{ vector<T> data; Sum(const vector<T>& v):data(v.size()+1){ for(ll i=0;i<v.size();i++) data[i+1]=data[i]+v[i]; } T get(ll l,ll r) const { return data[r]-data[l]; } }; template<class T> struct Sum2{ vector<vector<T>> data; Sum2(const vector<vector<T>> &v):data(v.size()+1,vector<T>(v[0].size()+1)){ for(int i=0;i<v.size();i++) for(int j=0;j<v[i].size();j++) data[i+1][j+1]=data[i][j+1]+v[i][j]; for(int i=0;i<v.size();i++) for(int j=0;j<v[i].size();j++) data[i+1][j+1]+=data[i+1][j]; } T get(ll x1,ll y1,ll x2,ll y2) const { return data[x2][y2]+data[x1][y1]-data[x1][y2]-data[x2][y1]; } }; void cincout(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); cout<< fixed << setprecision(10); } template<class T> vector<T> NTT(vector<T> a,vector<T> b){ ll nmod=T::mod(); int n=a.size(); int m=b.size(); vector<int> x1(n); vector<int> y1(m); for(int i=0;i<n;i++){ ll tmp1,tmp2,tmp3; tmp1=a[i].val(); x1[i]=tmp1; } for(int i=0;i<m;i++){ ll tmp1,tmp2,tmp3; tmp1=b[i].val(); y1[i]=tmp1; } auto z1=convolution<167772161>(x1,y1); auto z2=convolution<469762049>(x1,y1); auto z3=convolution<1224736769>(x1,y1); vector<T> res(n+m-1); ll m1=167772161; ll m2=469762049; ll m3=1224736769; ll m1m2=104391568; ll m1m2m3=721017874; ll mm12=m1*m2%nmod; for(int i=0;i<n+m-1;i++){ int v1=(z2[i]-z1[i])*m1m2%m2; if(v1<0) v1+=m2; int v2=(z3[i]-(z1[i]+v1*m1)%m3)*m1m2m3%m3; if(v2<0) v2+=m3; res[i]=(z1[i]+v1*m1+v2*mm12); } return res; } enum Mode { FAST = 1, NAIVE = -1, }; template <class T, Mode mode = FAST> struct FormalPowerSeries : std::vector<T> { using std::vector<T>::vector; using std::vector<T>::size; using std::vector<T>::resize; using F = FormalPowerSeries; F &operator+=(const F &g){ for(int i=0;i<int(min((*this).size(),g.size()));i++){ (*this)[i]+=g[i]; } return *this; } F &operator+=(const T &t){ assert(int((*this).size())); (*this)[0]+=t; return *this; } F &operator-=(const F &g) { for(int i=0;i<int(min((*this).size(),g.size()));i++){ (*this)[i]-=g[i]; } return *this; } F &operator-=(const T &t){ assert(int((*this).size())); (*this)[0]-=t; return *this; } F &operator*=(const T &g) { for(int i=0;i<int((*this).size());i++){ (*this)[i]*=g; } return *this; } F &operator/=(const T &g) { T div=g.inv(); for(int i=0;i<int((*this).size());i++){ (*this)[i]*=div; } return *this; } F &operator<<=(const int d) { int n=(*this).size(); (*this).insert((*this).begin(),d,0); (*this).resize(n); return *this; } F &operator>>=(const int d) { int n=(*this).size(); (*this).erase((*this).begin(),(*this).begin()+min(n, d)); (*this).resize(n); return *this; } F &operator=(const std::vector<T> &v) { int n = (*this).size(); for(int i = 0; i < n; ++i) (*this)[i] = v[i]; return *this; } F operator-() const { F ret = *this; return ret * -1; } F &operator*=(const F &g) { if(mode==FAST) { int n=(*this).size(); auto tmp=atcoder::convolution(*this,g); int k=tmp.size(); (*this).resize(k); for(int i=0;i<k;++i){ (*this)[i]=tmp[i]; } return *this; } else{ int n=(*this).size(); auto tmp=NTT(*this,g); int k=tmp.size(); (*this).resize(k); for(int i=0;i<k;++i){ (*this)[i]=tmp[i]; } return *this; } } F &operator/=(const F &g) { if(mode == FAST){ int n = (*this).size(); (*this) = atcoder::convolution(*this, g.inv()); return *this; } else{ int n = (*this).size(); (*this) = NTT(*this, g.inv()); return *this; } } F &operator%=(const F &g) { return *this-=*this/g*g; } F operator*(const T &g) const { return F(*this)*=g;} F operator-(const T &g) const { return F(*this)-=g;} F operator*(const F &g) const { return F(*this)*=g;} F operator-(const F &g) const { return F(*this)-=g;} F operator+(const F &g) const { return F(*this)+=g;} F operator/(const F &g) const { return F(*this)/=g;} F operator%(const F &g) const { return F(*this)%=g;} F operator<<(const int d) const { return F(*this)<<=d;} F operator>>(const int d) const { return F(*this)>>=d;} void onemul(const int d,const T c){ int n=(*this).size(); for(int i=n-d-1;i>=0;i--){ (*this)[i+d]+=(*this)[i]*c; } } void onediv(const int d,const T c){ int n=(*this).size(); for(int i=0;i<n-d;i++){ (*this)[i+d]-=(*this)[i]*c; } } T eval(const T &t) const { int n = (*this).size(); T res = 0, tmp = 1; for(int i = 0; i < n; ++i){ res += (*this)[i] * tmp, tmp *= t; } return res; } F inv(int deg = -1) const { int n = (*this).size(); if(mode==FAST){ if(deg == -1) deg = n; assert(deg > 0); F res{(*this)[0].inv()}; while(int(res.size()) < deg) { int m = res.size(); F f((*this).begin(), (*this).begin() + std::min(n, m * 2)), r(res); f.resize(m * 2), atcoder::internal::butterfly(f); r.resize(m * 2), atcoder::internal::butterfly(r); for(int i = 0; i < m * 2; ++i) f[i] *= r[i]; atcoder::internal::butterfly_inv(f); f.erase(f.begin(), f.begin() + m); f.resize(m * 2), atcoder::internal::butterfly(f); for(int i = 0; i < m * 2; ++i) f[i] *= r[i]; atcoder::internal::butterfly_inv(f); T iz = T(m * 2).inv(); iz *= -iz; for(int i = 0; i < m; ++i) f[i] *= iz; res.insert(res.end(), f.begin(), f.begin() + m); } res.resize(deg); return res; } else{ assert(n!=0&&(*this)[0]!=0); if(deg==-1) deg=n; assert(deg>0); F res{(*this)[0].inv()}; while(res.size()<deg){ int m=res.size(); F f(begin(*this),begin(*this)+min(n,2*m)); F r(res); f.resize(2*m); r.resize(2*m); vector<T> s=NTT(f,r); s.resize(2*m); for(int i=0;i<2*m;i++){ s[i]=-s[i]; } s[0]+=2; vector<T> g=NTT(s,r); g.resize(2*m); swap(res,g); } res.resize(n); return res; } } F &diff_inplace() { int n = (*this).size(); for(int i = 1; i < n; ++i) (*this)[i - 1] = (*this)[i] * i; (*this)[n - 1] = 0; return *this; } F diff() const { F(*this).diff_inplace();} F &integral_inplace() { int n = (*this).size(), mod = T::mod(); std::vector<T> inv(n); { inv[1] = 1; for(int i = 2; i < n; ++i) inv[i] = T(mod) - inv[mod % i] * (mod / i); } for(int i = n - 2; i >= 0; --i) (*this)[i + 1] = (*this)[i] * inv[i + 1]; (*this)[0] = 0; return *this; } F integral() const { return F(*this).integral_inplace(); } F &log_inplace() { int n = (*this).size(); assert(n and (*this)[0] == 1); F f_inv = (*this).inv(); (*this).diff_inplace(); (*this) *= f_inv; (*this).integral_inplace(); return *this; } F log() const { return F(*this).log_inplace(); } F &deriv_inplace() { int n = (*this).size(); assert(n); for(int i = 2; i < n; ++i) (*this)[i] *= i; (*this).erase((*this).begin()); (*this).push_back(0); return *this; } F deriv() const { return F(*this).deriv_inplace(); } F &exp_inplace() { int n = (*this).size(); assert(n and (*this)[0] == 0); F g{1}; (*this)[0] = 1; F h_drv((*this).deriv()); for(int m = 1; m < n; m *= 2) { F f((*this).begin(), (*this).begin() + m); f.resize(2 * m), atcoder::internal::butterfly(f); auto mult_f = [&](F &p) { p.resize(2 * m); atcoder::internal::butterfly(p); for(int i = 0; i < 2 * m; ++i) p[i] *= f[i]; atcoder::internal::butterfly_inv(p); p /= 2 * m; }; if(m > 1) { F g_(g); g_.resize(2 * m), atcoder::internal::butterfly(g_); for(int i = 0; i < 2 * m; ++i) g_[i] *= g_[i] * f[i]; atcoder::internal::butterfly_inv(g_); T iz = T(-2 * m).inv(); g_ *= iz; g.insert(g.end(), g_.begin() + m / 2, g_.begin() + m); } F t((*this).begin(), (*this).begin() + m); t.deriv_inplace(); { F r{h_drv.begin(), h_drv.begin() + m - 1}; mult_f(r); for(int i = 0; i < m; ++i) t[i] -= r[i] + r[m + i]; } t.insert(t.begin(), t.back()); t.pop_back(); t *= g; F v((*this).begin() + m, (*this).begin() + std::min(n, 2 * m)); v.resize(m); t.insert(t.begin(), m - 1, 0); t.push_back(0); t.integral_inplace(); for(int i = 0; i < m; ++i) v[i] -= t[m + i]; mult_f(v); for(int i = 0; i < std::min(n - m, m); ++i) (*this)[m + i] = v[i]; } return *this; } F exp() const { return F(*this).exp_inplace(); } F &pow_inplace(long long k) { int n = (*this).size(), l = 0; assert(k >= 0); if(!k){ for(int i = 0; i < n; ++i) (*this)[i] = !i; return *this; } while(l < n and (*this)[l] == 0) ++l; if(l > (n - 1) / k or l == n) return *this = F(n); T c = (*this)[l]; (*this).erase((*this).begin(), (*this).begin() + l); (*this) /= c; (*this).log_inplace(); (*this).resize(n - l * k); (*this) *= k; (*this).exp_inplace(); (*this) *= c.pow(k); (*this).insert((*this).begin(), l * k, 0); return *this; } F pow(const long long k) const { return F(*this).pow_inplace(); } void manymul(vector<pair<int, T>> g) { int n = (*this).size(); auto [d, c] = g.front(); if (d == 0) g.erase(g.begin()); else c = 0; drep(i, n) { (*this)[i] *= c; for (auto &[j, b] : g) { if (j > i) break; (*this)[i] += (*this)[i-j] * b; } } } void manydiv(vector<pair<int, T>> g) { int n = (*this).size(); auto [d, c] = g.front(); assert(d == 0 && c != T(0)); T ic = c.inv(); g.erase(g.begin()); rep(i, 0,n) { for (auto &[j, b] : g) { if (j > i) break; (*this)[i] -= (*this)[i-j] * b; } (*this)[i] *= ic; } } }; template<class T> void GaussJordan(vector<vector<T>> &A,bool is_extended = false){ ll m=A.size(),n=A[0].size(); ll rank=0; for(int i=0;i<n;i++){ if(is_extended&&i==n-1) break; ll p=-1; for(int j=rank;j<m;j++){ if(A[j][i]!=T(0)){ p=j; break; } } if(p==-1) continue; swap(A[p],A[rank]); auto k=A[rank][i]; for(int i2=0;i2<n;i2++){ A[rank][i2]/=k; } for(int j=0;j<m;j++){ if(j!=rank&&A[j][i]!=T(0)){ auto fac=A[j][i]; for(int i2=0;i2<n;i2++){ A[j][i2]-=A[rank][i2]*fac; } } } rank++; } } template<class T> void linear_equation(vector<vector<T>> a, vector<T> b, vector<T> &res) { ll m=a.size(),n=a[0].size(); vector<vector<T>> M(m,vector<T>(n+1)); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ M[i][j]=a[i][j]; } M[i][n]=b[i]; } GaussJordan(M,true); res.assign(n,0); for(int i=0;i<n;i++) res[i]=M[i][n]; } template<class F> pair<F,F> Characteristic_equation(const F &a) { using T=typename F::value_type; ll n=a.size(); ll p=n/2; ll u=p+(p+1); vector<vector<T>> f(u,vector<T>(u)); f[0][0]=1; for(int i=1;i<=p;i++){ f[i][i-1]=-1; } for(int i=p;i<u;i++){ ll t=0; for(int j=1+i-p;j<u;j++){ f[j][i]=a[t]; t++; } } vector<T> b(u); b[0]=1; vector<T> res(u); linear_equation(f,b,res); F X(p),Y(p+1); for(int i=0;i<p;i++) X[i]=res[i]; for(int j=p;j<res.size();j++) Y[j-p]=res[j]; return {X,Y}; } template <class T, Mode mode> T getK(FormalPowerSeries<T, mode> p, FormalPowerSeries<T, mode> q,ll k){ if(k<0) return T(0); ll d=q.size(); while(k){ auto qn=q; for(int i=1;i<d;i+=2) qn[i]*=-1; p.resize(2*d); q.resize(2*d); p*=qn; q*=qn; for(int i=0;i<d-1;i++){ p[i]=p[(i<<1)|(k&1)]; } for(int i=0;i<d;i++){ q[i]=q[(i<<1)]; } p.resize(d-1); q.resize(d); k/=2; } return p[0]; } /*using mint = modint1000000007; using fps = FormalPowerSeries<atcoder::modint1000000007,NAIVE>;*/ using mint = modint998244353; using fps = FormalPowerSeries<atcoder::modint998244353,FAST>; int main() { cincout(); ll n; cin>>n; fps f(n+1); ll u=0; ll k=1; for(;u*(3*u-1)/2<=n;){ if(k%4<2) f[u*(3*u-1)/2]=1; else f[u*(3*u-1)/2]=-1; k++; if(u<=0) u=abs(u)+1; else u*=-1; } f=f.inv(); for(int i=0;i<=n;i++) cout<<f[i].val()<<" "; }