## 回来第一次复习FFT

### 前置知识

1.复数相关

$a+bi$

$$(a+bi)+(c+di)=(a+c)+(b+d)i$$

$$(a+bi)-(c+di)=(a-c)+(b-d)i$$

$$(a+bi)*(c+di)=(ac-bd)+(ad+bc)i$$

2.点值表示法

$$A_n=a_0+a_1x+a_2x^2+...+a_nx^n$$

$$A_n=2+5x+3x^2$$

3.1.单位根

$$\omega_n^k=\cos \frac{2k\pi}{n}+i\sin \frac{2k\pi}{n}$$

3.2.单位根的性质

$$\omega_n^k=\cos \frac{2k\pi}{n}+i\sin \frac{2k\pi}{n}$$

$$\omega_{2n}^{2k}=\omega_n^k$$

$$\omega_n^{k+\frac{n}{2}}=-\omega_n^k$$

$$\omega_n^n=\omega_n^0=1$$

$k\not= 0$ 时

$$\sum_{i=1}^n\omega_n^{ki}=0$$

$k=0$ 时

$$\sum_{i=1}^n\omega_n^{ki}=n$$

### 快速傅里叶变换(FFT)(Fast Fourier Transfromation)

$$A(x)=a_0+a_1x+a_2x^2+...+a_{n-1}^{n-1}$$

$$=(a_0+a_2x^2+....+a_{n-2}x^{n-2})+(a_1x+a_3x^3+...+a_{n-1}x^{n-1})$$

$$=(a_0+a_2x^2+....+a_{n-2}x^{n-2})$$

$$+x(a_1+a_3x^2+...+a_{n-1}x^{n-2})$$

$$A_1(x)=a_0+a_2x+....+a_{n-2}x^{\frac{n}{2}-1}$$

$$A_2(x)=a_1+a_3x+...+a_{n-1}x^{\frac{n}{2}-1}$$

$$A(x)=A_1(x^2)+xA_2(x^2)$$

$$A(\omega_n^k)=A_1(\omega_n^{2k})+\omega_n^kA_2(\omega_n^{2k})$$

$$A(\omega_n^{k+\frac{n}{2}})=A_1(\omega_n^{2k+n})+\omega_n^{k+\frac{n}{2}}A_2(\omega_n^{2k+n})$$

$$=A_1(\omega_n^{2k})-\omega_n^kA_2(\omega_n^{2k})$$

$$A(\omega_n^k)=A_1(\omega_n^{2k})+\omega_n^kA_2(\omega_n^{2k})$$

$$A(\omega_n^{k+\frac{n}{2}})=A_1(\omega_n^{2k})-\omega_n^kA_2(\omega_n^{2k})$$

### 快速傅里叶逆变换(IFFT)(Fast Fourier Inverse Transformation)

$$c_k=\sum_{i=0}^{n-1}y_i(\omega_n^{-k})^i$$

$$=\sum_{i=0}^{n-1}(\sum_{j=0}^{n-1}a_j(\omega_n^{i})^j)(\omega_n^{-k})^i$$

$$=\sum_{i=0}^{n-1}(\sum_{j=0}^{n-1}a_j(\omega_n^{i})^j)(\omega_n^{-k})^i$$

$$=\sum_{j=0}^{n-1}a_j\sum_{i=0}^{n-1}(\omega_n^i)^{(j-k)}$$

$j=k$ 时

$$\sum_{i=0}^{n-1}(\omega_n^i)^{(j-k)}=n$$

$$\sum_{i=0}^{n-1}(\omega_n^i)^{(j-k)}=0$$

$$c_k=na_k$$

$$a_k=\frac{c_k}{n}$$

### 板子题

【模板】多项式乘法

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<iostream>

using namespace std;

#define fr(i,a,b) for(register long long i=a;i<=b;i++)

const double Pi=acos(-1.0);

struct complex{
double x,y;
complex(double xx=0,double yy=0){x=xx,y=yy;}
}a[5000010],b[5000010];
complex operator + (complex a,complex b){return complex(a.x+b.x,a.y+b.y);}
complex operator - (complex a,complex b){return complex(a.x-b.x,a.y-b.y);}
complex operator * (complex a,complex b){return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}

long long n,m,limit,l;
long long r[5000010];

inline long long v_in(){
char ch=getchar();long long sum=0,f=1;
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) sum=(sum<<3)+(sum<<1)+(ch^48),ch=getchar();
return sum*f;
}

void FFT(complex *A,long long type){
fr(i,0,limit-1) if(i<r[i]) swap(A[i],A[r[i]]);
for(register long long mid=1;mid<limit;mid<<=1){
complex Wn(cos(Pi/mid),type*sin(Pi/mid));
for(register long long j=0;j<limit;j+=(mid<<1)){
complex W(1,0);
for(register long long k=0;k<mid;k++,W=W*Wn){
complex x=A[j+k],y=W*A[j+mid+k];
A[j+k]=x+y;
A[j+mid+k]=x-y;
}
}
}
}

void inpt(){
n=v_in(),m=v_in();
fr(i,0,n) a[i].x=v_in();
fr(i,0,m) b[i].x=v_in();
limit=1,l=0;
while(limit<n+m+1) limit<<=1,l++;
fr(i,0,limit-1) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
}

void work(){
FFT(a,1);
FFT(b,1);
fr(i,0,limit) a[i]=a[i]*b[i];
FFT(a,-1);
}

int main(){
inpt();
work();
fr(i,0,n+m) printf("%lld ",(int)(a[i].x/limit+0.5));
printf("\n");
return 0;
}