快速傅里叶变换 (fast Fourier transform), 即利用计算机计算离散傅里叶变换（DFT)的高效、快速计算方法的统称，简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。

具体的贴出学习资源，个人认为讲解的非常好。

https://blog.csdn.net/ggn_2015/article/details/68922404

click

click

知识点以及证明综合都有利于理解。
上一道例题Gym100783C

题意：给定n个数的数组a，m个数的数组b，问b数组中的数有多少个可以由a数组中的1或者2个数值和组成，可以重复在a数组中选取。
可以看成，两个多项式的相乘，指数级别是相加的，系数分存在或者不存在，即0或者1。即a数组*a数组，看最后中的指数部分是否在b中出现。
自己非常菜，改的板子。
#include<cmath>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<istream>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<queue>
#define inf 0x3f3f3f3f
#define llinf 0x3f3f3f3f3f3f3f3f
#define MAX_len 210*4
using namespace std;
typedef long long ll;
const int MAXN = 262144 * 2+ 10;
const double PI = std::acos(-1.0);

struct Complex {
    double r, i;

    Complex(double r = 0, double i = 0) : r(r), i(i) {}

    Complex conj() const { return Complex(r, -i); }

    Complex operator+(const Complex &rhs) const { return Complex(r + rhs.r, i + rhs.i); }
    Complex operator-(const Complex &rhs) const { return Complex(r - rhs.r, i - rhs.i); }
    Complex operator*(const Complex &rhs) const { return Complex(r * rhs.r - i * rhs.i, r * rhs.i + i * rhs.r); }
    Complex operator/(double rhs) const { return Complex(r / rhs, i / rhs); }
};

class FFT {
private:
    static const int N = 262144*2;

    Complex omega[N + 1], omegaInv[N + 1];

    void init() {
        for (int i = 0; i < N; i++) {
            omega[i] = Complex(std::cos(2 * PI / N * i), std::sin(2 * PI / N * i));
            omegaInv[i] = omega[i].conj();
        }
    }

    void reverse(Complex *a, int n) {
        for (int i = 0, j = 0; i < n; i++) {
            if (i < j) std::swap(a[i], a[j]);
            for (int l = n >> 1; (j ^= l) < l; l >>= 1) {}
        }
    }

    void transform(Complex *a, int n, Complex *omega) {
        reverse(a, n);

        for (int l = 2; l <= n; l <<= 1) {
            int hl = l >> 1;
            for (Complex *x = a; x != a + n; x += l) {
                for (int i = 0; i < hl; i++) {
                    Complex t = omega[N / l * i] * x[i + hl];
                    x[i + hl] = x[i] - t;
                    x[i] = x[i] + t;
                }
            }
        }
    }

public:
    FFT() { init(); }

    int extend(int n) {
        int res = 1;
        while (res < n) res <<= 1;
        return res;
    }

    void dft(Complex *a, int n) {
        transform(a, n, omega);
    }

    void idft(Complex *a, int n) {
        transform(a, n, omegaInv);
        for (int i = 0; i < n; i++) a[i] = a[i] / n;
    }
} fft;
int aaa[MAXN];
map<int,int>hh1;
int main() {
    int n, m;
    scanf("%d", &n);

    static Complex a[MAXN], b[MAXN];
    int MAXXX=0;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&aaa[i]);
        hh1[aaa[i]]=1;
        MAXXX=max(MAXXX,aaa[i]);
    }
    for (int i = 0, x; i <=MAXXX; i++) {
        if(hh1[i])
        a[i] = Complex(1, 0);
        else
             a[i] = Complex(0, 0);
    }

    for (int i = 0; i <=MAXXX; i++) {
        if(hh1[i])
        a[i] = a[i] + Complex(0,1);
        else
                    a[i] = a[i] + Complex(0,0);
    }

    int len =MAXXX + MAXXX + 1;
    int N = fft.extend(len);

    fft.dft(a, N);
    for (int i = 1; i < N; i++) {
        double x1 = a[i].r, y1 = a[i].i;
        double x2 = a[N - i].r, y2 = a[N - i].i;
        Complex t1((x1 + x2) * 0.5, (y1 - y2) * 0.5);
        Complex t2((y1 + y2) * 0.5, (x2 - x1) * 0.5);
        b[i] = t1 * t2;
    }
    b[0] = a[0].r * a[0].i;
    fft.idft(b, N);
    int ans=0;
    for (int i = 0; i < len; i++)
    {
        int temp=(round(b[i].r));
        if(temp)
        {
            hh1[i]=1;
        }
    }
    scanf("%d",&m);
    for(int i=0;i<m;i++)
    {
        int x;
        scanf("%d",&x);
        if(hh1[x])
            ans++;
    }
     printf("%d",ans);

    return 0;
}
/*
3
1 3 5
6
2 4 5 7 8 9
*/

