Submit Info #4579

Problem Lang User Status Time Memory
Montmort Number cpp hotman AC 90 ms 25.39 MiB

ケース詳細
Name Status Time Memory
example_00 AC 0 ms 0.68 MiB
example_01 AC 1 ms 0.67 MiB
max_00 AC 85 ms 25.00 MiB
max_01 AC 90 ms 25.17 MiB
max_02 AC 88 ms 25.39 MiB
random_00 AC 35 ms 10.05 MiB
random_01 AC 43 ms 11.74 MiB
random_02 AC 52 ms 14.92 MiB
random_03 AC 38 ms 11.30 MiB
random_04 AC 71 ms 20.42 MiB

#pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include<bits/stdc++.h> using namespace::std; __attribute__((constructor))void init(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);} #include <xmmintrin.h> #include <immintrin.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/priority_queue.hpp> #include<ext/pb_ds/tag_and_trait.hpp> // #include <boost/multiprecision/cpp_dec_float.hpp> // #include <boost/multiprecision/cpp_int.hpp> // namespace mp = boost::multiprecision; // typedef mp::number<mp::cpp_dec_float<0>> cdouble; // typedef mp::cpp_int cint; template<typename T>using pbds=__gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>; template<typename T>using pbds_map=__gnu_pbds::tree<T,T,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>; template<typename T,typename E>using hash_map=__gnu_pbds::gp_hash_table<T,E>; template<typename T>using hash_set=__gnu_pbds::gp_hash_table<T,__gnu_pbds::null_type>; template<typename T>using pqueue =__gnu_pbds::priority_queue<T, greater<T>,__gnu_pbds::rc_binomial_heap_tag>; typedef long long lint; #define INF (1LL<<60) #define IINF (1<<30) #define EPS (1e-10) //#define MOD 1000000007LL #define MOD 998244353LL typedef vector<lint> vec; typedef vector<vector<lint>> mat; typedef vector<vector<vector<lint>>> mat3; typedef vector<string> svec; typedef vector<vector<string>> smat; template<typename T>inline void numout(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<<i<INF/2?i:"INF";f=1;}cout<<endl;} template<typename T>inline void numout2(T t){for(auto i:t)numout(i);} template<typename T>inline void output(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<<i;f=1;}cout<<endl;} template<typename T>inline void output2(T t){for(auto i:t)output(i);} template<typename T>inline void _output(T t){bool f=0;for(lint i=0;i<t.size();i++){cout<<f?"":" "<<t[i];f=1;}cout<<endl;} template<typename T>inline void _output2(T t){for(lint i=0;i<t.size();i++)output(t[i]);} #define rep(i,n) for(lint i=0;i<lint(n);++i) #define repi(i,a,b) for(lint i=lint(a);i<(lint)(b);++i) #define rrep(i,n) for(lint i=lint(n)-1;i>=0;--i) #define rrepi(i,a,b) for(lint i=lint(b)-1;i>=lint(a);--i) #define irep(i) for(lint i=0;;++i) #define all(n) begin(n),end(n) #define dist(a,b,c,d) sqrt(pow(a-c,2)+pow(b-d,2)) inline lint gcd(lint A,lint B){return B?gcd(B,A%B):A;} inline lint lcm(lint A,lint B){return A/gcd(A,B)*B;} // inline cint cgcd(cint A,cint B){return B?cgcd(B,A%B):A;} // inline cint clcm(cint A,cint B){return A/cgcd(A,B)*B;} inline bool chmin(auto& s,const auto& t){bool res=s>t;s=min(s,t);return res;} inline bool chmax(auto& s,const auto& t){bool res=s<t;s=max(s,t);return res;} const vector<lint> dx={1,0,-1,0,1,1,-1,-1}; const vector<lint> dy={0,1,0,-1,1,-1,1,-1}; #define SUM(v) accumulate(all(v),0LL) auto call=[](auto f,auto... args){return f(f,args...);}; template<typename T,typename P> struct FPS_BASE:vector<T>{ using vector<T>::vector; inline P operator +(T x)noexcept{return P(*static_cast<P*>(this))+=x;} inline P operator -(T x)noexcept{return P(*static_cast<P*>(this))-=x;} inline P operator *(T x)noexcept{return P(*static_cast<P*>(this))*=x;} inline P operator /(T x)noexcept{return P(*static_cast<P*>(this))/=x;} inline P operator <<(int x)noexcept{return P(*static_cast<P*>(this))<<=x;} inline P operator >>(int x)noexcept{return P(*static_cast<P*>(this))>>=x;} inline P operator +(const P& x)noexcept{return P(*static_cast<P*>(this))+=x;} inline P operator -(const P& x)noexcept{return P(*static_cast<P*>(this))-=x;} inline P operator -()noexcept{return P(1,T(0))-=P(*static_cast<P*>(this));} inline P operator *(const P& x)noexcept{return P(*static_cast<P*>(this))*=x;} inline P operator /(const P& x)noexcept{return P(*static_cast<P*>(this))/=x;} inline P operator %(const P& x)noexcept{return P(*static_cast<P*>(this))%=x;} inline P &operator +=(T x){ if(this->size()==0)this->resize(1,T(0)); (*static_cast<P*>(this))[0]+=x; return (*static_cast<P*>(this)); } inline P &operator -=(T x){ if(this->size()==0)this->resize(1,T(0)); (*static_cast<P*>(this))[0]-=x; return (*static_cast<P*>(this)); } inline P &operator *=(T x){ for(int i=0;i<(int)this->size();++i){ (*static_cast<P*>(this))[i]*=x; } return (*static_cast<P*>(this)); } inline P &operator /=(T x){ return (*static_cast<P*>(this))*=(T(1)/x); } inline P &operator <<=(int x){ P ret(x,T(0)); ret.insert(ret.end(),begin(*static_cast<P*>(this)),end(*static_cast<P*>(this))); return (*static_cast<P*>(this))=ret; } inline P &operator >>=(int x){ P ret; ret.insert(ret.end(),begin(*static_cast<P*>(this))+x,end(*static_cast<P*>(this))); return (*static_cast<P*>(this))=ret; } inline P &operator +=(const P& x){ if(this->size()<x.size())this->resize(x.size(),T(0)); for(int i=0;i<(int)x.size();++i){ (*this)[i]+=x[i]; } return (*static_cast<P*>(this)); } inline P &operator -=(const P& x){ if(this->size()<x.size())this->resize(x.size(),T(0)); for(int i=0;i<(int)x.size();++i){ (*static_cast<P*>(this))[i]-=x[i]; } return (*static_cast<P*>(this)); } inline P &operator *=(const P& x){ return (*static_cast<P*>(this))=mul((*static_cast<P*>(this)),x); } inline P &operator /=(P x){ if(this->size()<x.size()) { this->clear(); return (*static_cast<P*>(this)); } const int n=this->size()-x.size()+1; return (*static_cast<P*>(this)) = (rev().pre(n)*x.rev().inv(n)).pre(n).rev(n); } inline P &operator %=(const P& x){ return ((*static_cast<P*>(this))-=*static_cast<P*>(this)/x*x); } inline P& shrink(){while((*static_cast<P*>(this)).back()==0)(*static_cast<P*>(this)).pop_back();return (*static_cast<P*>(this));} inline P pre(int sz)const{ return P(begin(*this),begin(*this)+min((int)this->size(),sz)); } inline P rev(int deg=-1){ P ret(*static_cast<P*>(this)); if(deg!=-1)ret.resize(deg,T(0)); reverse(begin(ret),end(ret)); return ret; } P inv(int deg=-1){ assert((*static_cast<P*>(this))[0]!=T(0)); const int n=deg==-1?this->size():deg; P ret({T(1)/(*this)[0]}); for(int i=1;i<n;i<<=1){ ret=(ret*T(2)-ret*ret*pre(i<<1)).pre(i<<1); } return ret.pre(n); } inline P dot(const P& x){ P ret(*static_cast<P*>(this)); for(int i=0;i<int(min(this->size(),x.size()));++i){ ret[i]*=x[i]; } return ret; } P diff(){ P ret(*static_cast<P*>(this)); for(int i=0;i<(int)ret.size();i++){ ret[i]*=i; } return ret>>1; } P integral(){ P ret(*static_cast<P*>(this)); for(int i=0;i<(int)ret.size();i++){ ret[i]/=i+1; } return ret<<1; } P log(int deg=-1){ assert((*this)[0]==T(1)); const int n=deg==-1?this->size():deg; return (diff()*inv(n)).pre(n-1).integral(); } P exp(int deg=-1){ assert((*this)[0]==T(0)); const int n=deg==-1?this->size():deg; P ret({T(1)}); for(int i=1;i<n;i<<=1){ ret=ret*(pre(i<<1)+1-ret.log(i<<1)).pre(i<<1); } return ret.pre(n); } P sqrt(int deg=-1){ const int n=deg==-1?this->size():deg; if((*this)[0]==T(0)) { for(int i=1;i<(int)this->size();i++) { if((*this)[i]!=T(0)) { if(i&1)return{}; if(n-i/2<=0)break; auto ret=(*this>>i).sqrt(n-i/2)<<(i/2); if((int)ret.size()<n)ret.resize(n,T(0)); return ret; } } return P(n,0); } P ret({T(1)}); for(int i=1;i<n;i<<=1){ ret=(ret+pre(i<<1)*ret.inv(i<<1)).pre(i<<1)/T(2); } return ret.pre(n); } T eval(T x){ T res=0; for(int i=(int)this->size()-1;i>=0;--i){ res*=x; res+=(*this)[i]; } return res; } vector<T> multipoint_eval(const vector<T>&x){ const int n=x.size(); P* v=new P[2*n-1]; for(int i=0;i<n;i++)v[i+n-1]={T()-x[i],T(1)}; for(int i=n-2;i>=0;i--){v[i]=v[i*2+1]*v[i*2+2];} v[0]=P(*static_cast<P*>(this))%v[0];v[0].shrink(); for(int i=1;i<n*2-1;i++){ v[i]=v[(i-1)/2]%v[i]; v[i].shrink(); } vector<T>res(n); for(int i=0;i<n;i++)res[i]=v[i+n-1][0]; return res; } virtual P mul(P s,P t)=0; }; template<typename Mint> struct fps9:FPS_BASE<Mint,fps9<Mint>>{ using FPS_BASE<Mint,fps9<Mint>>::FPS_BASE; using P=fps9<Mint>; P mul(P s,P t)override{ if((int)min(s.size(),t.size())<=100){ if(s.size()>t.size())swap(s,t); P res(s.size()+t.size()-1,Mint()); for(int i=0;i<(int)s.size();i++){ if(s[i]!=Mint())res+=(t<<i)*s[i]; } return res; } const int n=s.size()+t.size()-1; int h=1; while((1<<h)<n)h++; s.resize((1<<h),Mint(0)); t.resize((1<<h),Mint(0)); return ntt(ntt(s,h,0).dot(ntt(t,h,0)),h,1).pre(n).shrink(); } P ntt(P v,const int& h,const bool& inv){ const int n=v.size(),mask=n-1; assert(Mint::get_mod()>=3&&Mint::get_mod()%2==1); P tmp(n); Mint* table=new Mint[n];table[0]=1; Mint theta=Mint(Mint::root()).pow((Mint::get_mod()-1)>>h); if(inv)theta=theta.inv(); for(int i=1;i<n;++i)table[i]=table[i-1]*theta; for(int j=n>>1,t=h-1;j>=1;j>>=1,--t){ for(int k=0;k<n;++k){ const int s=k&(j-1); const int i=k>>t; tmp[k]=v[((i<<(t+1))|s)&mask]+table[i*j]*v[((i<<(t+1))|j|s)&mask]; } v.swap(tmp); } if(inv)v/=n; return v; } }; class mint { using u64 = std::uint_fast64_t; public: u64 a; constexpr mint(const long long x = 0)noexcept:a(x>=0?x%get_mod():get_mod()-(-x)%get_mod()){} constexpr u64 &value()noexcept{return a;} constexpr const u64 &value() const noexcept {return a;} constexpr mint operator+(const mint rhs)const noexcept{return mint(*this) += rhs;} constexpr mint operator-(const mint rhs)const noexcept{return mint(*this)-=rhs;} constexpr mint operator*(const mint rhs) const noexcept {return mint(*this) *= rhs;} constexpr mint operator/(const mint rhs) const noexcept {return mint(*this) /= rhs;} constexpr mint &operator+=(const mint rhs) noexcept { a += rhs.a; if (a >= get_mod())a -= get_mod(); return *this; } constexpr mint &operator-=(const mint rhs) noexcept { if (a<rhs.a)a += get_mod(); a -= rhs.a; return *this; } constexpr mint &operator*=(const mint rhs) noexcept { a = a * rhs.a % get_mod(); return *this; } constexpr mint operator++(int n) noexcept { a += 1; if (a >= get_mod())a -= get_mod(); return *this; } constexpr mint operator--(int n) noexcept { if (a<1)a += get_mod(); a -= 1; return *this; } constexpr mint &operator/=(mint rhs) noexcept { return *this*= rhs.inv(); } constexpr bool operator==(mint x) noexcept { return a==x.a; } constexpr bool operator!=(mint x) noexcept { return a!=x.a; } constexpr static int root(){ mint root = 2; while(root.pow((get_mod()-1)>>1).a==1)root++; return root.a; } constexpr mint pow(long long n){ long long x=a; mint ret = 1; while(n>0) { if(n&1)(ret*=x); (x*=x)%=get_mod(); n>>=1; } return ret; } constexpr mint inv()const{ int x=a,y=get_mod(),u=1,v=0,t=0; while(y > 0) { t=x/y; x-=t*y;x^=y;y^=x;x^=y; u-=t*v;u^=v;v^=u;u^=v; } return mint(u); } mint comb(lint b){ using lint=long long; static bool init=1; static lint fac[3000001],ifac[3000001]; if(init){ init=0; fac[0]=1; ifac[0]=1; auto mod_pow=[&](lint x,lint n){ lint ans = 1; while(n != 0){ if(n&1)ans=ans*x%get_mod(); x=x*x%get_mod(); n=n>>1; } return ans; }; for(int i=0;i<3000000;i++){ fac[i+1]=fac[i]*(i+1)%get_mod(); ifac[i+1]=ifac[i]*mod_pow(i+1, get_mod()-2)%get_mod(); } } if(a==0&&b==0)return 1; if((lint)a<b||a<0)return 0; lint tmp=ifac[a-b]*ifac[b]%get_mod(); return tmp*fac[a]%get_mod(); } mint fact(){ using lint=long long; static bool init=1; static lint fac[3000001]; if(init){ init=0; fac[0]=1; for(int i=0;i<3000000;i++){ fac[i+1]=fac[i]*(i+1)%get_mod(); } } return fac[a]; } friend ostream& operator<<(ostream& lhs, const mint& rhs) noexcept { lhs << rhs.a; return lhs; } friend istream& operator>>(istream& lhs,mint& rhs) noexcept { lhs >> rhs.a; return lhs; } constexpr static u64 get_mod(){return MOD;} }; double timer(auto f){ auto s=chrono::system_clock::now(); f(); auto e=chrono::system_clock::now(); return std::chrono::duration_cast<std::chrono::milliseconds>(e-s).count(); } int main(){ lint n,m; cin>>n>>m; vec b(n); b[0]=0; b[1]=1; b[2]=2; repi(i,3,n)b[i]=i*(b[i-1]+b[i-2])%m; output(b); }