代码

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define re register
#define R register
#define ui unsigned int
#define ll long long
#define ull unsigned long long
#define geta(_x) (ll)(_x.a+0.5)
#define getb(_x) (ll)(_x.b+0.5)
using namespace std;
const int maxn=(1<<21)+1;
const double pi=3.14159265358979323846264338327950;
#define D(xx) y[xx].a=A1[xx].a*W[xx].a-A1[xx].b*W[xx].b;y[xx].b=A1[xx].a*W[xx].b+A1[xx].b*W[xx].a;A1[xx].a=A[xx].a-y[xx].a;A1[xx].b=A[xx].b-y[xx].b;A[xx].a+=y[xx].a;A[xx].b+=y[xx].b;
#define com cp
struct cp{
	double a,b;
	cp operator +(R const cp &o) {return (cp){a+o.a,b+o.b};}
	cp operator -(R const cp &o) {return (cp){a-o.a,b-o.b};}
	cp operator *(R const cp &o) {return (cp){a*o.a-b*o.b,a*o.b+b*o.a};}
	cp operator /(R const int o) {return (cp){a/o,b/o};}
	cp operator !() const{return (cp){a,-b};}
	cp operator -() const{return (cp){-a,-b};}
	cp operator *(R const double &o) {return (cp){a*o,b*o};}
} A1[maxn],A2[maxn],B1[maxn],B2[maxn],T1[maxn],T2[maxn],T3[maxn],w[maxn],w0[maxn];
void fft(cp *f,R int k,int v) {
	for(R int i=0,j=0;i<k;++i) {
		if(j<i) swap(f[i],f[j]);
		for(R int l=k>>1;(j^=l)<l;l>>=1);
	}
	w[0]=(cp){1,0};
	for(R int i=2;i<=k;i<<=1) {
		cp g=(cp){cos(2*pi/i),v*sin(2*pi/i)};
		for(R int j=i>>1;j>=0;j-=2) w[j]=w[j>>1];
		for(R int j=1;j<i>>1;j+=2) w[j]=w[j-1]*g;
		for(R int j=0;j<k;j+=i) {
			R cp *a=f+j,*b=a+(i>>1);
			for(R int l=0;l<i>>1;++l) {
				cp o=b[l]*w[l];
				b[l]=a[l]-o;
				a[l]=a[l]+o;
			}
		}
	}
	if(v==-1) for(R int i=0;i<k;++i) f[i]=f[i]/k;
}
int getlen(int n) {int ans=1;for(;ans<n;ans<<=1);return ans;}
void DFT(ui *a,cp *R1,int n,int len) {
	for(R int i=0;i<n+1>>1;++i) R1[i]=(cp){a[i<<1],a[i<<1|1]};
	fft(R1,len,1);
}
void DFTMul(cp *R1,cp *S1,int len) {
	for(R int i=0;i<len;++i) {
		R int j=len-1&len-i;
		cp tmp=(i&len>>1)?(cp){1,0}-w[i^len>>1]:w[i]+(cp){1,0};
		T1[i]=(R1[i]*S1[i]*4-(R1[i]-!R1[j])*(S1[i]-!S1[j])*tmp)*0.25;
	}
}
void IDFT(ui *__ans,int r,int len) {
	fft(T1,len,-1);
	for(R int i=0;i<r;++i) __ans[i]=(i&1)?getb(T1[i>>1]):geta(T1[i>>1]);
}
ui x1[(1<<21)+1],x2[(1<<21)+1],x3[(1<<21)+1];
com xx1[(1<<21)+1],xx2[(1<<21)+1];
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;
	DFT(a,xx1,n+1,len);DFT(b,xx2,m+1,len);
	DFTMul(xx1,xx2,len);
	IDFT(c,n+m+1,len);
}

评测结果