首先安利一个网站，在线做傅里叶变换，不用等MATLAB漫长的启动了

https://sci2fig.herokuapp.com/fourier

文章中部分图片来自

https://blog.csdn.net/ViatorSun/article/details/82387854

理论部分参考了：

https://homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm

https://plus.maths.org/content/fourier-transforms-images
零基础也能理解傅里叶变换后的频谱图
频谱图
类比
图像的傅里叶变换原理
位置信息
图像高频低频含义
对图像的操作所造成的影响
具体公式和理论应用
常见的傅里叶变换结果
练习题
解答

频谱图
声音的频谱图很好理解，尖峰代表着该频率有着更多的分量



关于数字信号处理的更多内容，这里安利我的学习笔记【持续更新中】：【从零开始学信号与系统】
但是图像的傅里叶变换抽象的多，下面讲讲述如何看懂傅里叶图。
类比
将图像视为变化的函数，不过不是随时间变化，而是跨图像的二维空间变化。

在灰度数字图像中，每个像素的值在0到255之间，代表该像素的暗度。因此，该像素的暗度或强度是水平坐标和垂直坐标的函数，给出了该像素的位置。您可以将图像视为起伏的景观，而高度由像素值确定。


图像也可以表示为正弦波的总和，但是这次，它们不是一维波，而是二维变化的波，就像纸张上的波纹。
二维正弦波写为
$z =sin（hx + ky）$
其中x和y给出“图纸”上各点的坐标，z是该点处波浪的高度或强度，a给出波浪的振幅（最大高度），h和k给出数字波分别在x和y方向重复的次数（它们是 x和y频率）。
当k = 0时，正弦波仅沿x轴波动。当h = 0时，它仅沿y轴波动。但是，如果k 和h都不为零，则正弦波在片材上对角移动，并且波的传播方向（垂直于波阵面）与斜率h / k成一定角度 。
图像的傅里叶变换原理
图像的傅立叶变换将图像（起伏的地形）分解为正弦波的总和。就像声波一样，对频率绘制傅立叶变换。但是与那种情况不同，频率空间具有二维，对于x和y维 中的波的频率 h和k。因此，它不是以一系列尖峰的形式绘制的，而是以与原始图像（大约）相同的像素尺寸绘制的图像。
位置信息
傅立叶变换中的每个像素都有一个坐标（h，k）表示在傅立叶变换中具有x频率h和 y频率k的正弦波的贡献。

中心点表示（0,0）波–没有波纹的平面–其强度（灰度颜色的亮度）是图像中像素的平均值。
中心左侧和右侧的点代表沿x轴变化的正弦波，即k = 0）。这些点的亮度表示傅立叶变换中具有该频率的正弦波的强度（强度是正弦波的振幅的平方）。
在中心点上下垂直的那些代表那些在y中变化但在x中保持恒定（即h = 0）的正弦波。傅立叶变换中的其他点表示对角波的贡献。



例如，考虑上面的图像，在左侧。这是二维波sin（x）被视为灰度图像。它的旁边是此灰度图像的傅立叶变换。
它具有与原始像素相同的尺寸（像素），并且全黑
在中心处有一些明亮的像素
放大傅立叶变换的中心（您可以在上面在右侧看到），您会看到恰好有三个不是黑色的像素。

