有关FFT中的蝴蝶操作的疑问

蒟蒻特来请教，蝴蝶操作是干什么用的，例题见ZJOI2014 力，以下是标程
#include <cstdio>
#include <algorithm>
#include <complex>
using namespace std;
typedef complex<double> Complex;
#define LL long long
const int MAXN = 1 << 18;
const double PI = acos(-1.0);
void FFT(Complex P[], int n, int oper)
{
for (int i = 1, j = 0; i < n - 1; i++) {
for (int s = n; j ^= s >>= 1, ~j & s;);
if (i < j) swap(P[i], P[j]);
}//原地bit reversal
Complex unit_p0;
for (int d = 0; (1 << d) < n; d++) {
int m = 1 << d, m2 = m * 2;
double p0 = PI / m * oper;
unit_p0 = Complex(cos(p0), sin(p0));
for (int i = 0; i < n; i += m2) {
Complex unit = 1;
for (int j = 0; j < m; j++) {
Complex &P1 = P[i + j + m], &P2 = P[i + j];
Complex t = unit * P1;
P1 = P2 - t;
P2 = P2 + t;
unit = unit * unit_p0;
}
}
}
}
int n;
Complex x[MAXN], y[MAXN], z[MAXN], c[MAXN];
inline double squ(double k)
{
return k * k;
}
int main()
{
freopen("force.in", "r", stdin);
freopen("force.out", "w", stdout);
scanf("%d",&n);
for (int i = 0; i < n; i++)
scanf("%lf", &x[i]);
for (int i=0;i<n;i++) y[i]=-1.0/squ(n - i);
y[n]=0;
for (int i=n+1;i<=2*n;i++) y[i]=1.0/squ(i-n);
int MXN = 1;
while (MXN<n*2+1)
MXN<<=1;
//printf("%d\n", MXN);
for (int i=n;i<MXN;i++) x[i]=0;
for (int i=2*n+1;i<MXN;i++) y[i] = 0;
FFT(x, MXN, 1);
FFT(y, MXN, 1);
for (int i = 0; i < MXN; ++i) z[i] = x[i] * y[i];
FFT(z, MXN, -1);
for (int i = 0; i < MXN; ++i)
c[i] = z[i].real() / MXN;
for (int i = 0; i < n; i++)
printf("%.3f\n", c[n + i].real());
return 0;
}