快速傅里叶变换

用途在$O(nlo{g}_n)$复杂度内解决多项式乘法 比$O(N^2)$要优

$A(x)=a_0+a_{1}x+...+a_n{x}^n$

性质一：可以用n+1个点，表示一个n次多项式

证明用高斯消元，范德蒙行列式满秩唯一解。

点表示法：

如果多项式乘积为：$C(x)=A(x)B(x)$

那么：如果A(x)是n次的，B(x)是m次的，那么我们能用n+m+1个点表示C(x)。

$x_1,x_2,x_3.....x_{n+m+1}$

A对应的点为：$(x_1,A(x_1)),(x_2,A(x_2)....(x_{n+m+1},A(x_{n+m+1}))$

B对应的点为：$(x_1,B(x_1)),(x_2,B(x_2)....(x_{n+m+1},B(x_{n+m+1}))$

我们知道C(x)=A(x)B(x)

那么C对应的点为：$(x_1,A(x_1)B(x_1)),(x_2,A(x_2)B(x_2)....(x_{n+m+1},A(x_{n+m+1})B(x_{n+m+1}))$

所以我们可以通过O(n+m)表示出来C(x);

所以我们希望从系数表示法转化成点表示法，在从点表示法转化成系数表示法。

复数

欧拉公式证明：

证明过程参考繁凡博客吧。
https://www.wolai.com/naS2MSmNf2imHpmYtEpUtF#bedxV3DwQ7wfDDThBQg78S

递归版：未运行出来：

///FFT递归版#include using namespace std;const double pi = acos(-1);const int N = 300;struct Complex{    double x, y;    Complex(double x = 0, double y = 0): x(x), y(y) {}} A[N], B[N];Complex operator * (Complex J, Complex Q){    //模长相乘，幅度相加    return Complex(J.x * Q.x - J.y * Q.y, J.x * Q.y + J.y * Q.x);}Complex operator - (Complex J, Complex Q){    return Complex(J.x - Q.x, J.y - Q.y);}Complex operator + (Complex J, Complex Q){    return Complex(J.x + Q.x, J.y + Q.y);}void FFT(int limit, Complex *a, int type){    if(limit == 1) return ;//常数项    Complex a1[limit / 2], a2[limit / 2]; //分成两端，左右两端平分    for(int i = 0; i <= limit; i += 2) //偶数项,奇数项    {        a1[i / 2] = a[i];        a2[i / 2] = a[i + 1];    }    FFT(limit / 2, a1, type);    FFT(limit / 2, a2, type);    Complex tmp = Complex(cos(2.0 * pi / limit), type * sin(2.0 * pi / limit)), w = Complex(1, 0);    ///tmp表示单位根，w表示幂。    for(int i = 0; i < (limit /2); i++, w = w * tmp)    {        a[i] = a1[i] + w * a2[i]; //左加        a[i + limit / 2] = a1[i] - w * a2[i]; //右减    }}int main(){    int n, m;    scanf("%d%d", &n, &m);    for(int i = 0; i <= n; i++)scanf("%lf", &A[i].x);    for(int i = 0; i <= m; i++)scanf("%lf", &B[i].x);    int limit = 1;    while(limit <= n + m) limit *= 2; //2的整数次幂    FFT(limit, A, 1);    FFT(limit, B, 1);    //后面的1表示要进行的变换是什么类型    // 1表示从系数变为点值    //-1表示从点值变为系数    //这就与推导过程中的 w指数部分正负有关。    for(int i = 0; i <= limit; i++)    {        A[i] = A[i] * B[i];    }    FFT(limit, A, -1);    for(int i = 0;i <= n + m; i++)    {        printf("%d ", (int)(A[i].x / limit + 0.5)); ///对其四舍五入+0.5    }    return 0;}

迭代版

蝴蝶变换

///迭代版#include using namespace std;const int N = 5e6 + 7;const double PI = acos(-1);int n, m;int limit = 1;int res, ans[N];int l;int r[N];struct Complex{    double x, y;    Complex (double x = 0, double y = 0) : x(x), y(y) {}} a[N], b[N];Complex operator * (Complex J, Complex Q){    //模长相乘，幅度相加    return Complex(J.x * Q.x - J.y * Q.y, J.x * Q.y + J.y * Q.x);}Complex operator + (Complex J, Complex Q){    return Complex(J.x + Q.x, J.y + Q.y);}Complex operator - (Complex J, Complex Q){    return Complex(J.x - Q.x, J.y - Q.y);}void FFT(Complex *A, int type){    for(int i = 0; i < limit; i++)    {        if(i < r[i]) swap(A[i], A[r[i]]); ///保证不在换过去    }    ///从底层开始合并：    for(int mid = 1; mid < limit; mid = mid * 2)    {        ///待合并区间长度的一半，最开始是长度为1的合并，类似倍增的思想        Complex wn(cos(PI / mid), type * sin(PI / mid)); //单位根        for(int len = mid *2, pos = 0; pos < limit; pos += len)        {            ///len是区间的长度，pos是当前的位置            Complex w(1, 0);            for(int k = 0; k < mid; k++, w = w * wn)            {                ///只扫左半部分，蝴蝶变换得到有半部分。                Complex x = A[pos + k]; //左半部分                Complex y = w * A[pos + mid + k]; //右半部分                A[pos + k] = x + y;//左加                A[pos + mid + k] = x - y;///右减            }        }    }    if(type 
                 

                                                                                                                    
                         超融合服务器
                                             
                         云服务器
                                                                                                                                                 
                                      
                     
                    
                                                                                               傅里叶变换
                                                                                                           傅里叶变换图像识别
                                                                                                           傅里叶
                                                                                                           鼠标变换