一个是明亮的中心点，坐标为（0,0），代表（0,0）波对图像的贡献。
两侧的明亮像素具有坐标（1,0）和反射（-1,0），表示（1,0）波（我们原始图像中的正弦波）的贡献。
傅立叶变换中的所有其余像素都是黑色的，因为仅使用原始（1,0）波精确描述了原始图像。





图像高频低频含义
图像的频率是表征图像中灰度变化剧烈程度的指标，是灰度在平面空间上的梯度。
简短概括：

图像的高频，意味着灰度变化剧烈
图像的低频，意味着灰度变化平坦

不同频率信息在图像结构中有不同的作用：

图像的主要成分是低频信息，它形成了图像的基本灰度等级，对图像结构的决定作用较小；
中频信息决定了图像的基本结构，形成了图像的主要边缘结构；
高频信息形成了图像的边缘和细节，是在中频信息上对图像内容的进一步强化。

图像进行二维傅立叶变换得到频谱图，就是图像梯度的分布图,当然频谱图上的各点与图像上各点并不存在一一对应的关系，即使在不移频的情况下也是没有。

傅立叶频谱图上我们看到的明暗不一的亮点，实际是上图像上某一点与邻域点差异的强弱，即梯度的大小，也即该点的频率的大小（可以这么理解，图像中的低频部分指低梯度的点，高频部分相反）。
对图像的操作所造成的影响
在二维傅里叶变换中，空间域中横向的周期变化会反应在频谱图中的Y轴上，而空间域中纵向的周期变化会反应在频谱图中的X轴上。空间域中东南方向的周期变化会反应在频谱图中的东北方向，反之亦然。说明见下图。




具体公式和理论应用
参考：https://homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm

由于我们只关注数字图像，因此我们将讨论仅限于离散傅立叶变换（DFT）。
DFT是采样的傅立叶变换，因此不包含构成图像的所有频率，而仅包含足够大以完全描述空间域图像的一组采样。频率的数量对应于空间域图像中的像素数量，即，空间域和傅立叶域中的图像具有相同的大小。
对于大小为N×N的正方形图像，二维DFT由下式给出：



其中f（a，b）是空间域中的图像，指数项是与傅立叶空间中每个点F（k，l）对应的基函数。该方程式可以解释为：通过将空间图像乘以相应的基函数并将结果相加得出每个点F（k，l）的值。
基本函数是频率增加的正弦和余弦波，即 F（0,0）表示图像的DC分量，该分量对应于平均亮度，F（N-1，N-1）表示最高频率。
以类似的方式，可以将傅立叶图像重新变换到空间域。傅里叶逆变换由下式给出：

【这里不太会翻译，看图吧】



原网站还有关于低通滤波等操作的详细知识，吃透了再补文。
常见的傅里叶变换结果
不同频率的正弦波：



MIT的摄影师：


练习题
判断上面两张傅里叶变换频谱图和下面两张原始图像如何对应？


解答
右下角的图片灰度变化更剧烈，由于图像的频率是灰度的梯度，且傅里叶变换后高频特征位于边缘，因此对应着亮点分布在更边缘地区的左上图：

快速傅里叶变换(FFT)



快速傅里叶变换FFT

例题UOJ34 多项式乘法

简要解析


多项式

多项式的表示


单位复数根

定义
基本性质


DFT离散傅里叶变换
FFT快速傅里叶变换

递归
迭代
傅里叶逆变换公式
完整代码


参考资料











例题:UOJ#34. 多项式乘法


  
题目描述 

  给你两个多项式，请输出乘起来后的多项式。 

  输入格式 

  第一行两个整数 n 和 m，分别表示两个多项式的次数。 

  第二行 n+1 个整数，分别表示第一个多项式的 0 到 n 次项前的系数。 

  第三行 m+1 个整数，分别表示第一个多项式的 0 到 m 次项前的系数。 

  输出格式 

  一行 n+m+1 个整数，分别表示乘起来后的多项式的 0 到 n+m 次项前的系数。 

  样例 

  input: 

  1 2 

  1 2 

  1 2 1 

  output: 

  1 4 5 2 

  explanation: 

  $(1+2x)⋅(1+2x+x^2)=1+4x+5x^2+2x^3$ 

  限制与约定 

  0≤n , m≤$10^5$




