[FFT] 例题详解

2024-04-10 11:52| 来源: 网络整理| 查看: 265

FFT是什么

FFT（Fast Fourier Transformation）就是“快速傅里叶变换”的意思，它是一种用来计算DFT（离散傅里叶变换）和IDFT（离散傅里叶反变换）的一种快速算法。这种算法运用了一种高深的数学方式、把原来复杂度为O(n2)的朴素多项式乘法转化为了O(nlogn)的算法。

FFT在算法竞赛中的例题

FFT能将多项式乘法O(n^2) 优化为 O(nlogn)

但是题目中并不是直接了当的求多项式乘法，而是将问题转化成多项式乘法的形式。

高精度乘法-HDU1402

众所周知高精度乘法其实是两个字符串模拟乘法，而两个字符串可以看成两个多项式，满足多项式乘法的性质。

可以使用FFT加速

#include using namespace std; const double pi = acos(-1.0); // 复数结构体 struct Complex { double x,y; Complex(double _x = 0.0,double _y = 0.0) { x = _x; y = _y; } Complex operator - (const Complex &b)const { return Complex(x-b.x,y-b.y); } Complex operator + (const Complex &b)const { return Complex(x+b.x,y+b.y); } Complex operator * (const Complex &b)const { return Complex(x*b.x-y*b.y,x*b.y+y*b.x); } }; /* 进行FFT和IFFT前的反转变化 * 位置 i 和 (i 二进制反转后位置) 互换 * len 必须为 2 的整数幂 */ void change(Complex y[],int len) { int i,j,k; for(i=1,j=len/2;i= k) { j -= k; k /= 2; } if(j < k) j += k; } } /* * FFT * len必须是2^k形式 * on = 1是FFT， -1是IFFT */ void fft(Complex y[],int len,int on) { change(y,len); for(int h=2;h

【本文地址】

公司简介

联系我们