代码

#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;}U R[N],T[N]{0,1};void f(U*a){for(U b=1;b^N;b++)if(R[b]<b)a[b]^=a[R[b]]^=a[b]^=a[R[b]];for(U b=1,c,d,e,f;b^N;b*=2)for(c=0;c^N;c+=b*2)for(d=0;d^b;d++)e=a[c+d],f=(V)a[b+c+d]*T[b+d]%P,(a[c+d]=e+f)>=P&&(a[c+d]-=P),(a[b+c+d]=e-f)>=P&&(a[b+c+d]+=P);}void poly_multiply(U*a,int b,U*c,int d,U*e){for(U a=1;a^N;a++)R[a]=(R[a/2]+a%2*N)/2;for(U a=2,b,c;a^N;a*=2)for(b=F(3,P/a/2),c=a/2;c^a;c++)T[c*2]=T[c],T[c*2+1]=(V)T[c]*b%P;U g[N]{},h[N]{};__builtin_memcpy(g,a,b*4+4),__builtin_memcpy(h,c,d*4+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=0,j=F(N,P-2);i^N;i++)h[i]=(V)g[(N-i)%N]*j%P;__builtin_memcpy(e,h,b*4+d*4+4);}

评测结果