简要解析

首先这道涉及多项式乘法,求相乘后新多项式的系数,可简记为: 

  
 $$C(x)=A(x)*B(x)=\sum_{j=0}^{2*n-2} (\sum_{k=0}^ja_k*b_{k-j})x^j$$  

  正常算法的时间复杂度很容易得到,即O($n^2$),显然无法再规定时间内得到正确解,怎么办呢?这里我们介绍一种可在O($nlgn$)复杂度下快速求出该答案的方法,即FFT.希望读者在阅读此文后可自行编写!




多项式



多项式的表示


系数表达 

系数表达是我们平时最常见的表示多项式的方法,对任意一个多项式$A(x)=\sum_{i=0}^{n-1}a_ix^i$,其系数表示为
 $$A(x)=(a_0,a_1,\dots,a_{n-1})$$  

系数表达的优势是它很容易求出该多项式在点$x_0$处的值$A(x_0)$,即利用霍纳法则(也称秦九韶算法): $$A(x_0)=a_0+x_0(a_1+x_0(a_2+\dots+x_0(a_{n-2}+x_0a_{n-1})\dots))$$ 

点值表达 

所谓点值表达就是将一个次数界为n的多项式用 n个点值对 的集合来表示,即: 

 $$A(x)=\{ (x_0,y_0),(x_1,y_1),(x_2,y_2)\dots(x_{n-1},y_{n-1}) \}$$  

需要注意的是,一定需要n个点值对来表示,因为只有点值对数等于多项式的次数界时,其插值(由点值表达确定该多项式的系数表达,后边会讲到)才明确,这个结论可以由插值多项式的唯一性证明: 

 $$\begin{vmatrix}\\
1 & x_0 & x_0^2 & \cdots & x_0^{n-1}\\
1 & x_1 & x_1^2 & \cdots & x_1^{n-1}\\
\vdots &  \vdots & \vdots & &\vdots\\
1 & x_{n-1} & x_{n-1}^2 & \cdots & x_{n-1}^{n-1}\\
\end{vmatrix}
\begin{vmatrix}\\
a_0\\
a_1\\
a_2\\
\vdots\\
a_{n-1}\\
\end{vmatrix}=
\begin{vmatrix}\\
y_0\\
y_1\\
y_2\\
\vdots\\
y_{n-1}\\
\end{vmatrix}$$  

先将多项式转化为矩阵乘法的形式,其中第一项为范德蒙德行列式,记为$V(x_0,x_1,x_2,\dots,x_{n-1})$,其值为 $\prod_{0\le j<k\le n-1}(x_k-x_j)$ ,显然当任意两个x值不同时该值不为0,故该矩阵可逆,进而可以求得$a=V(x_0,x_1,x_2,\dots,x_{n-1})^{-1}y$ , 故其唯一性得证!


点值表示有什么优势呢?我们可以在O(n)的时间内求出两多项式的乘积!如果我们有一种很快的算法可以将系数表达式转化为点值表达式,那么我们就可以快速计算出两多项式的乘积.为了快速实现两种表达方式的快速转化,我们引入一个概念,* 单 位 复 数 根 *!




单位复数根



定义

满足$w^n=1$的复数$w$,其单位复数根恰好有n个,分别为$e^{2\pi ik/n},k=\{0,1,2,\dots,n-1\}$,由复数的指数形式定义$e^{iu}=cos(u)+isin(u)$可将其转化为 $y_k=cos(2 \pi k/n)+isin(2\pi k/n)$



基本性质


消去引理 

 $$W_{dn}^{dk}=(e^{2\pi i/{dn}})^{kn}=(e^{2\pi i/{d}})^{k}=W_n^k(n\ge 0 , k\ge 0 , d>0)$$ 
折半引理 

