Submit Info #56867

Problem Lang User Status Time Memory
Multipoint Evaluation cpp turtle0123 AC 3272 ms 304.44 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.61 MiB
example_01 AC 1 ms 0.61 MiB
max_random_00 AC 3272 ms 304.44 MiB
max_random_01 AC 3271 ms 304.43 MiB
random_00 AC 730 ms 85.58 MiB
random_01 AC 585 ms 77.97 MiB
random_02 AC 2801 ms 299.17 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-(){ return modint(*this)=mod-val; } 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=-1; int limit=0; vector<mint> zeta,zeta_inv; 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_inv.resize(limit+1,1); zeta[limit]=power_NTT(g,now); zeta_inv[limit]/=zeta[limit]; for(int i=limit-1;i>=0;--i){ zeta[i]=zeta[i+1]*zeta[i+1]; zeta_inv[i]=zeta_inv[i+1]*zeta_inv[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]; } } } void idft(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_inv[b+1]; } } } vector<mint> mul(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]; } idft(a,cnt); mint isiz=mint(1)/siz; for(int i=0;i<siz;++i){ a[i]*=isiz; } a.resize(mxsiz); return a; } vector<mint> mul_naive(vector<mint> a,vector<mint> b){ vector<mint> res(a.size()+b.size()-1); if(a.size()>b.size()){ 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]; } } } else{ for(int j=0;j<int(b.size());++j){ for(int i=0;i<int(a.size());++i){ res[i+j]+=a[i]*b[j]; } } } return res; } }; template<u64 mod> struct FPS{ typedef modint<mod> mint; NTT<mod> ntt; vector<mint> val; FPS(int siz=0,vector<mint> init={}):val(siz){ if(!init.empty()){ val=init; } } mint &operator[](int i){ return val[i]; } size_t size(){ return val.size(); } void resize(const int siz){ val.resize(siz); } FPS operator+(FPS rhs){ return FPS(*this)+=rhs; } FPS operator-(FPS rhs){ return FPS(*this)-=rhs; } FPS operator*(FPS rhs){ return FPS(*this)*=rhs; } FPS operator/(FPS rhs){ return FPS(*this)/=rhs; } FPS operator%(FPS rhs){ return FPS(*this)%=rhs; } void inv_add(){ for(mint& v:val){ v=mint(0)-v; } } void inv_mul(int mx){ FPS g(1); g[0]=mint(1)/val[0]; int now=1; while(now<mx){ now<<=1; FPS t=(*this); t.resize(now); t*=g,t.inv_add(); t[0]+=2,g=g*t; g.resize(now); } g.resize(mx); (*this)=g; } FPS operator+=(FPS rhs){ val.resize(max(val.size(),rhs.size())); for(int i=0;i<int(rhs.size());++i){ val[i]+=rhs[i]; } return (*this); } FPS operator-=(FPS rhs){ val.resize(max(val.size(),rhs.size())); for(int i=0;i<int(rhs.size());++i){ val[i]-=rhs[i]; } return (*this); } FPS operator*=(FPS rhs){ if(min(val.size(),rhs.val.size())<=128){ val=ntt.mul_naive(val,rhs.val); return (*this); } val=ntt.mul(val,rhs.val); return (*this); } FPS operator/=(FPS rhs){ if(val.size()<rhs.size()){ val.assign(1,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_mul(rsiz); (*this)*=rhs; val.resize(rsiz); reverse(val.begin(),val.end()); return (*this); } FPS operator%=(FPS rhs){ if(val.size()<rhs.size()){ return (*this); } (*this)-=(*this)/rhs*rhs; val.resize(rhs.size()-1); return (*this); } }; template<u64 mod> FPS<mod> product(vector<FPS<mod>> a){ int siz=1; while(siz<int(a.size())){ siz<<=1; } vector<FPS<mod>> res(siz*2-1,{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]; } return res[0]; } template<u64 mod> vector<modint<mod>> multipoint_evaluation(FPS<mod> f,vector<modint<mod>> a){ int siz=1; while(siz<int(a.size())){ siz<<=1; } vector<FPS<mod>> t(siz*2-1,{1,{1}}); for(int i=0;i<int(a.size());++i){ t[i+siz-1].val={-a[i],1}; } for(int i=siz-2;i>=0;--i){ t[i]=t[2*i+1]*t[2*i+2]; } vector<FPS<mod>> g(siz*2-1); g[0]=f%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; } int main(){ constexpr u64 mod=998244353; int N,M; scanf("%d%d",&N,&M); FPS<mod> f(N); for(int i=0;i<N;++i){ int t; scanf("%d",&t); f[i]=t; } vector<modint<mod>> a(M); for(int i=0;i<M;++i){ int t; scanf("%d",&t); a[i]=t; } vector<modint<mod>> b=multipoint_evaluation(f,a); printf("%d",int(b[0].val)); for(int i=1;i<M;++i){ printf(" %d",int(b[i].val)); } printf("\n"); return 0; }