代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
complex<double>f[2097152];
void DIF(int n,complex<double>f[]){
  for(int i=n;i>=2;i>>=1){
    complex<double>wn(cos(2*M_PI/i),sin(2*M_PI/i));
    for(int j=0;j<n;j+=i){
      complex<double>w(1,0),x,y;
      for(int k=j;k<j+i/2;k++)x=f[k],y=f[k+i/2],f[k]=x+y,f[k+i/2]=w*(x-y),w*=wn;
    }
  }
}
void DIT(int n,complex<double>f[]){
  for(int i=2;i<=n;i<<=1){
    complex<double>wn(cos(2*M_PI/i),sin(2*M_PI/i));
    for(int j=0;j<n;j+=i){
      complex<double>w(1,0),x,y;
      for(int k=j;k<j+i/2;k++)x=f[k],y=w*f[k+i/2],f[k]=x+y,f[k+i/2]=x-y,w*=wn;
    }
  }
  reverse(f+1,f+n);
  for(int i=0;i<n;i++)f[i]/=n;
}
void poly_multiply(unsigned a[],int n,unsigned b[],int m,unsigned c[]){
  for(int i=0;i<=max(n,m);i++)f[i]=complex<double>(a[i],b[i]);
  DIF(2<<__lg(n+m),f);
  for(int i=0;i<2<<__lg(n+m);i++)f[i]*=f[i];
  DIT(2<<__lg(n+m),f);
  for(int i=0;i<=n+m;i++)c[i]=f[i].imag()/2+0.5;
}

评测结果