洛谷 3803 【模板】多项式乘法（FFT）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define db double
using namespace std;
const int N=1e6+5;const db pi=acos(-1.0);
int n,m,len,r[N<<2];//<<2! for (n+m)<<1
struct cpl{
  db x,y;
}I,a[N<<2],b[N<<2];
cpl operator+ (cpl a,cpl b){return (cpl){a.x+b.x,a.y+b.y};}
cpl operator- (cpl a,cpl b){return (cpl){a.x-b.x,a.y-b.y};}
cpl operator* (cpl a,cpl b){return (cpl){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}
int rdn()
{
  int ret=0;bool fx=1;char ch=getchar();
  while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)fx=0;ch=getchar();}
  while(ch>=‘0‘&&ch<=‘9‘) ret=(ret<<3)+(ret<<1)+ch-‘0‘,ch=getchar();
  return fx?ret:-ret;
}
void fft(cpl *a,bool fx)
{
  for(int i=0;i<len;i++)
    if(i<r[i])swap(a[i],a[r[i]]);
  for(int R=2;R<=len;R<<=1)//<=
    {
      int m=R>>1;
      cpl Wn=(cpl){ cos(pi/m),(fx?-1:1)*sin(pi/m) };
      for(int i=0;i<len;i+=R)
    {
      cpl w=I;
      for(int j=0;j<m;j++,w=w*Wn)
        {
          cpl tmp=w*a[i+m+j];
          a[i+m+j]=a[i+j]-tmp;
          a[i+j]=a[i+j]+tmp;
        }
    }
    }
}
int main()
{
  n=rdn(); m=rdn(); I.x=1; I.y=0;
  for(int i=0;i<=n;i++)a[i].x=rdn();
  for(int i=0;i<=m;i++)b[i].x=rdn();
  len=1;
  while(len<=n+m)len<<=1;//<=
  for(int i=0;i<len;i++)
    r[i]=(r[i>>1]>>1)+((i&1)?len>>1:0);
  fft(a,0);  fft(b,0);
  for(int i=0;i<len;i++)
    a[i]=a[i]*b[i];
  fft(a,1);
  for(int i=0;i<=n+m;i++)
    printf("%d ",int(a[i].x/len+0.5));puts("");
  return 0;
}