Submit Info #477

Problem Lang User Status Time Memory
Partition Function cpp (anonymous) AC 496 ms 21.26 MiB

ケース詳細
Name Status Time Memory
0_00 AC 1 ms 0.71 MiB
100000_00 AC 113 ms 5.59 MiB
10000_00 AC 17 ms 1.30 MiB
1000_00 AC 2 ms 0.68 MiB
100_00 AC 1 ms 0.67 MiB
1_00 AC 2 ms 0.67 MiB
200000_00 AC 237 ms 10.40 MiB
300000_00 AC 480 ms 19.80 MiB
400000_00 AC 491 ms 20.21 MiB
500000_00 AC 496 ms 21.26 MiB
example_00 AC 2 ms 0.68 MiB

#include<bits/stdc++.h> using namespace std; #define int long long #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define all(v) (v).begin(),(v).end() #define fi first #define se second typedef vector<int>vint; typedef pair<int,int>pint; typedef vector<pint>vpint; template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;} template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;} /* GF(p) inverse:O(log p) based on Fermat's little theorem (a^(p-1)=1 mod p) */ template<int32_t mod> struct ModInt{ int32_t a; inline int32_t normalize(int64_t x){ x%=mod; if(x<0)x+=mod; return x; } ModInt(const int64_t a=0):a(normalize(a)){} ModInt& operator+=(const ModInt &x){ a+=x.a; if(a>=mod)a-=mod; return *this; } ModInt& operator-=(const ModInt &x){ a-=x.a; if(a<0)a+=mod; return *this; } ModInt& operator*=(const ModInt &x){ a=(int64_t)a*x.a%mod; return *this; } ModInt& operator/=(const ModInt &x){ *this*=x.inv(); return *this; } ModInt operator+(const ModInt x){return ModInt(*this)+=x;} ModInt operator-(const ModInt x){return ModInt(*this)-=x;} ModInt operator*(const ModInt x){return ModInt(*this)*=x;} ModInt operator/(const ModInt x){return ModInt(*this)/=x;} bool operator==(const ModInt x){return a==x.a;} bool operator!=(const ModInt x){return a!=x.a;} ModInt operator-(){return ModInt(0)-ModInt(*this);} ModInt pow(int64_t ex)const{ int64_t x=a; int64_t res=1; while(ex){ if(ex&1)res=res*x%mod; x=x*x%mod; ex>>=1; } return ModInt(res); } ModInt inv()const{return pow(mod-2);} }; template<int32_t mod> istream& operator>>(istream& in,ModInt<mod>& a){ return (in>>a.a); } template<int32_t mod> ostream& operator<<(ostream& out,const ModInt<mod>& a){ return (out<<a.a); } using mint=ModInt<998244353>; /* based on Cooley-Tukey O(nlogn) */ template<class Mint,int32_t root> struct NumberTheoreticTransform{ static void ntt(vector<Mint>&f){ int n=f.size(); int s=__lg(n); for(int i=0,j=1;j<n-1;j++){ for(int k=n>>1;k>(i^=k);k>>=1); if(i>j)swap(f[i],f[j]); } for(int m=1;m<=s;m++){ Mint wr=Mint(root).pow(Mint(-1).a>>m); for(int i=0;i<n;i+=1<<m){ Mint w=1; for(int j=0;j<1<<m-1;j++){ Mint f0=f[i+j],f1=w*f[i+j+(1<<m-1)]; f[i+j]=f0+f1; f[i+j+(1<<m-1)]=f0-f1; w*=wr; } } } } static void intt(vector<Mint>&f){ reverse(f.begin()+1,f.end()); ntt(f); Mint in=Mint(f.size()).inv(); for(int i=0;i<f.size();i++)f[i]*=in; } static vector<Mint>convolute(const vector<Mint>&A,const vector<Mint>&B){ int n=1<<__lg(A.size()+B.size()-2)+1; vector<Mint>a=A,b=B; a.resize(n);b.resize(n); ntt(a); ntt(b); for(int i=0;i<n;i++)a[i]*=b[i]; intt(a); a.resize(A.size()+B.size()-1); return a; } }; using NTT=NumberTheoreticTransform<mint,3>; /* each operation:O(n) or O(nlogn) */ template<class Mint,class Convoluter> struct Poly{ vector<Mint>v; inline void normalize(){ while(v.size()&&v.back()==0)v.pop_back(); } template<class...Args> Poly(Args...args):v(args...){} Poly(const initializer_list<Mint>&in):v(in.begin(),in.end()){} int size()const{return v.size();} inline Mint coef(const int i)const{return (i<v.size())?v[i]:Mint(0);} Poly operator+(const Poly &x){ int n=max(size(),x.size()); vector<Mint>res(n); for(int i=0;i<n;i++)res[i]=coef(i)+x.coef(i); return res; } Poly operator-(const Poly &x){ int n=max(size(),x.size()); vector<Mint>res(n); for(int i=0;i<n;i++)res[i]=coef(i)-x.coef(i); return res; } Poly operator*(const Poly& x){ return Convoluter::convolute(v,x.v); } Poly operator*(const Mint& x){ int n=size(); vector<Mint>res(n); for(int i=0;i<n;i++)res[i]=v[i]*x; return res; } Poly operator/(const Mint& x){ return (*this)*x.inv(); } Poly& operator+=(const Poly& x){return *this=(*this)+x;} Poly& operator-=(const Poly& x){return *this=(*this)-x;} Poly& operator*=(const Poly& x){return *this=(*this)*x;} Poly& operator*=(const Mint& x){return *this=(*this)*x;} Poly& operator/=(const Mint& x){return *this=(*this)/x;} Poly pre(int n){ return {v.begin(),v.begin()+min(n,size())}; } Poly rev(){ vector<Mint>res=v; res.normalize(); reverse(res.begin(),res.end()); return res; } Poly diff(int n){ vector<Mint>res(n); for(int i=1;i<size()&&i<=n;i++)res[i-1]=coef(i)*i; return res; } Poly inte(int n){ vector<Mint>res(n); for(int i=0;i<size()&&i+1<n;i++)res[i+1]=coef(i)/(i+1); return res; } Poly inv(int m){ Poly res{1}; for(int i=1;i<m;i*=2){ res=(res*Mint(2)-res*res*pre(2*i)).pre(2*i); } return res.pre(m); } Poly exp(int n){ Poly f{1}; for(int i=1;i<n;i*=2){ f=(f*(pre(2*i)-f.log(2*i))+f).pre(2*i); } return f.pre(n); } Poly log(int n){ return (diff(n-1)*inv(n-1)).inte(n); } Poly pow(int n,Mint m){ Poly res=log(n); res*=m; return res.exp(n); } Mint& operator[](const int i){return v[i];} }; using poly=Poly<mint,NTT>; template<class Mint,class Convoluter> ostream& operator<<(ostream& ost,Poly<Mint,Convoluter>a){ for(int i=0;i<a.size();i++){ if(i)cout<<" "; cout<<a.v[i]; } return ost; } poly partitionGF(int n){ poly A(n); A[0]=1; for(int k=1;k<n;k++){ if((long long)k*(3*k+1)/2<=n)A[k*(3*k+1)/2]+=k%2?-1:1; if((long long)k*(3*k-1)/2<=n)A[k*(3*k-1)/2]+=k%2?-1:1; } return A.inv(n); } signed main(){ int N;cin>>N; auto P=partitionGF(N+1); for(int i=0;i<=N;i++){ if(i)printf(" "); printf("%d",P[i].a); } puts(""); return 0; }