Submit Info #59799

Problem Lang User Status Time Memory
Multipoint Evaluation cpp turtle0123 AC 2811 ms 188.77 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.45 MiB
example_01 AC 1 ms 0.42 MiB
max_random_00 AC 2805 ms 188.70 MiB
max_random_01 AC 2811 ms 188.77 MiB
random_00 AC 669 ms 56.35 MiB
random_01 AC 501 ms 49.40 MiB
random_02 AC 2321 ms 184.62 MiB
zero_00 AC 1 ms 0.41 MiB

#include<bits/stdc++.h> typedef uint64_t u64; typedef int64_t i64; using namespace std; template<u64 mod> struct modint{ u64 val; modint(i64 val_=0):val((val_%i64(mod)+i64(mod))%i64(mod)){} modint operator-(){ val=(val==0)?val:mod-val; return (*this); } modint operator+(modint rhs){ return modint(*this)+=rhs; } modint operator-(modint rhs){ return modint(*this)-=rhs; } modint operator*(modint rhs){ return modint(*this)*=rhs; } modint operator/(modint rhs){ return modint(*this)/=rhs; } modint &operator+=(modint rhs){ val+=rhs.val; val-=((val>=mod)?mod:0); return (*this); } modint &operator-=(modint rhs){ val+=((val<rhs.val)?mod:0); val-=rhs.val; return (*this); } modint &operator*=(modint rhs){ val=val*rhs.val%mod; return (*this); } modint &operator/=(modint rhs){ u64 ex=mod-2; modint now=1; while(ex){ now*=((ex&1)?rhs:1); rhs*=rhs,ex>>=1; } return (*this)*=now; } bool operator==(modint rhs){ return val==rhs.val; } bool operator!=(modint rhs){ return val!=rhs.val; } friend std::ostream &operator<<(std::ostream& os,modint x){ return os<<(x.val); } friend std::istream &operator>>(std::istream& is,modint& x){ u64 t; is>>t,x=t; return is; } }; template<u64 mod> struct NTT{ typedef modint<mod> mint; mint g=0; int limit=0; vector<mint> zeta; mint power_NTT(mint a,u64 n){ mint res=1; while(n){ res*=((n&1)?a:1); a*=a; n>>=1; } return res; } NTT(){ for(g=2;;g+=1){ if(power_NTT(g,(mod-1)>>1)!=1){ break; } } u64 now=(mod-1); while(!(now&1)){ now>>=1; ++limit; } zeta.resize(limit+1,1); zeta[limit]=power_NTT(g,now); for(int i=limit-1;i>=0;--i){ zeta[i]=zeta[i+1]*zeta[i+1]; } } void dft(vector<mint>& f,int cnt){ for(int i=0;i<(1<<cnt);++i){ int j=0; for(int k=0;k<cnt;++k){ j+=((i>>k)&1)<<(cnt-1-k); } if(i<j){ swap(f[i],f[j]); } } for(int b=0;b<cnt;++b){ mint now=1; for(int j=0;j<(1<<b);++j){ for(int k=0;k<(1<<cnt);k+=(1<<(b+1))){ mint s=f[k+j],t=f[k+j+(1<<b)]*now; f[k+j]=s+t,f[k+j+(1<<b)]=s-t; } now*=zeta[b+1]; } } } vector<mint> mul_naive(vector<mint> a,vector<mint> b){ vector<mint> res(a.size()+b.size()-1); for(int i=0;i<int(a.size());++i){ for(int j=0;j<int(b.size());++j){ res[i+j]+=a[i]*b[j]; } } return res; } vector<mint> mul_fast(vector<mint> a,vector<mint> b){ int cnt=0,siz=1,mxsiz=a.size()+b.size()-1; while(siz<mxsiz){ siz<<=1,++cnt; } assert(cnt<=limit); a.resize(siz),b.resize(siz); dft(a,cnt),dft(b,cnt); for(int i=0;i<siz;++i){ a[i]*=b[i]; } dft(a,cnt); reverse(a.begin()+1,a.end()); mint isiz=mint(1)/siz; for(int i=0;i<siz;++i){ a[i]*=isiz; } a.resize(mxsiz); return a; } vector<mint> mul(vector<mint> a,vector<mint> b){ if(min(a.size(),b.size())<=64){ return mul_naive(a,b); } else{ return mul_fast(a,b); } } }; template<u64 mod> struct Poly{ typedef modint<mod> mint; NTT<mod> ntt; vector<mint> val; Poly():val({0}){} Poly(int siz):val(siz){} Poly(initializer_list<modint<mod>> init):val(init){} Poly(vector<mint> init):val(init){} mint &operator[](int i){ return val[i]; } int size(){ return val.size(); } void resize(int siz){ val.resize(siz); } Poly operator+(Poly rhs){ return Poly(*this)+=rhs; } Poly operator-(Poly rhs){ return Poly(*this)-=rhs; } Poly operator*(Poly rhs){ return Poly(*this)*=rhs; } Poly operator/(Poly rhs){ return Poly(*this)/=rhs; } Poly operator%(Poly rhs){ return Poly(*this)%=rhs; } Poly operator-(){ for(mint& v:val){ v=mint(0)-v; } return (*this); } Poly operator+=(Poly rhs){ resize(max(this->size(),rhs.size())); for(int i=0;i<int(rhs.size());++i){ (*this)[i]+=rhs[i]; } shrink(); return (*this); } Poly operator-=(Poly rhs){ resize(max(this->size(),rhs.size())); for(int i=0;i<int(rhs.size());++i){ (*this)[i]-=rhs[i]; } shrink(); return (*this); } Poly operator*=(Poly rhs){ val=ntt.mul(val,rhs.val); return (*this); } Poly operator/=(Poly rhs){ if(val.size()<rhs.size()){ val.resize(0); return (*this); } int rsiz=val.size()-rhs.size()+1; reverse(val.begin(),val.end()); reverse(rhs.val.begin(),rhs.val.end()); val.resize(rsiz),rhs.inv(rsiz); (*this)*=rhs; val.resize(rsiz); reverse(val.begin(),val.end()); return (*this); } Poly operator%=(Poly rhs){ if(val.size()<rhs.size()){ return (*this); } (*this)-=(*this)/rhs*rhs; val.resize(rhs.size()-1); shrink(); return (*this); } void inv(int mx){ Poly g({mint(1)/val[0]}); int now=1; while(now<mx){ now<<=1; Poly t=(*this); t.resize(now); t*=g,t=-t; t[0]+=2,g*=t; g.resize(now); } g.resize(mx); (*this)=g; } void shrink(){ for(int i=val.size()-1;i>0;--i){ if(val[i]==0){ val.pop_back(); } else{ return; } } } void get(){ for(int i=0;i<int(val.size());++i){ cin>>val[i]; } } void out(){ cout<<val[0]; for(int i=1;i<int(val.size());++i){ cout<<" "<<val[i]; } cout<<"\n"; } vector<mint> multieval(vector<modint<mod>> a){ int siz=1; while(siz<int(a.size())){ siz<<=1; } vector<Poly<mod>> t(siz*2-1,{1}); for(int i=0;i<int(a.size());++i){ t[i+siz-1]={-a[i],1}; } for(int i=siz-2;i>=0;--i){ t[i]=t[2*i+1]*t[2*i+2]; } vector<Poly<mod>> g(siz*2-1); g[0]=(*this)%t[0]; for(int i=1;i<siz*2-1;++i){ g[i]=g[(i-1)/2]%t[i]; } vector<modint<mod>> res(a.size()); for(int i=0;i<int(a.size());++i){ res[i]=g[i+siz-1][0]; } return res; } void product(vector<Poly<mod>> a){ int siz=1; while(siz<int(a.size())){ siz<<=1; } vector<Poly<mod>> res(siz*2-1,{1}); for(int i=0;i<int(a.size());++i){ res[i+siz-1]=a[i]; } for(int i=siz-2;i>=0;--i){ res[i]=res[2*i+1]*res[2*i+2]; } (*this)=res[0]; } }; int main(){ constexpr u64 mod=998244353; int N,M; cin>>N>>M; Poly<mod> f(N); f.get(); vector<modint<mod>> a(M); for(int i=0;i<M;++i){ cin>>a[i]; } vector<modint<mod>> b=f.multieval(a); cout<<b[0]; for(int i=1;i<M;++i){ cout<<" "<<b[i]; } cout<<"\n"; return 0; }