代码

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <complex>
#define MAX_N 2100005

using namespace std;

typedef complex<double> cd;

const double PI=acos(-1);

int n,m;
int rev[MAX_N];
cd f[MAX_N];
cd g[MAX_N];

void get_rev(int x)
{
	for(int i=0;i<(1<<x);i++)
	{
		rev[i]=(rev[i>>1]>>1)|((i&1)<<(x-1));
	}
}

void fft(cd *a,int n,int dft)
{
	for(int i=0;i<n;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
	for(int i=1;i<n;i<<=1)
	{
		cd wn=exp(cd(0,dft*PI/i));
		for(int j=0;j<n;j+=(i<<1))
		{
			cd wnk(1,0);
			for(int k=j;k<j+i;k++)
			{
				cd a0=a[k],a1=wnk*a[k+i];
				a[k]=a0+a1,a[k+i]=a0-a1;
				wnk*=wn;
			}
		}
	}
	if(dft==-1) for(int i=0;i<n;i++) a[i]/=n;
}

void poly_multiply(unsigned *a, int _n, unsigned *b, int _m, unsigned *c)
{
	n=_n,m=_m;
	int x,len=1,bt=0;
	while(len<n+m+1) len<<=1,bt++;
	for(int i=0;i<=n;i++) f[i]=a[i];
	for(int i=0;i<=m;i++) g[i]=b[i];
	get_rev(bt);
	fft(f,len,1),fft(g,len,1);
	for(int i=0;i<len;i++) f[i]*=g[i];
	fft(f,len,-1);
	for(int i=0;i<=n+m;i++) c[i]=(unsigned)(f[i].real()+0.5);
}

评测结果