若n>0且为偶数,那么n个n次单位复数根的平方的集合就是$n/2$个$n/2$次单位复数根的集合(每个元素出现两次) $$(W_n^{k+n/2})^2=W_n^{2k+n}=W_n^{2k}\cdot W_n^n=(W_n^k)^2=W_{n/2}^k$$ 
求和引理 

 $$\sum_{j=0}^{n-1}(W_n^k)^j=\frac{(W_n^k)^n-1}{W_n^k-1}=\frac{(W_n^n)^k-1}{W_n^k-1}=0$$ 




DFT离散傅里叶变换

这个算法的核心是利用了卷积定理
 $$a\times b=DFT^{-1}_{2n}(DFT_{2n}(a)\cdot DFT_{2n}(b))$$ 


本文最开始的例题UOJ#34,目标多项式的系数$c_k=\sum_{k=0}^ja_k*b_{k-j}$,熟悉的人可能都知道这实际上就是a,b的卷积,能用傅里叶变换求解的题目一般都可以被转化成类似这样的卷积的形式,大家一定要对这个式子足够熟悉!!!



 $$y_k=A(W_n^k)=\sum_{j=0}^{n-1}a_j\cdot W_n^{kj}=\sum_{j=0}^{n-1}a_j\cdot e^{\frac{2\pi i}{n}jk}$$  

该算法的复杂度是O($n^2$)的,有没有适当变换使其结合一些复数根的性质加速此过程?答案是肯定的!




FFT快速傅里叶变换





递归

利用分治的思想将$A(x)=a_0+a_1x+a_2x^2+\dots+a_{n-1}x^{n-1}$分为下标为奇数和偶数的两部分: 

 $$A^{[0]}(x)=a_0+a_2x+a_4x^2+\dots+a_{n-2}x^{\frac{n}{2}-1}$$   

 $$A^{[1]}(x)=a_1+a_3x+a_5x^2+\dots+a_{n-1}x^{\frac{n}{2}-1}$$  

 $$A(x)=A^{[0]}(x^2)+x*A^{[1]}(x^2)$$   

这样的话问题就可以转化求在$(W_n^0)^2,(W_n^1)^2,\dots,(W_n^{n-1})^2$上A(x)值,又根据折半引理,只需计算次数界为n/2的值即可,这样一直递归下去,即可在O($nlgn$)复杂度内计算出结果,附上伪代码:




FFT(a):  
    n=a.length()  
    if n==1:  
        return a  
    w_n=e^(pi*i/n)=complex(cos(2*pi/n),sin(2*pi/n))  
    w=1  
    a(0)=[a0,a2,...a_n-2]  
    a(1)=[a1,a3,...a_n-1]  
    y(0)=FFT(a(0))  
    y(1)=FFT(a(1))  
    for k in range(0,n/2):  
        y_k=y_k(0)+w*y_k(1)                     //w*y_k(1)为公用子表达式 
        y_k+n/2=y_k(0)-w*y_k(1)  
        w=w*w_n                                 //w为旋转因子
    return y  

但递归的常数是很大的,我们是否可以进一步优化常数呢?只要将递归过程改为迭代的过程就好了!



迭代


位逆序置换 

 

观察其下标序列为 $$0,4,2,6,1,5,3,7$$  

对应的二进制数为 $$000,100,010,110,001,101,011,111$$  

若将每个数的二进制位反转,即得到 $$000,001,010,011,100,101,110,111$$  

显然为0~7这8个数的升序排列,这样我们就找到了运算顺序与下标间的对应关系,这个过程就叫做位逆序置换,这样我们只要在计算之前将下标通过位逆序置换的方式更新即可按序自底向上求解,代码很简单:




inline int rev(int x,int n)                 //x为当前处理的待改变的数,n为二进制位的总长度(按上例则n=3)
{
    int x0=0;
    while(n--) x0=(x0+(x&1))<<1,x>>=1;
    return x0>>1;
}


蝴蝶操作 

 $$y_k=A(W_n^k)=y^{[0]}_k+W_n^k\cdot y_k^{[1]}$$  

 $$y_{k+\frac{n}{2}}=A(W_n^{k+\frac{n}{2}})=A^{[0]}(W_n^{2k+n})+W_n^{k+\frac{n}{2}}\cdot A^{[1]}(W_n^{2k+n})=A^{[0]}(W_n^{2k})+W_n^{k+\frac{n}{2}}\cdot A^{[1]}(W_n^{2k})=y^{[0]}_k-W_n^k\cdot y_k^{[1]}$$ 


