代码

#include<cstring>
#include<algorithm>
using namespace std;
const unsigned int mod=998244353,G=3;
inline int qpow(int a,int b)
{
	int ret=1;
	while(b)
	{
		if(b&1)
		{
			ret=(long long)
			ret*a%mod;
		}
		a=(long long)
		a*a%mod,b>>=1;
	}
	return ret;
}
inline void NTT(int n,unsigned int *F)
{
	static unsigned long long f[1<<21];
	for(int i=0;i<n;i++)
	{
		f[i]=F[i];
	}
	static int g[1<<21];
	for(int i=0;i<n;i++)
	{
		if((g[i]=(g[i>>1]|(i&1)*n)>>1)>i)
		{
			swap(f[i],f[g[i]]);
		}
	}
	static int w[1<<20];
	w[0]=1;
	for(int i=1;i<n;i<<=1)
	{
		int W=qpow(G,(mod-1)/(i<<1));
		for(int j=1;j<i;j++)
		{
			w[j]=(long long)
			w[j-1]*W%mod;
		}
		for(int j=0;j<n;j+=i<<1)
		{
			for(int k=0;k<i;k++)
			{
				unsigned long long x=f[j|k],y=w[k]*f[i|j|k]%mod;
				f[j|k]=x+y,f[i|j|k]=x+mod-y;
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		F[i]=f[i]%mod;
	}
}
inline void convolution(int n,int m,unsigned int *a,unsigned int *b,unsigned int *c)
{
	int N=1<<__lg(n+m)+1;
	static int f[1<<21],g[1<<21];
	memcpy(f,a,n+1<<2),NTT(N,f);
	memcpy(g,b,m+1<<2),NTT(N,g);
	for(int i=0;i<N;i++)
	{
		f[i]=(long long)
		f[i]*g[i]%mod;
	}
	NTT(N,f);
	int inv=qpow(N,mod-2);
	for(int i=0;i<=n+m;i++)
	{
		c[i]=(long long)
		f[N-i&N-1]*inv%mod;
	}
}
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c)
{
	convolution(n,m,a,b,c);
}

评测结果