新技能——FFT。 可在 \(O(nlogn)\) 时间内完成多项式在系数表达与点值表达之间的转换。 其中最关键的一点便为单位复数根，有神奇的折半性质。 多项式乘法（即为卷积）的常见形式：\[ C_n=\sum\limits_{i=0}^n A_iB_{n-i} \] 基本思路为先将系数表达 -> 点值表达 \(O(nlogn)\) 随后点值 \(O(n)\) 进行乘法运算 最后将点值表达 -> 系数表达 \(O(nlogn)\)
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 2100005;
const double pi = 3.1415926535897932384626433832795;
struct c{
double r,i;
c() { r=i=0.0; }
c(double x,double y) { r=x; i=y; }
c operator + (const c &b) { return c(r+b.r,i+b.i); }
c operator += (const c &b) { return *this=*this+b; }
c operator - (const c &b) { return c(r-b.r,i-b.i); }
c operator -= (const c &b) { return *this=*this-b; }
c operator * (const c &b) { return c(r*b.r-i*b.i,r*b.i+b.r*i); }
c operator *= (const c &b) { return *this=*this*b; }
}a[N],b[N],x[N];
int l;
int r[N];
void fft(c A[],int ty){
for(int i=0;i<l;i++) x[r[i]]=A[i];
for(int i=0;i<l;i++) A[i]=x[i];
for(int i=2;i<=l;i<<=1){
c wn(cos(pi*2/i),ty*sin(pi*2/i));
for(int j=0;j<l;j+=i){
c w(1,0);
for(int k=j;k<j+i/2;k++){
c t=A[k+i/2]*w;
A[k+i/2]=A[k]-t;
A[k]+=t;
w*=wn;
}
}
}
}
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++) scanf("%lf",&a[i].r);
for(int i=0;i<=m;i++) scanf("%lf",&b[i].r);
l=1;
while(l<=n+m) l<<=1;
for(int i=0;i<l;i++) r[i]=(r[i>>1]>>1)|((i&1)*(l>>1));
fft(a,1);fft(b,1);
for(int i=0;i<l;i++)
a[i]*=b[i];
fft(a,-1);
for(int i=0;i<n+m;i++)
printf("%d ",int(a[i].r/l+0.5));
printf("%d",int(a[n+m].r/l+0.5));
return 0;
}
转载于:https://www.cnblogs.com/lindalee/p/8511814.html