因此只要知道出$y^{[0]}_k$与$W_n^k\cdot y_k^{[1]}$的值就可直接算出$y_k$与$y_{k+\frac{n}{2}}$的值,只要将上一步中分成的树状结构从下向上计算一遍就能求出答案了,这一操作也被称为蝴 蝶 操 作,伪代码如下:



for k in range(0,n/2):  
    t=w*y_k(1)  
    y_k=y_k(0)+t  
    y_k+n/2=y_k(0)-t  
    w=w*w_n 



傅里叶逆变换公式

以上我们了解到如何将系数表示转换为点值表示,通过点值表示在O(n)复杂度下求出多项式的乘积之后只要再将点值表示转换为系数表示(求插值)即可.前面讲多项式的点值表达时我们提到了一种求插值的过程,$a=V(x_0,x_1,x_2,\dots,x_{n-1})^{-1}\cdot y$ , 即只要得到范德蒙德行列式的逆矩阵就能求出对应的a.

由于一个矩阵的逆矩阵$A^{-1}=\frac{1}{|A|}A^*$,易推得傅里叶逆变换公式: 

 $$a_k=\frac{1}{n}\sum_{j=0}^{n-1}y^j\cdot e^{-\frac{2\pi i}{n}jk}$$  

除了这种求逆矩阵的方法,我们还可以用拉格朗日公式求插值,但复杂度为O($n^2$),公式如下: 

 $$A(x)=\sum_{k=0}^{n-1}y_k\frac{ \prod_{j\neq k}(x-x_j) }{ \prod_{j\neq k}(x_j-x_k) }$$ 




完整代码

大家最想要的代码来了,UOJ#34 AC代码:



#include<bits/stdc++.h>
#define pi acos(-1.0)
#define maxn 300010
//#define DEBUG                                     //DEBUG无视就好
using namespace std;
int n,m;
complex<double> a[maxn],b[maxn];

inline int read()                                   //读入优化
{
    char ch;
    int read=0;
    int sign=1;
    do
        ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-');
    if(ch=='-') sign=-1,ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        read=read*10+ch-'0';
        ch=getchar(); 
    } 
    return read*sign;
}

int Power2(int x)                                 //把x转化为2的整数次幂
{
    int x0;
    for(x0=1;x0<=x;x0<<=1) ;
    return x0;
}

inline int lg(int n)                             //计算二进制位数
{
    int l=0;
    if(n==0) return l;
    for(int x=1;x<=n;x<<=1) l++;
    return l;
}

inline int rev(int x,int n)                      //位逆序置换
{
    int x0=0;
    while(n--) x0=(x0+(x&1))<<1,x>>=1;
    return x0>>1;
}

void FFT(complex<double> a[],int n,int flag)    //主体
{
    complex<double> A[n+1];
    for(int i=0,l=lg(n-1);i<n;++i) A[rev(i,l)]=a[i];
    #ifdef DEBUG
        int l=lg(n-1);                          //切记是lg(n-1)
    cerr<<"l="<<l<<endl;
    for(int i=0;i<n;++i) cerr<<rev(i,l)<<" ";
    cerr<<endl;
    #endif 
        for(int i=2;i<=n;i<<=1)                 //枚举合并后序列长度
    {
        complex<double> dw(cos(2*pi/i),sin(flag*2*pi/i));
        for(int j=0;j<n;j+=i)                   //该长度下每部分进行求解
        {
            complex<double> w(1.0,0);
            for(int k=0;k<(i>>1);k++,w=w*dw)    //蝴蝶变换,只需求i>>1次 
            {
                complex<double> u=A[j+k];
                complex<double> t=w*A[j+k+(i>>1)];
                A[j+k]=u+t;
                A[j+k+(i>>1)]=u-t;
            }
        }
        if(flag==-1)
            for(int i=0;i<n;++i) a[i]=int(A[i].real()/n+0.5);
        else
            for(int i=0;i<n;++i) a[i]=A[i];
    }
}

