代码

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,gen=3;
namespace math{
	// fast power , (x and ans) must in [-mod,mod], y must in [-mod+1,mod-1] 
	typedef int i32;
	typedef unsigned int u32;
	typedef long long i64;
	typedef unsigned long long u64;
	template<typename T=int>
	inline T fsp(i64 x,int y,i64 ans=1){
		for(y<0?y+=mod-1:0;y;y>>=1,x=x*x%mod)
			y&1?ans=ans*x%mod:0;
		return ans;
	}
	namespace fast_number_theory_transform{
		const int maxbit=22;
		const u32 modm2=mod+mod;
		// i64 mod_root[maxbit+1]; // mod_root[i]**(2**i) == 1
		// i64 mod_iroot[maxbit+1]; // mod_iroot[i]*mod_root[i] == 1

		// __attribute__((constructor))
		// inline void init_mod_root(){
		// 	mod_root[maxbit]=fsp(gen,mod>>(maxbit+1));
		// 	mod_iroot[maxbit]=fsp(mod_root[maxbit],mod-2);
		// 	for(int i=maxbit;i-->0;)
		// 		mod_root[i]=mod_root[i+1]*mod_root[i+1]%mod,
		// 		mod_iroot[i]=mod_iroot[i+1]*mod_iroot[i+1]%mod;
		// }

		// butterfly transform
		// int rev[1<<24];
		template<class T>
		inline void butterfly(T* p,int bit) {
			for(unsigned i=0,j=0;i<(1u<<bit);i++){
				// j=rev[i]=(rev[i>>1]>>1)^((i&1)<<(bit-1));
				if(i>j)swap(p[i],p[j]);
				for(unsigned l=1u<<(bit-1);(j^=l)<l;l>>=1);
			}
		}
		u32 *_q0[maxbit+1],*_p0[maxbit+1],*_q1[maxbit+1],*_p1[maxbit+1];
		inline void prep(int bit){
			static int k=0;
			for(;k<bit;k++){
				u32 *p,*q,nl=1<<k;
				u64 g=fsp(3,mod>>(k+1));
				p=_p0[k]=new u32[nl];
				for(int i=p[0]=1;i<nl;i++)p[i]=p[i-1]*g%mod;
				butterfly(p,k);
				q=_q0[k]=new u32[nl];
				for(int i=0;i<nl;i++)q[i]=(u64(p[i])<<32)/mod;
				g=fsp(g,-1);
				p=_p1[k]=new u32[nl];
				for(int i=p[0]=1;i<nl;i++)p[i]=p[i-1]*g%mod;
				butterfly(p,k);
				q=_q1[k]=new u32[nl];
				for(int i=0;i<nl;i++)q[i]=(u64(p[i])<<32)/mod;
			}
		}
		inline u32 ntt_mul(u32 x,u64 p,u64 q){
			// u32 y=x*p-(q*x>>32)*mod;
			return x*p-(q*x>>32)*mod;
		}
		void ntt(u32* a,int bit,bool f=0){
			prep(bit);
			for(int k=0,l=1,r=1<<bit;k<bit;k++){
				r>>=1;
				u32 *_p=_p0[k],*_q=_q0[k];
				u32 *_a0=a,*_a1=a+r;
				for(int i=0;i<l;i++,_a0+=r<<1,_a1+=r<<1)
					for(int j=0;j<r;++j){
						u32 x=_a0[j],y=ntt_mul(_a1[j],_p[i],_q[i]);
						x-=(x>=modm2)*modm2;
						_a0[j]=x+y;_a1[j]=x+modm2-y;
						// us u=xa[j]-(xa[j]>=us(MOD+MOD))*us(MOD+MOD);
						// us v=my_mul(xb[j],p[i],q[i]);
						// xa[j]=u+v;
						// xb[j]=u-v+us(MOD+MOD);
					}
				// i64 pw=1;
				// for(int j=0;j<(1<<k)-1;j++,pw=pw*mod_root[k]%mod){
				// 	for(int i=j;i<lim;i+=1<<(k+1)){
				// 		int x=a[i],&y=a[i^(1<<k)];
				// 		(a[i]+=y)<mod?0:a[i]-=mod;
				// 		y=pw*(x+mod-y)%mod;
				// 	}
				// }
				// for(int i=(1<<k)-1;i<lim;i+=1<<(k+1)){
				// 	int x=a[i],&y=a[i^(1<<k)];
				// 	(a[i]+=y)<mod?0:a[i]-=mod;
				// 	y=pw*(x+mod-y)%mod;
				// }
				l<<=1;
			}for(int i=0;i<(1<<bit);i++){
				a[i]-=(a[i]>=modm2)*modm2;
				a[i]-=(a[i]>=mod)*mod;
				// a[i]<mod?0:a[i]-=mod;
			}
			if(f)butterfly(a,bit);
		}
		
		void intt(u32* a,int bit,bool f=0){
			prep(bit);
			if(f)butterfly(a,bit);
			for(int k=bit,l=1,r=1<<bit;k-->0;){
				r>>=1;
				u32 *_p=_p1[k],*_q=_q1[k];
				u32 *_a0=a,*_a1=a+l;
				for(int i=0;i<r;i++,_a0+=l<<1,_a1+=l<<1)
					for(int j=0;j<l;++j){
						u32 x=_a0[j],&y=_a1[j];
						_a0[j]-=((_a0[j]+=y)>=modm2)*modm2;
						y=ntt_mul(x+modm2-y,_p[i],_q[i]);
					}
				l<<=1;
			}
			u64 iv=mod;iv<<=bit;iv=(iv-mod+1)>>bit;
			for(int i=0;i<(1<<bit);i++)
				a[i]=a[i]*iv%mod;
		}
	}using fast_number_theory_transform::ntt;
	using fast_number_theory_transform::intt;
}
using math::fsp;
using math::ntt;
using math::intt;
unsigned f[1<<21],g[1<<21];
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c){
	int bit=__lg(n+m)+1;
	memcpy(f,a,4*(n+1));
	memcpy(g,b,4*(m+1));
	ntt(f,bit);ntt(g,bit);
	for(int i=0;i<(1<<bit);i++)f[i]=1ll*f[i]*g[i]%mod;
	intt(f,bit);
	memcpy(c,f,4*(n+m+1));
}

评测结果