12/20/2018 重写。

### 基本概念

#### 多项式

##### 系数表示

\begin{aligned} A(x)=& \sum_{i=1}^{n-1}a_ix^i \\ =& a_0+a_1x+a_2x^2\cdots+a_{n-1}x^{n-1}\end{aligned}

##### 点值表示

\begin{aligned} y_i=& A(x_i) \\ =&\sum_{j=1}^{n-1}a_j x_i^j\end{aligned}

##### 多项式乘法

$$C(x)=A(x)\times B(x) = \sum_{k=0}^{2n-2}(\sum_{k=i+j}a_i b_j)x^k$$

$$C_{y_i}=(\sum_{j=0}^{2n-1}a_j x_i^j)\times(\sum_{j=0}^{2n-1}b_j x_i^j)=A_{y_i}\times B_{y_i}$$

#### 复数

##### 单位根

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

##### 性质

\begin{aligned} \omega_{2n}^{2k}=&\omega_n^k \\ \omega_n^{k+\frac{n}{2}}=& -\omega_n^k \end{aligned}

##### 欧拉公式

$$e^{ix}=\cos x+i\sin x$$

##### 单位根的代码实现

const double PI = acos(-1.0);
complex<double> wn=exp(complex<double>(0,PI/n));

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

$$A(x)=(a_0 + a_2 x^2 + a_4 x^4 + \cdots) + (a_1 x + a_3 x^3 + a_5 x^5 + \cdots)$$

\begin{aligned}A_1(x)=&a_0+a_2x+a_4x^2+\cdots \\ A_2(x)=& a_1 + a_3 x + a_5 x^2 + \cdots \end{aligned}

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

\begin{aligned} A(\omega_n ^ k) &= A_1(\omega_n ^ {2k}) + \omega_n ^ {k} A_2(\omega_n ^ {2k}) \\ &= A_1(\omega_{\frac{n}{2}} ^ {k}) + \omega_n ^ {k} A_2(\omega_{\frac{n}{2}} ^ {k}) \ \end{aligned}

\begin{aligned} 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} \times \omega_n ^ n)-\omega_n ^ {k} A_2(\omega_n ^ {2k} \times \omega_n ^ n) \\ &= A_1(\omega_n ^ {2k})-\omega_n ^ {k} A_2(\omega_n ^ {2k}) \\ &= A_1(\omega_{\frac{n}{2}} ^ {k})-\omega_n ^ {k} A_2(\omega_{\frac{n}{2}} ^ {k}) \ \end{aligned}

#### 傅里叶逆变换 (Inverse Fourier Transform)

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

\begin{aligned} c_k &= \sum\limits_{i = 0} ^ {n – 1} y_i (\omega_n ^ {-k}) ^ i \\ &= \sum\limits_{i = 0} ^ {n – 1} (\sum\limits_{j = 0} ^ {n – 1} a_j (\omega_n ^ i) ^ j) (\omega_n ^ {-k}) ^ i \\ &= \sum\limits_{i = 0} ^ {n – 1} (\sum\limits_{j = 0} ^ {n – 1} a_j (\omega_n ^ j) ^ i) (\omega_n ^ {-k}) ^ i \\ &= \sum\limits_{i = 0} ^ {n – 1} (\sum\limits_{j = 0} ^ {n – 1} a_j (\omega_n ^ j) ^ i (\omega_n ^ {-k}) ^ i) \\ &= \sum\limits_{i = 0} ^ {n – 1} \sum\limits_{j = 0} ^ {n – 1} a_j (\omega_n ^ {j – k}) ^ i \\ &= \sum\limits_{j = 0} ^ {n – 1} a_j (\sum\limits_{i = 0} ^ {n – 1} (\omega_n ^ {j – k}) ^ i) \end{aligned}

\begin{aligned} c_i &= n a_i \\ a_i &= \frac{1}{n} c_i \end{aligned}

### 代码实现

#### 预处理下标

000 001 010 011 100 101 110
0   1   2   3   4   5   6
0   2   4   6   1   3   5
0   4   2   6   1   5   3
0   4   2   6   1   5   3
000 100 010 110 001 101 011

#### 蝴蝶操作

\begin{aligned} b(k) & \leftarrow a(k) + \omega_n ^ k \times a(\frac{n}{2} + k) \\ b(\frac{n}{2} + k) & \leftarrow a(k)-\omega_n ^ k \times a(\frac{n}{2} + k) \ \end{aligned}

\begin{aligned} t & \leftarrow \omega_n ^ k \times a(\frac{n}{2} + k) \\ a(\frac{n}{2}+k) & \leftarrow a(k)-t \\ a(k) & \leftarrow a(k)+t \end{aligned}

### 代码

#include <bits/stdc++.h>
#define maxl 4294153
using namespace std;
typedef complex<double> cd;
const double PI=acos(-1.0);
cd a[maxl],b[maxl];
int n,m,s,bit,rev[maxl];
int x=0,flag=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-') ch=getchar();
if (ch=='-') flag=-1,ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
return x*flag;
}
void init(){
for (bit=1,s=2;(1<<bit)<n+m-1;++bit)
s<<=1;
for (int i=0;i<s;++i)
rev[i]=((rev[i>>1]>>1)|((i&1)<<(bit-1)));
}
// 预处理下标，二进制翻转
void fft(cd *a,int n,int dft){
for (int i=0;i<n;++i)
if (i<rev[i]) swap(a[i],a[rev[i]]);
for (int step=1;step<n;step<<=1){
cd wn=exp(cd(0,dft*PI/step));
// wn 提供了特定的幅角，原理见上文 复数：欧拉公式 和 单位根的代码实现
for (int j=0;j<n;j+=step<<1){
cd wnk(1,0);
for (int k=j;k<j+step;++k,wnk*=wn){
cd t=wnk*a[k+step];
a[k+step]=a[k]-t;
a[k]+=t;
}
}
}
if (dft==-1)
for (int i=0;i<n;++i)
a[i]/=n;
}

int main(){
n++,m++;init();
for (int i=0;i<n;++i)
for (int i=0;i<m;++i)
fft(a,s,1);
fft(b,s,1);
for (int i=0;i<s;++i)
a[i]*=b[i];
fft(a,s,-1);
for (int i=0;i<n+m-1;++i)
printf("%d ",(int)(a[i].real()+0.5));
putchar('\n');
return 0;
}