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++代码如下:

 

http://blog.miskcoo.com/2015/04/polynomial-multiplication-and-fast-fourier-transform#i-15

随便再加一点:

3992: [SDOI2015]序列统计

容易列出dp方程f[i][j]表示第i个位置乘积为j的方案数。
那么推出转移 f[i+1][j*p\%m] += f[i][j]
此时复杂度O(n*m^2) 显然不能接受
想到对于n特别大的情况一般都会用快速幂。
那么可以列出一个m*m的矩阵进行转移,复杂度O(\log n * m^2)
明显还是不能接受,发现瓶颈在于m.
考虑利用fft把 m^2优化掉
如何优化,发现因为j*p\%m导致没法直接递推
那么利用原根g的性质,求出m的原根。
已知g^i互不相同,令i = g[i]
那么原方程可写作f[i+1][g^j*g^p\%m] += f[i][j] \to f[i+1][g^{j+p\%m}] += f[i][j]
那么这样显然可以用fft优化
复杂度O(\log n *\log m*m)
c++代码见:[序列统计]

codeforces:D. Fuzzy Search

fft下标一定要从0开始,不然特麻烦
观察题目容易发现,可以在O(n)时间内判断对于位置i是否能在[i-k,i+k]区间存在 A G C T
然后得到一个O(n*m)的算法,考虑优化
那么分开考虑 A G C T,令s[i]表示在第i个位置匹配到了多少字母。
s[i] = \sum_{j=1}^m k[i-j]*t[j]其中k[i]表示第i个位置是否能匹配到某一个字母
类似于某个字符串匹配的题一样 ,t数组还是要取反。
然后fft即可,注意要四舍五入,复杂度O(n\log n)
c++代码见:[该题代码]

(待更。。。)

回复

  1. 回复 kkksc03

    你好:cool: :cool: :mad: :roll: :wink: :arrow: :neutral: :mrgreen: :cry: :cry: :cry: :cry: :cry: :arrow: :arrow: :arrow: :arrow: :arrow:

8 + 5 =