代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
typedef long long ll;
typedef unsigned un;
ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x;
}
using std::min;
using std::max;
template<typename T>bool umin(T& a,T t){if(a>t)return a=t,1;return 0;}
template<typename T>bool umax(T& a,T t){if(a<t)return a=t,1;return 0;}
ll abs(ll x){return x>0?x:-x;}
const int MAXN = 2097211;
const double PI=acos(-1.0);
struct comp
{
	double x,y;
	comp():x(0),y(0) {}
	comp(double x,double y):x(x),y(y) {}
	comp operator+ (const comp& you){return comp(x+you.x,y+you.y);}
	comp operator- (const comp& you){return comp(x-you.x,y-you.y);}
	comp operator* (const comp& you){return comp(x*you.x-y*you.y,x*you.y+y*you.x);}
}RT[MAXN],f[MAXN],g[MAXN];
int init(int n)
{
	int len=1;
	while(len<=n)len<<=1;
	for(int i=1;i<len;i<<=1)
	{
		comp R(cos(PI/i),sin(PI/i));
		RT[i]=comp(1,0);
		for(int j=1;j<i;++j)RT[i+j]=RT[i+j-1]*R;
	}
	return len;
}
int status[MAXN];
void DFT(comp* a,int len)
{
	for(int i=0;i<len;++i)
		if(status[i]>i)std::swap(a[i],a[status[i]]);
	for(int cur=1;cur<4&&cur<len;cur<<=1)
		for(int j=0;j<len;j+=cur<<1)
			for(int k=0;k<cur;++k)
			{
				comp x=a[j+k],y=a[j+cur+k]*RT[cur+k];
				a[j+k]=x+y,a[j+cur+k]=x-y;
			}
	for(int cur=4;cur<len;cur<<=1)
		for(int j=0;j<len;j+=cur<<1)
			for(int k=0;k<cur;k+=4)
			{
				comp y=a[j+cur+k]*RT[cur+k];
				a[j+cur+k]=a[j+k]-y,a[j+k]=a[j+k]+y;
				y=a[j+cur+k+1]*RT[cur+k+1];
				a[j+cur+k+1]=a[j+k+1]-y,a[j+k+1]=a[j+k+1]+y;
				y=a[j+cur+k+2]*RT[cur+k+2];
				a[j+cur+k+2]=a[j+k+2]-y,a[j+k+2]=a[j+k+2]+y;
				y=a[j+cur+k+3]*RT[cur+k+3];
				a[j+cur+k+3]=a[j+k+3]-y,a[j+k+3]=a[j+k+3]+y;
			}
}
void IDFT(comp* a,int len)
{
	std::reverse(a+1,a+len);
	DFT(a,len);
	for(int i=0;i<len;++i)a[i].x/=len,a[i].y/=len;
}
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c)
{
	int len=init(n+m);
	for(int i=0;i<=n;++i)f[i].x=a[i];
	for(int i=0;i<=m;++i)g[i].x=b[i];
	for(int i=0;i<len;++i)
		status[i]=(status[i>>1]>>1)|((i&1)?len>>1:0);
	DFT(f,len),DFT(g,len);
	for(int i=0;i<len;++i)f[i]=f[i]*g[i];
	IDFT(f,len);
	for(int i=0;i<=n+m;++i)c[i]=unsigned(f[i].x+0.5);
}

评测结果