fft学习笔记

学习网站:

http://tieba.baidu.com/p/2513502552?see_lz=1

http://picks.logdown.com/posts/177631-fast-fourier-transform

fft很早以前大概学过,但是其实根本没理解,然后现在重学。

收获挺大的,毕竟花费一整晚。

打了一个板子

BZOJ 2179: FFT快速傅立叶

裸题,在黄学长blog上抄的:革命尚未成功,同志仍需努力。http://hzwer.com/3668.html

不过还是颇有收获。

系数表示  -> 点值表示 -> 乘法 -> 点值表示 -> 系数表示

在大佬quack的指点下总算大概明白了这点。

然后其他就是在代码里面的加速,就是利用蝴蝶变换实现迭代版。

然后内部的原理明天继续琢磨

以下是quack的一些话:

day2

以下是quack的一些话:

在quack大佬的推荐下看了很多blog

popoqqq大佬一下午就学完了%%%%%%%%%%

bzoj2194: 快速傅立叶之二

fft 暂时当成了个黑匣子;

手写了一遍。

如果是fft(a,1)相当于从系数转为点值

如果是fft(b,-1)相当于从点值转为系数

c++代码如下:

 

理解的确逐步加深。做题果然进步的良师。

BZOJ3527: [Zjoi2014]力

实际就是直接除以pi然后化为卷积的形式,两个卷积分开弄,完了

c++代码如下:

 

 

(待更。。。)

回复

6 + 4 =