int main()
{
    #ifdef DEBUG
    freopen("in.txt","r",stdin);
    #endif
    n=read();
    m=read();
    for(int i=0;i<=n;++i) a[i]=read();
    for(int i=0;i<=m;++i) b[i]=read();
    int length=Power2(n+m);
    #ifdef DEBUG
    cerr<<"length="<<length<<endl;
    #endif
    FFT(a,length,1);
    FFT(b,length,1);
    for(int i=0;i<=length;++i) a[i]*=b[i];
    FFT(a,length,-1);
    for(int i=0;i<=n+m;++i) printf("%d ",int(a[i].real()));
    return 0;
}



参考资料


  
http://blog.csdn.net/oiljt12138/article/details/54810204 

  http://blog.csdn.net/iamzky/article/details/22712347 

  算法导论第三十章


如有疑问欢迎积极评论 !

	

一提到傅里叶变换，学子们都会比较头痛
尤其是第一节周期信号的傅里叶级数就直接扼杀了继续学习的动力
很多学子都遨游在谷哥信号群中，享受着免费答疑和学习交流
考研视频课程：cctalk平台搜索82812059(其他平台为盗版)
其他学习群推荐：580889349(全国信号与系统学习1群)
650358224(全国信号与系统学习2群)
288715702(全国信号与系统学习3群)
                            864981185(2021届考研新群)
杜绝小号，杜绝中介，免费答疑不想妨碍各位大佬的抨击
傅里叶咋就这么难呢？o(╥﹏╥)oo(╥﹏╥)o
谷哥信号来解忧
(截图和内容节选自谷哥自编精华讲义，高分必备哦)
一、傅里叶变换的全部内容
二、傅里叶变换章节之间的关系
(1)周期信号的傅里叶级数属于数学内容，即从大家高数中学过的内容出发。主要讲解三角形式和指数形式傅里叶级数、频谱和带宽等；
(2)周期趋于无穷就成了非周期：毕竟常见信号还是非周期信号居多，所以这样就将周期信号的傅里叶级数转换成了非周期信号的傅里叶变换，进而讲了常见信号傅里叶变换、性质和应用等内容；
(3)假如冲激信号存在：既然非周期信号的FT都讲了，借助于周期信号是非周期信号的周期延拓关系，也就引出了周期信号的FT，以便让周期信号去进行采样啊(原来这个知识点是垫脚石O(∩_∩)O哈哈~)
(4)抽样的本质：时域被周期信号抽样，频域伴随着周期延拓，幅度变为之前的1/T倍。可见频谱会动，想了解抽样，可链接至会动的频谱——揭示傅里叶变换的抽样本质
(5)频谱动了就要想办法恢复，进而引出了抽样定理，无失真恢复和滤波器设计等。
三、傅里叶变换大题的克星揭秘(今日重点)
1、傅里叶变换最重要的两个大题考点——抽样与恢复、调制与恢复
2、学习建议：虽然带着抽样和调制等术语去学习，看懂就好，不要总是一味想着啥时候是抽样啥时候是调制，抓住重点，忘记术语，享受过程的本质；
3、傅里叶变换的大题的本质揭秘——乘法器
输入同样是频带受限的时域信号，框图同样是一个乘法器，但是另外一个输入：若是周期信号考察的是抽样，本质是频谱的周期延拓
      若是余弦信号考察的是调制，本质是频域的左右搬移
也就是说不管考察哪一种类型，归根到底就是频谱动了，和之前不一样了，正式不一样了，所以才牵扯出后期的利用滤波器等无失真恢复内容。
~~~恭喜你，终于了解傅里叶变换的本质了，下面在跟着谷哥看看解题~~~
~~~所有内容节选与谷哥自编精华讲义哦~~
自编讲义(知识点总结、解题步骤总结、结论总结、逆向思维总结+例题)
+章节练习题+考研模拟测试题+答案。40元全国包邮中~~
每日发货中，加群直接找管理员即可