默认n是2的整数幂次。f(x)=a0+a1+...+an-1，比如8，对应的bit就是3，因为只有a0a7，rev[i]是把一个数在二进制下倒过来，思想是把一个数在2进制下分为前bit-1位和最后一位的话，需要让前bit-1位倒过来，并把最后一位放到前面去，由于让rev[i>>1]倒过来会多出一个后缀0，因此需要>>1，然后把i给移动bit-1位到最前面。在实现提前把a[i]放到正确位置上的时候，要在irev[i]的时候之前到rev[i]的时候已经把原来的rev[i]的位置已经与i的位置交换了，再交换就换回来了。后面mid是枚举要合并的一半，temp中应该cos(2pi/mid2)+sin(2pi/mid2),已约分。i是枚举起始点，j是枚举左边的一半，a[i]~a[i+mid-1]储存了图片说明 （k从1到n/2）的A值，为了让a[i+j]的变化与a[i+j+mid]的变化相互独立，用x，y先储存，然后再进行操作，美其名曰蝴蝶变换...
代码：

#include<complex>
#define cp complex<double>
const double pi = acos(-1.0);
void fft(cp *a, int n, int inv)
{
    int bit = 0;
    while((1<<bit)<n)bit++;
    for(int i = 0; i <= n-1; i++)
    {
        rev[i]=(rev[i>>1]>>1|((i&1)<<(bit-1)));
        if(i < rev[i]) swap(a[i],a[rev[i]]);
    }
    for(int mid = 1; mid < n; mid*=2)
    {
        cp temp(cos(pi/mid),inv*sin(pi/mid));
        for(int i = 0; i < n; i+=mid*2)
        {
            cp omega(1,0);
            for(int j = 0; j < mid; j++,omega*=temp)
            {
                cp x = a[i+j], y = omega*a[i+j+mid];
                a[i+j] = x+y, a[i+j+mid]=x-y;
            }
        }
    }
}

两个多项式a,b相乘再转系数多项式c，通常只用打这么一小段

cp a[MAXN],b[MAXN];
    int c[MAXN];
    fft(a,n,1),fft(b,n,1);//1系数转点值
    fo(i,0,n-1)a[i]*=b[i];
    fft(a,n,-1);//-1点值转系数
    fo(i,0,n-1)c[i]=(int)(a[i].real()/n+0.5);//注意精度