代码

#pragma GCC optimize("Ofast")
using U=unsigned;using V=unsigned long long;constexpr U P=998244353,N=1<<21;
constexpr U F(U a,U b){U c=1;for(;b;b/=2)b&1&&(c=(V)c*a%P),a=(V)a*a%P;return c;}
void f(U*a){U b[N]{};for(U c=1;c<N;c++)b[c]=b[c>>1]>>1|(c&1)*N/2;for(U c=1,d,e,f,g,h,i,j;c<N;c=d)for(e=F(3,P/(d=c*2)),f=0;f<N;f+=d)for(g=1,h=f;h<f+c;g=(V)g*e%P,h++)i=a[h],j=(V)a[h+c]*g%P,(a[h]=i+j)>=P&&(a[h]-=P),(a[h+c]=P+i-j)>=P&&(a[h+c]-=P);}
void poly_multiply(U*a,int b,U*c,int d,U*e){U g[N]{},h[N]{};__builtin_memcpy(a,g,b*4),__builtin_memcpy(c,h,d*4),f(g),f(h);for(U i=0;i<N;i++)g[i]=(V)g[i]*h[i]%P;f(g);for(U i=1,j=F(N,P-2);i<N;i++)h[i]=(V)g[(N-i)%N]*j%P;__builtin_memcpy(h,e,b*4+d*4);}

评测结果