代码

#include<bits/stdc++.h>
using namespace std;
#define re register
#define ui unsigned int
#define ull unsigned long long
const unsigned int mod=998244353;
const double pi=3.14159265358979323846264338327950;
const int maxn=(1<<21)+1;
struct com
{
	double a,b;
	inline com operator +(const com&A){return(com){a+A.a,b+A.b};}
	inline void operator +=(const com&A){a+=A.a,b+=A.b;}
	inline com operator -(const com&A){return(com){a-A.a,b-A.b};}
	inline com operator *(const com&A){return(com){a*A.a-b*A.b,a*A.b+b*A.a};}
	inline com operator *(re const double &o) {return (com){a*o,b*o};}
	inline com operator /(const int&A){return(com){a/A,b/A};}
	inline com operator !(){return(com){a,-b};}
	inline bool operator !=(const com&A){return a!=A.a||b!=A.b;}
};
com w[maxn],T1[maxn],xx1[maxn],xx2[maxn];
int getlen(re int n){re int x=1;for(n--;n;n>>=1,x<<=1);return x;}
ui x1[maxn],x2[maxn];
bool cp[maxn<<1];
void init(re int len)
{
	cp[1]=1;
	for(re int i=2;i<len;i++)
	{
		cp[i]=(cp[i>>1]&(!(i&1)))||(cp[i>>2]&((i>>1)&1));
	}
}
void fft(com*a,re int len)
{
	re ui i1=0;
	re com x1,x2,x3;
	for(re ui i=0,j=0;i<len;i++)
	{
		if(i<j)swap(a[i],a[j]);
		for(ui k=len>>1;;k>>=1)if((j^=k)>=k)break;
	}w[0]=(com){1,0};
	if(len>=2)
	{
		for(re ui i=0;i<len;i+=2)if(cp[(len+i)>>1])x1=a[i+1],a[i+1]=a[i]-x1,a[i]+=x1;
	}
	if(len>=4)
	for(re ui i=0;i<len;i+=4)
		if(cp[(len+i)>>2])
		{
			x1=a[i+2];
			x2=a[i+3];
			x3=(com){-x1.b+x2.b,-x2.a+x1.a};x1+=x2;
			a[i+2]=a[i]-x1;a[i]+=x1;
			a[i+3]=a[i+1]-x3;a[i+1]+=x3;
		}
	w[1]=(com){0,1};w[2]=(com){-1,0};
	for(re ui i=8,i2=3;i<=len;i<<=1,i2++)
	{
		i1=i>>2;
		com s=(com){cos(pi/i1/2),sin(pi/i1/2)};
		for(re ui j=3*i1-2;j>0;j-=2)
			w[j]=w[j>>1];
		for(re ui j=1;j<3*i1;j+=2)
			w[j]=s*w[j-1];
		for(re ui j=0;j<len;j+=i)
		if(cp[(len+j)>>i2]){re com*aa=a+j,*aaa=aa+i1,*bb=aaa+i1,*cc=bb+i1;
			for(re int k=0;k<i1;k++)
			{
				x1=w[k]*bb[k];
				x2=w[k*3]*cc[k];
				x3=(com){-x1.b+x2.b,-x2.a+x1.a};
				cc[k]=aaa[k]-x3;
				aaa[k]+=x3;
				x1+=x2;
				bb[k]=aa[k]-x1;
				aa[k]+=x1;
			}
		}
	}
}
void DFT(ui *a,com *R1,int n,int len) {
	for(re int i=0;i<n+1>>1;++i) R1[i]=(com){a[i<<1],a[i<<1|1]};
	fft(R1,len);
}
void DFTMul(com *R1,com *S1,int len) {
	for(re int i=0;i<len;++i) {
		re int j=len-1&len-i;
		com tmp=(i&len>>1)?(com){1,0}-w[i^len>>1]:w[i]+(com){1,0};
		T1[j]=R1[i]*S1[i]-(R1[i]-!R1[j])*(S1[i]-!S1[j])*tmp*0.25;
	}
}
void IDFT(ui *__ans,int r,int len) {
	fft(T1,len);
	for(re int i=0;i<r;++i) __ans[i]=(i&1)?(ull)(T1[i>>1].b/len+0.5)%mod:(ull)(T1[i>>1].a/len+0.5)%mod;
}
ui x3[2012342];
void poly_multiply(re unsigned *a,re int n,re unsigned *b,re int m,re unsigned *c)
{
	re int len=getlen(n+1),x;
	re unsigned int ans=0;
	init(len);
	DFT(a,xx1,n+1,len);DFT(b,xx2,m+1,len);
	DFTMul(xx1,xx2,len);
	IDFT(c,n+m+1,len);
}

评测结果